My solution is Submission #14182185 - Educational DP Contest
passed 16/28.
Can someone help??
You were missing one condition
vector <bool> dp(k+1);
for(int i=0;i<=k;i++)
{
for(int j=0;j<n;j++)
if(i>=arr[j] && !dp[i-arr[j]])
dp[i]=1;
}
if(dp[k])
cout<<"First\n";
else
cout<<"Second\n";
Sorry but I couldn’t find any extra condition in your code. Could you please mention?
Try
1 100000
1
What if your inner loop never stops
Thanks a lot!!
Your example did the job.
I initially thought , a[j]<=i would work and skipped that condition.
Can you help me in this?
Your size of dp[][] is less than the available constraints. Make it dp[3001][3001]
what’s wrong with me? I think I’m going crazy.
Sorry for disturbing for such a silly error.
And Thanks a lot!!
Chill bro, it happens sometime.
try the above mentioned input
I did and the problem has been solved.
Thanks!!
welc
Hey, Can you help me in this?
Not able to move even a single step forward.
Can u give me some hints , how to approach the problem?
No of subseq with gcd=1 is ans
Actually, I had already figured it out. but how to proceed further?
See for each value, it has two options (taken or not). Now for each arr[i] take two cases and when you have reached last count , see if gcd is 1 then return 1. I mean in case of recursion just pass pos and current gcd as its argument
Won’t this give TLE?
Edit: I did and got TLE.
(Might be a possibility that I didn’t get what you suggested. So here is my solution: CodeChef: Practical coding for everyone)
Man with memoization
Code
#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
#define lld long long int
#define pb push_back
#define fo(i,a,b) for(int i=a;i<b;i++)
#define foe(i,a,b) for (int i=a;i<=b;i++)
lld n,dp[70][100000],arr[61];
lld gcd(lld a, lld b){
if (b==0) return a;
else
return gcd(b,a%b);
}
// x is defined to initiate curgcd
lld fun(lld ind,lld curgcd)
{
if (ind==n+1 && curgcd==1)
return 1;
if(ind==n+1&&curgcd!=1)
return 0;
if(dp[ind][curgcd]!=-1)
return dp[ind][curgcd];
return dp[ind][curgcd]=fun(ind+1,gcd(curgcd,arr[ind]))+fun(ind+1,curgcd);
}
void solve()
{
cin>>n;
foe(i,1,n)
cin>>arr[i];
memset(dp,-1,sizeof(dp));
lld ans = fun(1,arr[0]);
if(n==1&&arr[0]==1)
cout<<"1\n";
else
cout<<ans<<"\n";
}
signed main()
{
faster;
int t;cin>>t;
while(t--)
solve();
}
Ohh Sorry. I thought that It will calculate every state once even without memoization.
Got Ac after using memoization.
Thanks Btw