Problem - I - Coins
Anyone can guide me through this problem would be appreciated.
I am not able to make any progress in solving this question.
What’s the approach to solve this problem?
How did you reached to the conclusion that using dp will be beneficial?
P.S- I checked on here Dynamic Programming - AtCoder educational dp contest - YouTube
It’s about Errichto’s stream on solving this problem but i couldn’t understand.
This is indeed a DP problem. Now, to answer your question why, we would first begin with a brute-force approach as with any other DP problem and later on realise that the problem contains Overlapping Subproblems and Optimal Substructure.
So, first thing first, let us try to solve this using recursion. The problem states that we want to have more heads than tails, so we want all the possible permutations and combinations where number-of-heads > N/2. Now, think about how would you solve this naively using recursion? Give it thought for a moment and come back. If you are stuck then proceed below.
Say, for example, we have a function f(n, K) which can count the probability of getting K heads using last n coins only, now we start with the coin number 1, and for this coin, and for any coin in general we have two choices - either make it a head or make it tail. Let us suppose for convenience that we currently are at the index i, and so, as per the question the probability of getting a head here is p_{i}(read as p subscript i) (oops! can we use Latex in Markdown? Anybody let me know if we can), so the recursion from the next will proceed as follows(assume 1 based indexing instead of 0)-
p_{i} * f(n - i, K - (heads_selected_so_far + 1)) -> select a head here
+
(1 - p_{i}) * f(n - i, K - (heads_selected_so_far)) -> select a tail here
Now, do you see repeated branches of computation here? No? Draw the recursion tree on a plain sheet of paper and you will(with enough practice you don’t even need to do that) :).
Now, once you realise that this question indeed has computations we can memoize we, we simply add all the results for getting head > N/2 using all the coins, that is to say, if we have N coins in total and that dp[i][j] represents the probability of getting j heads using first i coins then we add dp[N][N/2 + 1] + dp[N][N/2 + 2] + ... + dp[N][N] to the answer.
Now, how to do the bottom-up? It is not very hard from here(if you understood everything till here) and if you have tried some problems on DP previously(such as LCS) then it shouldn’t be much tough. I will leave it on you to try to that for the moment, if you are still stuck fill free to ask me. 
Thanks man, I appreciate you taking your time to answer my query.
I understood it why we needed DP. 
If you want, you can see my commented AC submission here. This uses the Bottom Up approach-
COINS - Atcoder Bottom Up DP
I solved the question bottom up myself after you guided it. It looks most of the problem of dp generally as far as i have seen can be computed by using 2D matrix.
Like LCS, Knapsack and this particular problem.
So i think when i get stuck i can think of giving a try with a 2D matrix approach.
Thanks @anon62928982, I learned much from this problem
Thanks .
Thank Youn for your soln but cout << fixed << setprecision(10) << res; gives you a output of 10 digits in decimal…
which is not expected in test case 1: 0.612 against 0.6120000000
Can you please tell how can I get correct outpu???
ok got it… Just remove fixed
Amazing explanation
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator>
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
#include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb push_back
#define res(v) v.resize(unique(v.begin(), v.end()) - v.begin());
#define cnt_res(v) std::distance(v.begin(),std::unique(v.begin(), v.end()));
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
using namespace std;
const int N=3e3+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
double dp[N][N];int n;double a[N],ans;
void solve(){
cin>>n;dp[0][0]=1;
rep(i,1,n)cin>>a[i];
rep(i,1,n)
rep(j,0,i){
if(j!=0)dp[i][j]=dp[i-1][j-1]*a[i]+dp[i-1][j]*(1-a[i]);
else dp[i][j]=dp[i-1][j]*(1-a[i]);
}
rep(i,0,n)
if(i>n-i)
ans+=dp[n][i];
cout<<setprecision(20)<<ans;
}
int32_t main()
{
ibs;cti;
solve()
/*,cout<<"\n"*/;
// cout<<"\n";
int xx=0;
// int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<":\n"*/;solve();cout<<"\n";}
return 0;
}A recursive Solution
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
int tot = 0 ;
double d(int i , vector<double>&arr, int numtell,vector<vector<double>>&dp)
{
int a = arr.size();
if(numtell==a/2){
double sum = 1;
for(int j = i;j<a;j++){
sum *= arr[j];
}
return sum;
}
if(i>=arr.size())return 1;
if(dp[i][numtell]!=-1)return dp[i][numtell];
double total = 0;
double total2 = 0;
double sum = 0 ;
if(numtell<a/2){
total = (1-arr[i])*d(i+1,arr,numtell+1,dp);
}
total2 = (arr[i])*d(i+1,arr,numtell,dp);
sum += total;
sum+=total2;
return dp[i][numtell] = sum;
}
int main()
{
int n;
cin>>n;
vector<double>arr(n);
for(int i =0 ; i <n;i++)cin>>arr[i];
vector<vector<double>>dp(n,vector<double>(n/2 +1 ,-1));
cout<<setprecision(12)<<d(0,arr,0,dp);
return 0;
}
Thanks for the reply, it’s finally working for me.