 # K - Stones

My solution is https://atcoder.jp/contests/dp/submissions/14182185
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";
``````
2 Likes

Sorry but I couldn’t find any extra condition in your code. Could you please mention?

Try
1 100000
1

1 Like

What if your inner loop never stops

1 Like

Thanks a lot!!
I initially thought , a[j]<=i would work and skipped that condition.

Can you help me in this?

1 Like

Your size of dp[][] is less than the available constraints. Make it dp

3 Likes

what’s wrong with me? I think I’m going crazy.
Sorry for disturbing for such a silly error.
And Thanks a lot!!  1 Like

Chill bro, it happens sometime.

2 Likes

try the above mentioned input

1 Like

I did and the problem has been solved.
Thanks!!   1 Like

welc

1 Like

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: https://www.codechef.com/viewsolution/34551576)

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,arr;

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);
if(n==1&&arr==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 