CNDYGAME - Editorial

i guess

Oh I thought it is some concept😅. BTW I used DP but only got 15 points, since it is using O(R) space which is 10^12, so it throws RuntimeError

I am so far not a great coder, looking at the question and after going through it I did get a know of almost all the edge cases but when i tried to code it… Ufff
The video editorial did help me understand the edge cases i missed but not how to go about the code…
Could anyone help me with a commented well written code please

Can someone find a failing testcase for my sol https://www.codechef.com/viewsolution/39684545

It passes the very last test, no idea what is wrong.

Thank you!

good question but poorly explanied by the video guy you should have explained the code along with the cases so it becomes more easy to understand … it looked like you were just trying to wrap it up asap when you were showing the code

You are failing on test case for example

N=5
1 2 3 4 5
Q=5
r=7
the answer should be 2 but your code is showing 1.

So you are failing on all the input where the first element is 1

2 Likes

My whole code failed because of one edge test case alone.I was so frustrated.

#include <bits/stdc++.h>
#define ll unsigned long long int
#define MOD 1000000007

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–){
ll n;
cin>>n;
ll arr[n];
for(int i=0;i<n;i++) cin>>arr[i];

   ll chef[n],chefGreed[n];
   memset(chef,0,sizeof(chef));
   memset(chefGreed,0,sizeof(chef));
   
   if(arr[0]==1){
       for(int i=0;i<n;i++){
           chef[i]=1;
           if(i==0 && n>1) chefGreed[i]=0;
           else chefGreed[i]=1;
       }
   }
   else{
       // normal case + greedy case
       if(arr[0]%2==0){
           if(n>1) chef[0]=arr[0];
           else chef[0]=arr[0]-1;
       }
       else{
           if(n>1) chef[0]=arr[0]-1;
           else chef[0]=arr[0];
       }
       chefGreed[0]=arr[0];
       for(int i=1;i<n;i++){
           if(i==n-1){
               if(arr[i]%2==0) chef[i]=(chef[i-1]+arr[i]-1)%MOD;
               else chef[i]=(chef[i-1]+arr[i])%MOD;
           }
           else if(i+1<n-1 && arr[i+1]==1){
               if(arr[i]%2==0){
                   chef[i]=(chef[i-1]+arr[i]-1)%MOD;
                   chef[i+1]=(chef[i])%MOD;
                   chefGreed[i]=(chef[i]+1)%MOD;
                   chefGreed[i+1]=(chefGreed[i]+1)%MOD;
                   i++;
                   continue;
               }
               else{
                   chef[i]=(chef[i-1]+arr[i])%MOD;
                   chef[i+1]=(chef[i])%MOD;
                   chefGreed[i]=(chef[i])%MOD;
                   chefGreed[i+1]=(chefGreed[i])%MOD;
                   i++;
                   continue;
               }
           }
           else{
               if(arr[i]%2==0) chef[i]=(chef[i-1]+arr[i])%MOD;
               else chef[i]=(chef[i-1]+arr[i]-1)%MOD;
           }
           chefGreed[i]=(chef[i-1]+arr[i])%MOD;
       }
       
   }
   
//   for(int i=0;i<n;i++){
//       cout<<chef[i]<<" ";
//   }
//   cout<<"\n";
//   for(int i=0;i<n;i++){
//       cout<<chefGreed[i]<<" ";
//   }
//   cout<<"\n";
   
   int q;
   cin>>q;
   while(q--){
       ll r;
       cin>>r;
       
       ll ans=0;
       if(r<=n){
           if(arr[0]!=1) ans=chefGreed[r-1];
           else ans=1;
       }
       else{
           if(r%n==0 || (n==1 && arr[0]==1)){
               ans=(ans+((chef[n-1]*((r/n-1)%MOD))%MOD))%MOD;
               ans=(ans+chefGreed[n-1])%MOD;
           }
           else{
               ans=(ans+((chef[n-1]*((r/n)%MOD))%MOD))%MOD;
               ans=(ans+chefGreed[(r%n)-1])%MOD;
           }
        //   if(r%n==0) ans=(ans+chefGreed[n-1])%MOD;
        //   else ans=(ans + chefGreed[r%n])%MOD;
       }

       cout<<(ans%MOD)<<"\n";
   }

}

return 0;
}

My code has also passed subtask 2 but it fails for 15 pts. I have tried all test case and inserted MOD everywhere. Can you please tell me where I am wrong?

plz tell where i am geting wrong answer
https://www.codechef.com/viewsolution/39646006

i have one small doubt, lets say the candy[ ]={2,5,6,3 };
and I am standing at the last index i.e 3,if I choose 3 candies here will my place change 2 times?

For Test case

1
3
3 1 5
1
3
Expected output: 8
Your output: 7

1 Like

Your place will change once but the status of counter will be the same even after swapping places

Both mine and tester’s solution is commented. If you get stuck somewhere, feel free to ask :slight_smile:

https://www.codechef.com/viewsolution/39797040

Please tell any test case where my code fails. I have verified with editorial also and it passes all test cases mentioned there. It would be very helpful if you can suggest some case where my code can get fails

Thanks in Advance

@utkarsh911 can you please see to it. Thanks

One of the test case where this code fails is

1
2
1 5
1
4

Expected output: 2

anyone plz reply me

I always thought the value could be the same, my goodness.

But I think output should be 6 corresponding to it. Chef will have to take 1 in first turn and then has to swap position with chefu. After third turn chefu and chef again exchange position and chef will take 5 candies finally. So total 6 candies.

Turn 1: Chef takes 1, he has no other option, Switching
Turn 2: Chefu will take 4 here.
end of array so we have to switch again. Chef on open counter.
Turn 3: Chef takes 1 again, Again switch
Turn 4: Chefu takes 4

Ans: 2