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:
- Take the maximum number of candies in a given turn.
- 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 = 2Case 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 = 1Considering 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:
- 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
- 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;
}
)
