AtCoder DP Contest Q -I Coins (getting wrong answer may be using double)

Question

Link to Problem -> https://atcoder.jp/contests/dp/tasks/dp_i

question Coins-I
Code I wrote gave wrong answer to TEST CASE 3

5
0.42 0.01 0.42 0.99 0.42

Expected output

0.3821815872

MY code output

0.382182

As the error is greater than 1e-9 it got WA

What I tried:

I made double to long double but still it doesn't give accuracy is there any way to increase the accuracy when working with double in this question.

#include<bits/stdc++.h>
using namespace std;

long double p[3000];

long double dp[3001][1501];



long double solve(int i,int tail_count){

    if(dp[i][tail_count]!=2){
        return dp[i][tail_count];
    }
    long double ans=0;

    if(i==1 && tail_count==0)return p[1];

    else if(i==1 && tail_count>0)return (long double)1;

    else if(tail_count==0)ans= p[i]*solve(i-1,tail_count);
    else ans= (p[i]*solve(i-1,tail_count)+(1-p[i])*solve(i-1,tail_count-1));

    dp[i][tail_count]=ans;
    return ans;
}


int main(){
    for(int i=0;i<3000;i++){
        for(int j=0;j<1500;j++){
            dp[i][j]=2;
        }
    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    
    cout<<solve(n,(n-1)/2);
    return 0;
}

OT: read this: https://stackoverflow.com/questions/25311011/how-does-include-bits-stdc-h-work-in-c — Jabberwocky, Jan 13 '22 at 07:47
it will solve other problems that you didn't encounter yet. Same is true for [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — 463035818_is_not_an_ai, Jan 13 '22 at 07:52
when you write "Expected output" do you mean the first line is the correct and the second line is your wrong output? — 463035818_is_not_an_ai, Jan 13 '22 at 07:53

score 2 · Accepted Answer · answered Jan 13 '22 at 08:38

The number of digits to be printed via output streams is controlled by their precision parameter. The default is 6 digits, if you want more you need to adjust it accordingly by std::setprecision :

std::cout << std::setprecision(num_digits) << solve(n,(n-1)/2);

Most of your indexing is off by one. Valid indices of an array with N elements are 0 till (including) N-1. dp is 3001 x 1501 but you only use 3000 x 1500 and p leaves the first element unused. Perhaps the code is still correct, but at least your way of using indices is confusing. Also in case you know the size of the array only at runtime you could use a std::vector.

AtCoder DP Contest Q -I Coins (getting wrong answer may be using double)

1 Answers1