CNDYGAME - Editorial

PROBLEM LINK:

Practice
Division 1 Contest
Division 2 Contest

Author: Utkarsh Pandey
Tester: Istvan Nagy
Editorialist: Utkarsh Pandey

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Prefix sum, Observation

PROBLEM:

A game is played between two players. There are two counters out of which only one is active at a time. Both players are always at different counters. On each turn, the counter offers some number of candies to the player in front of it. This player can accept some number of candies(at least one) out of the offered candies. Players have to swap their positions if the number of candies accepted by the player is odd and again at the end of each N rounds. Find the maximum number of candies a player can get ensuring the other player gets as less as possible as a second priority, if he gets to start from the active counter and both players play the game optimally.

QUICK EXPLANATION:

The optimal strategy to play the game is:

  1. Take the maximum number of candies in a given turn.
  2. Ensure yourself to be present at the open counter in next turn (Except some special cases).

EXPLANATION:

Click only if you're a cricket fan

Q: What can be the maximum score of a single opening batsman in a cricket match?

A: Very easy, right? He will score 5 sixes in each over and take 3(or 5?) runs on the last ball of each over to retain the strike in next over. Also in the last over, he will hit all 6 balls for six(because he don’t need the strike anymore).

Let’s change the question a little now. Till now, the batsman could only score between 0 to 6 in each ball. What if we change this condition?

The question is tough now? We have to use DP?
NO. It’s the same and we can solve it almost the same way.

This problem can be solved greedily by accepting the highest number of candies in a given turn while making sure to retain control(be present at the active counter) in the next turn.

Conclusion

Take the maximum possible even number of candies in each turn i when i mod N \neq 0 and take the maximum possible odd number of candies in each turn i when i mod N = 0

Why this works?

In each turn, we reject at most one candy out of the total number of offered candies to retain control in the next turn. This is the optimal choice because even by rejecting one candy we are making sure that we get at least one candy in the next round(and the other person doesn’t get anything)

By following this strategy, Chef is only forced to lose control when A_i = 1. Also A_i will be 1 at most 1 time because all elements in the array are pairwise distinct.

There are 4 cases now:

Case 1 (No 1 in the array A): The optimal strategy will be to take maximum possible even number of candies in each turn i mod N \neq 0 and maximum possible odd number of candies in each i mod N = 0.
Using this strategy, Chefu will not get a single chance to be at the active counter. Also on R-th turn, take all the candies without considering it’s parity (because we want to maximize the no. of candies till this round only and we don’t care about retaining control in the next round).

Example test case

A = [2,5,6,4]
R = 6
Answer = 2 + 4 + 6 + 3 + 2 + 5 = 22

Case 2 (A_1 = 1): In this case, Chef will be forced to take 1 candy at the start of the game and will lose control. Chefu playing optimally, will not lose control to Chef for the next (N-1) rounds by picking even number of candies and will pick odd number of candies in each N-th turn so that Chef gets control on each i-th turn such that i mod N = 1, and is forced to take 1 candy and lose the control again.

Example

A = [1,5,6,3]

  • Chef will take 1 and will lose control.
  • Chefu will take 4, 6 and 2.
  • Then Chef will again have to take 1 and lose control.
  • And this process will go on.

Edge Case (R \neq 1 and R mod N = 1): In this case, Chefu will not lose control in (R - 1)-th turn and will take 1 candy in R-th turn(to minimize Chef’s candies while ensuring his number of candies remains same).

Example test case 1

A = [1,5,6,3]
R = 5
Chef takes 1 and loses control.
Chefu takes 4, 6, 3 and 1.
Answer = 1

Example test case 2

A = [1,5,6,2]
R = 5
Chef takes 1 and loses control.
Chefu takes 4 and 6. Now in the 4-th turn, Chefu has 2 choices:

Case 1: Take 2 candies and lose the control.
Number of candies of Chefu at the end = 4 + 6 + 2 = 12
Number of candies of Chef at the end = 1 + 1 = 2

Case 2: Take 1 candy and retain the control.
Number of candies of Chefu at the end = 4 + 6 + 1 + 1 = 12
Number of candies of Chef at the end = 1

Considering 2-nd priority of the game, Chefu will choose the 2-nd case as it lowers Chef’s candies.

Answer = 1

Case 3 (1 at index i where 1 \leq i \leq N): The optimal strategy in this case is to lose control when A_{i+1} = 1 so that the control is retained again in (i + 2)-th turn

Example test case

A = [3, 2, 1, 5, 6]
R = 5
Chef takes 2 and 1
Chefu takes 1
Chef takes 4 and 6
Answer = 2 + 1 + 4 + 6 = 13

Special cases:

  1. If R mod N = i-1 and A_{i-1} mod 2 = 0, Chef will take A_{i-1} candies in last turn.
Example test case

A = [3, 2, 1, 5, 6]
R = 2
Chef takes 2 and 2 (did not lose control before 1)
Answer = 2 + 2 = 4

  1. If R mod N = i and A_{i-1} mod 2 = 0, Chef will take A_{i-1} candies in second last turn and will take 1 candy in the last turn.
Example test case

A = [3, 2, 1, 5, 6]
R = 3
Chef takes 2, 2 and 1 (again did not lose control before 1)
Answer = 2 + 2 + 1 = 5

Case 4 (A_N = 1): The strategy of this case is same as that of 1-st case.

Implementation

Since Q and R both are very large, we can precompute the prefix array P for the given array where P_i stores the maximum amount of candies(kind of) Chef can get after round i, for 1 \leq i \leq N. For each R \geq N, we can multiply P_N with a scaling(periodic) factor and add the remnants accordingly.

Since there are a lot of I/O operations, use fast I/O to avoid TLEs.

Time Complexity:

The time complexity is O(N) for precomputation and O(1) per query which makes it O(N + Q) per test case.

Solutions:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define ll long long
#define fo(i,a,n) for(ll i=a;i<n;i++)
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t,n,i,j,ans,q;
	cin>>t;
	while(t--){
	cin>>n;
	ll a[n+1],pref[n+1];
	for(ll i=1;i<=n;i++)
	cin>>a[i];
	ll f=0,in,sum=0;
	for(ll i=1;i<=n;i++){
	if(a[i]==1 && i==1){ // f=1 for 1 at start
        f=1;break;
	}
    else if(a[i]==1 && i==n){ // f=0 for no 1 or 1 at end
        f=0;break;
    }
    else if(a[i]==1){ // f=2 for 1 at mid
        f=2;
        in=i; break;
    }
	}
 
    pref[0]=0;
    if(!f){                    // No 1 or 1 at end
      fo(i,1,n)
      pref[i]=(pref[i-1]+((a[i]&1)?(a[i]-1):a[i]))%M;
      if(a[n]&1)
        pref[n]=(pref[n-1]+a[n])%M;
      else
        pref[n]=(pref[n-1]+a[n]-1)%M;
        pref[0]=pref[n];
 
	}
    else if(f==2){                 // 1 at mid
       fo(i,1,n){
           if(i==in){
            pref[i]=pref[i-1];
            continue;
           }
       if(i+1==in)
        pref[i]=(pref[i-1]+((a[i]&1)?(a[i]):(a[i]-1)))%M;
       else
        pref[i]=(pref[i-1]+((a[i]&1)?(a[i]-1):a[i]))%M;
       }
       if(a[n]&1)
        pref[n]=(pref[n-1]+a[n])%M;
      else
        pref[n]=(pref[n-1]+a[n]-1)%M;
        pref[0]=pref[n];
    }
 
    cin>>q;
    while(q--){
        ll r;
        cin>>r;
 
        if(f==1){                               // 1 at start
              ans=(r/n)%M;
              if(r%n)
              ans++;
              if(r!=1 && r%(n)==1)
              ans--;
              cout<<ans%M<<endl;
              continue;
        }
        // else
        ans=(((r/n)%M)*(pref[n]%M))%M;
        if(r%n!=0)
        ans=(ans+pref[r%(n)])%M;
 
        if(!f){                                     // No 1 or 1 at end
            if(r%(n)!=0 && (a[r%(n)]&1))
            ans++;
            if(r%n==0 && (a[n]%2==0))
            ans++;
            cout<<ans%M<<endl;
            continue;
        }
 
        if(f==2){                                   // 1 at mid
            if(r%(n)!=0 && r%n!=in-1 && r%n!=in && (a[r%(n)]&1) )
            ans++;
            if(r%n==0 && (a[n]%2==0))
            ans++;
            if(r%n==in-1 && a[r%n]%2==0)
            ans++;
            if(r%n==in && a[in-1]%2==0)
            ans+=2;
            cout<<ans%M<<endl;
            continue;
        }
	}
	}
}
Tester's Solution
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < (int)(n); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

//CNDYGAME
int main(int argc, char** argv) 
{
	int T;
	scanf("%d",&T);
	const int MOD = 1e9 + 7;
	int qc = 0;
	int sumNQ = 0;
	int64_t lastq = 0;
	forn(tc, T)
	{
		int N;
		scanf("%d",&N);
		vector<int> A(N), R;
		for(auto& ai: A)
			scanf("%d",&ai);
			
		//if the first value is 1 thats sucks
		int br = 0;
		if (A[0] == 1)
		{
			R = vector<int>(N, 1);
			R[0] = 0;
			br = 1;
		}
		else
		{
			//if 1 in the middle, than the prev should be also odd
			//if the last is 1 it doesnt matter
			int r0 = 0, r1 = 0;
			forn(i, N)
			{
				int prevr0 = r0;
				r0 = (r1 + (A[i] & 1 ? A[i]: A[i]-1)) % MOD;
				if (i + 1 == N)
					br = (r1 + (A[i] & 1 ? A[i] : A[i] - 1)) % MOD;
				if (A[i] == 1)
				{
					r1 = prevr0;
				}
				else
				{
					r1 = (r1 + (A[i] & 1 ? A[i] -1 : A[i])) % MOD;
				}
				R.push_back(max(r0, r1));
			}
			
		}
		

		int Q;
		scanf("%d",&Q);
		sumNQ += Q;
		uint64_t actq;
		forn(q, Q)
		{
			scanf("%llu",&actq);
			lastq = actq;
			if (N == 1)
			{
				uint64_t ans = (A[0] % 2 ? actq * A[0] : actq * (A[0] - 1) + 1);
				ans %= MOD;
				printf("%llu\n",ans);
				continue;
			}
			--actq;
			
			if (actq == 0)
			{
				cout << A[0] << '\n';
				continue;
			}
			uint64_t ans = actq / N;
			ans = (ans * br) % MOD;
			ans += R[actq % N];
			ans %= MOD;
			printf("%llu\n",ans);
		}
	}
	return 0;
}

VIDEO EDITORIAL:

7 Likes

this question is made to gift to enemies & relatives

23 Likes

I didn’t like this problem. There was nothing to learn, just annoying casework and implementation.

41 Likes

Good problem to frustrate people.

:confused:

10 Likes

A more interesting problem arises when the numbers are not all distinct(so we can have many 1s :upside_down_face:)

4 Likes

yes I missed distinct on the first go… and the pain which followed.

9 Likes

wrote nearly 200 lines of codes, submitted 20+ times, just to get partial correct :joy: :joy: , it was full of corner cases

3 Likes

Damn I missed it throughout the contest. I had almost built a solution for non-distinct numbers but it was failing for one case…

4 Likes

Same for me :frowning:

I didn’t read the word DISTNCT integers thus writing a 400 lines code for numerous types of cases and ending up wasting 3 days, making it heavily complicated.
Also tried to submit couple of times after debugging thus increasing my rank from 1700 to 2000 now.
This was my first contest which I followed from the first day of the challenge.
But anyways now I am waiting for the upcoming contests eagerly.

3 Likes

This problem taught me to read the question thoroughly and plan first with a pen and paper. I didn’t read the word DISTINCT and wrote a 350 + line code only to end up increasing my wrong submissions and wasting days thinking about it.

3 Likes

Any test-case on which my code goes wrong (only for 15pts). It will be really helpful. Thank you :slight_smile:
https://www.codechef.com/viewsolution/39484959

Absolutely agree, just one of those problems where you’re just looking forward to get it over with and forget about it next minute. Nothing to learn at all. But I do understand that solving these types of problems with multiple edge cases is also a skill, so fine with having 1 problem like this on a challenge.

5 Likes

Why don’t you people atleast give 3 or 4 test case like codeforces
just because of one edge case my whole program got WA

2 Likes

requires DP then ig

Question quality was fine but its explanation was worst,
and the worst thing is long challenges.

1 Like

try
1
3
1 2 4
1
4
it should output 1 but as per your code it output 2 :upside_down_face:

3 Likes

https://www.codechef.com/viewsolution/39542628
What was wrong in this code?

1
5
2 3 4 5 1
5
1
2
3
4
5

at 5 the answer should be 2+2+4+4+1=13
your output is 14
check your code if 1 is at last position

1 Like

FEMA2 Iron Magnet wall Solution :- https://youtu.be/HtT9bexr1SA