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!!
Your example did the job.
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[3001][3001]

3 Likes

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

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!!:upside_down_face::slightly_smiling_face::upside_down_face:

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[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 :upside_down_face: