RING_GAME - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: wuhudsm
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

1666

PREREQUISITES:

Observation

PROBLEM:

Alice and Bob play a game on a circle with black and white pieces. On their move, a player can choose any subarray of this circle and left-rotate it once. As an extra condition, a move is only valid if the number of positions i with A_i \neq A_{i+1} strictly increases after the move is made.

The person who cannot make a move loses. Determine who wins under optimal play.

EXPLANATION:

The main observation to be made here is as follows:

Let diff(A) denote the number of adjacent pairs of indices with different values in A. Then, any valid move increases diff(A) by exactly 2 - as such, a move is valid if and only if it increases diff(A) by 2.

Proof

This is not too hard to see.

Suppose we perform the rotate operation on the range [L, R]. This is essentially the same thing as deleting A_L from its position, and then inserting it between A_R and A_{R+1}.

Let’s analyze the deletion step:

  • If A_{L-1} = A_{L+1}, deletion decreases diff(A) by either 0 or 2, depending on the value of A_L
  • If A_{L-1} \neq A_{L+1}, deletion doesn’t change diff(A) at all, no matter what the value of A_L is.

So, deleting A_L either reduces diff(A) by 2, or leaves it the same.
The exact same analysis can be applied to the insertion step to see that insertion either increases diff(A) by 2 or doesn’t change it.

Thus, the only way to increase diff(A) is for the deletion step to not change it, and the insertion step to increase it by 2. Ergo, the only possible increase is +2.

With this observation, the solution is fairly simple:

  • Let x be the initial value of diff(A).
    • x can be easily computed in \mathcal{O}(N).
  • Let y be the maximum possible value of diff(A)
    • y can also be computed in \mathcal{O}(N). For diff(A) to be maximum, we would like 0's and 1's to alternate as much as possible. Upon constructing a string like this, it can be seen that y = 2\cdot \min(c_0, c_1), where c_i is the count of i in A. Alternately, you can construct this alternating string and directly compute its difference value in \mathcal{O}(N).
  • The number of moves that can be made is then always exactly \frac{y-x}{2}.
  • If this value is odd, Alice wins. Otherwise, Bob wins.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (C++)
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
int T,n;
int c[N],cnt[2];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&c[i]);
		cnt[0]=cnt[1]=0;
		if(c[1]==c[n]) cnt[c[1]]++;
		for(int i=1;i<n;i++) if(c[i]==c[i+1]) cnt[c[i]]++;
		printf("%s\n",(min(cnt[0],cnt[1])&1)?"Alice":"Bob");
	}
	
	return 0;
}
Tester's code (C++)
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int a[n];
        for(int i = 0; i < n; i++) cin >> a[i];
        int c[2] = {0, 0};
        for(int i = 0; i < n; i++) c[a[i]]++;
        if(c[0] > c[1]) {
            for(int i = 0; i < n; i++) a[i] = !a[i];
            swap(c[0], c[1]);
        }
        int ans = c[0]*2;
        for(int i = 0; i < n; i++) {
            if(a[i] != a[(i + 1)%n]) ans--;
        }
        ans /= 2;
        ans &= 1;
        if(ans) cout << "Alice\n";
        else cout << "Bob\n";
    }
	return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    cur = 0
    for i in range(n):
        cur += a[i] != a[(i+1)%n]
    cur //= 2
    mx = min(a.count(0), a.count(1))
    print('bob' if cur%2 == mx%2 else 'alice')
3 Likes

I know it takes a lot of effort to set a problem, but I hate this problem :frowning:

15 Likes

I can understand your pain :sleepy:

3 Likes

someone please tell me, where can i get the video editorials of the problems

can anyone please tell the different approach of this problem ?

Yes, Efforts to set the problem are praised. But In 3hr contest who will analyse this much on the 4th problem itself. Also I don’t see any particular algorithm to solve this problem.
Preparing test cases and analysing to this level, took much time.

BTW, @iceknight1093 has provided the nice editorial to understand the logic.

lol, go checkout codeforces, even 2nd or 3rd problems are much harder and observational than this in a 2hr contest

Was so close to getting it correct. I somehow thought that the sequence of binary numbers should also matter, and was confused on that prospect. But good to know I learnt something.

1 Like

Can u provide the link?

11000->10001->01001->01010
Alice bob Alice
Hence Alice Wins. but according to the editorial Bob is winning.
Am i wrong for this case?

optimally means the player wants to win, so Alice can win if she plays like above otherwise she can’t win.

just ct the number of pairs of zero’s and one’s in the circular array then if(min( zero, one)&1)Alice; else Bob my solution

2 Likes

11000 \to 10001 is not a valid move since diff(11000) = 2 = diff(10001).

Similarly 01001 \to 01010 is not a valid move.

Edit: Also, the answer for 11000 is indeed Alice because only one move can be made, which is also what the editorial’s solution gives.

got that. i missed that front and last elements are also considered as adjacent elements.

PS: thanks for the clarification.

iceknight1093 please explain sample test cases

can u tell me where i can find text editorials code

The sample cases are explained in the statement.

do check the editorial of the problem.