PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
SIMPLE
PREREQUISITES:
PROBLEM:
Given integer N, Alice and Bob play the following game, with Alice moving first. The rules are as follows:
- Choose a positive integer y such that 2^y|N, and divide N by 2^y.
- If this is not possible, subtract 1 from N.
The player who can’t make a move loses. Determine the winner if both parties play optimally.
EXPLANATION:
Let w(x) be the winner of the game with starting value x, if Alice plays first and both players play optimally. Consider w(x)=1 if Alice wins and 0 otherwise.
Let us find a suitable recurrence relation for function w.
Hint 1
A simple idea would be to try all moves and determine if Alice wins in at least one of those possibilities. Can you visualise the recurrence equations?
Pseudocode
int w(int N){
if(N == 0) return 0;
// We invert the result because Bob plays the next move.
if(N%2 == 1) return !w(N-1);
bool canWin = false;
for(int i = 2; N%i == 0; i *= 2)
if(!w(N/i)) canWin = true;
return canWin;
}
This naive solution can be sped up with memoization, which is sufficient to AC the first two test cases.
Hint 2
I claim that, if x is positive and divisible by 4, then w(x)=1.
Solution
Let y be the largest non-negative integer such that 2^y | x. Then, there are 3 cases for y:
-
y=0 - The only move possible in this case is move two (subtracting 1 from x), so w(x)=1 only if w(x-1)=0 (we invert the answer since Bob plays the next move).
-
y=1 - The only move possible in this case is dividing by 2, so w(x)=1 only if w(x/2)=0.
-
y>1 - For this case, w(x) is always equal to 1, because
- if w(x/2^y)=0, Alice can divide x by 2^y and win, and
- if w(x/2^y)=1, Alice can divide x by 2^{y-1}, and Bob in the next move is forced to divide by 2 (see second point above), allowing Alice to play the next move on x/2^y and win.
The pseudocode is thus as follows:
int w(int N){
if(N == 0) return 0;
if(N%2 == 1) return !w(N-1); // case 1
if(N%4 != 0) return !w(N/2); // case 2
return 1; // case 3
}
It is easy to see that the algorithm iterates over each bit of N at most twice, which is efficient enough for the given constraints.
TIME COMPLEXITY:
In the worst case (N=2^i-1), we process each bit in the binary representation of N twice, making the time complexity
per test case, where d is the number of bits of N.
SOLUTIONS:
Editorialist’s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters