RANDGAME - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Udit Sanghi
Tester: Teja Vardhan Reddy
Editorialist: Oleksandr Kulkov

DIFFICULTY:
EASY
PREREQUISITES:
game theory basics
PROBLEM:
Two players are playing following game. Initially they’re given integer N. On each turn if N is even, the current player must divide it by 2, otherwise the player must increase or decrease N by 1. Player who made N equal to 0 wins the game. You’re the first player, you have to win the game or declare it’s impossible.
EXPLANATION:
Note that if we may calculate function win(x) which is equal to 1 if first player wins and 0 otherwise then it’s easy for us to make a strategy. If win(N)=0 we simply say that we lose and go to the next game. Otherwise if N is even we divide it by 2 and if N is odd we make a move to N-1 or N+1 whichever gives win(N')=0. Very naive implementation of win(x) looks like this:

bool win(int x) {
	if(x == 0) {
		return false;
	} else if(x == 1) {
		return true;
	} else {
		if(x % 2 == 0) {
			return !win(x / 2);
		} else {
			return !win(x - 1) | !win(x + 1);
		}
	}
}

If you’ll look on values of win(x) for small x, you may notice that it’s equal to 1 when x is odd.

Let’s prove it by induction. It holds for x=1. Now if last two bits are 11, you should subtract 1 and you’ll get odd number in return from other player’s move. Otherwise if last two bits are 01, you should add 1 and again you’ll get odd number in return from other player’s move. But in both cases it will be smaller odd number, thus it will be winning due to induction assumption. Thus win(x) is actually depends only on parity of the number of trailing zeroes of x and may be calculated e.

ALTERNATIVE SOLUTION:
Turns out you may simply add memoization to win(x) function and it would be enough to get AC! It seems that number of states you’ll visit may be estimated as 2 \log_2 n but rigorous proof is left to reader as an exercise :stuck_out_tongue:
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

2 Likes

What is the meaning of this line???

!win(x - 1) | !win(x + 1) , this statement defines that for any odd value of x if any of win(x-1) or win(x+1) is a losing state then x is a winning state otherwise x is losing state.

Let’s understand it by example , suppose x is 3 as it is odd number it will call win(x-1) and win(x+1) both means win(2) and win(4) .( you can check manually 2 is a losing state whereas 4 is winning state ) so 2 will return false and 4 will return true . now (!win(2) | !win(4) ) result in ( true | false) = true so 3 is also a winning state .
you can also test the condition where both win(x-1) and win (x+1) is winning so (!true | ! true) - > ( false | false ) = false. and it will make x to losing state.

Hope it will help.