This problem beats me. I was trying to solve it since the match's day. Came to understand a lot of it, except the subproblem. Then I read the official explanation and thought I understood how to solve the problem, but I didn't. As soon as I found free time I gave it a serious try and found out that the subproblem in question I have just found out I solved in 2010 during a topcoder match. I guess I am getting worse...
b%a, a is inevitable Let us say our numbers are 0 < a <= b . We represent such a state as (a,b). (If b < a, then just swap them). The first thing to notice is that it is inevitable that we will
eventually reach the state equal to (b%a, a). One of the available steps actually does it. But it is also nice to notice that the other kind of allowed steps, to subtract from
b a power of
a not equal to 1,
will never change the result b'%a. This is because all
ak when (k != 0) are multiples of
a. So, if we have (b >= a
k) then (b % a) will always be equal to ( (b - a
k) % a ).
This is useful, because given a state (a,b), the number of different states reached by doing only (b % a, a) operations is quite small. (This is actually like an
Euclidean algorithm, which we know has few states even for pairs of large numbers).
Some recursion won't hurt.
We got a state (a,b), and we know it will eventually become (b%a, b). Let us assume that we are using our knowledge in the theory of impartial games: We want to know if the player to receive the state (a,b) will win or not and we already know, whether the smaller case (b%a, b) is a victorious game or not (We are using recursion).
If (b % a, b) is a losing state, then the player that got state (a,b) can already win: Simply do the b%=a, operation.
In the other case, we got quite a sub-problem. The player is not able to use the b%=a operation without losing. Now, imagine the current player did some subtraction operation that did not lead to state (b%a, b), the next player will not be able to use the (b%a%a, b%a) move without losing either. In this battle to avoid letting the other player get state (b%a, a), we will have both players using only subtraction operations.
Let us consider the total number of times we can subtract
a from
b before it becomes equal to (
b%
a). We can assume
b is not a multiple of
a, (because else (
b%
a = 0,
a) would be a losing state). Thus we have
c = (
b /
a) - The number of times we can subtract
a.
A subproblemWe can translate the previous subproblem to this version: We have a stack of
c "stones" and two players. Each player can take 1,
a,
a^2,
a^3, ... stones from the stack. The last player to remove stones from the stack before it becomes empty, will lose - The player that receives an empty stack wins.
(Removing one stone from the stack is the equivalent to subtracting
a from
b. Removing a stones is the equivalent of subtracting
a^2. Etc. And when the stack is empty, it is equivalent to reaching state (
b%
a,
a) which is a victory state).
At first I thought that we could somehow reduce this to
Nim. But it turns out that's not the best approach (although I think it is possible and the end result is exactly the same we will find).
Imagine for a second that
c is not very large. In fact, it is not larger than
a. This means that the only move we are allowed to do is to take a single stone. (We cannot take
a*
a stones or greater, and if we take
a stones, we lose). In this case, it is easy to see that the player will win if and only if
c is even.
That is simply because 1 is an odd number. In fact, we can extend the idea: Imagine
a was an odd number. Then every power of
a will also be an odd number. This means that each player can only take an odd amount of stones in each turns. Once again, the current player wins if and only if
c is even.
What to do when
a is even and
c is greater than
a?. That is a nice question. Please note that we already know the answers for smaller values of
c. Let us model our f(
c) that says if it is a winning state or not:
f(0) = 1 (The player who receives the state with 0 stones wins).
f(1) = 0
f(2) = 1
f(3) = 0 // Since the only legal move is to subtract 1, the results alternate unti:
...
f(a-1) = 0
f(a) = 1 (We are assuming a is even)
f(a+1) = 1
f(a+2) = 0
f(a+3) = 1
...
f(a+a-1) = 1
f(a+a) = 0
f(a+a+1) = 1
f(a+a+2) = 1
Yes, (a+1) is a winning state. We can simply remove a stones and we force the other player to receive state 1, which is a losing state.
(a+2) is not a winning state. If we remove a single stone, the other player receives (a+1) which is a winning state. If we take (a) stones, the other player receives state (2). Another winning state. (a+3), ... keep alternating until we reach f(a+a-1) which is a winning state (subtract a to reach (a-1), a losing state). f(a+a) is a losing state, subtract 1 to reach (a+a-1) or a to reach state (a). It becomes interesting in (a+a+2)'s case, in which once again it is necessary to subtract (a) and reach (a+2). Now note that for each (a + 2 <= c <= a+a+2), f(c) is equal to f(c-(a+1) ). With this it is enough to conclude that if the allowed moves were 1 and a, the results are cyclic every (a+1) steps. In fact, the result is equal to taking (c % (a+1)) - if (c % (a+1)) is even, you win, else you lose.
Finally, consider a value of c such that it is a losing state in our supposed variation in which only taking 1 or
a stones is allowed. This means that both f(c-1) and f(c-a) are winning states. Is it possible for f(c-a^k) (k > 1) to be a losing state? By induction, assume that the formula is valid for smaller states. So Since f(c - a) is a winning state and for contradiction purposes we assume that f(c - a^k) is a losing state then we have that the parities of the following two expressions must be
different:
1. (c - a) % (a + 1)
2. (c - a^k) % (a + 1)
BUT, a and a^k always have the same parity (for k >= 2). So this is a contradiction and we have demonstrated that the formula is correct.
The similar problem from an old SRM:
PotatoGame. I thank the blog at
http://d.hatena.ne.jp/komiyam/20120328/1332881255 for pointing it out.
The code
bool solve(long a, long b)
{
if (a > b) {
return solve(b, a);
}
if (a==0) {
return false;
}
bool next = solve(b % a, a);
if (! next) {
return true;
}
long c = (b / a);
if ( (a % 2 == 1) || (c <= a) ) {
return (c % 2 == 0);
} else {
return ( ( c%(a + 1) ) % 2 == 0);
}
}
inline void init(){}
int main()
{
init();
bool prev = false;
int T;
while( cin >> T) {
if (prev) {
cout << endl;
}
prev = true;
long a,b;
for (int i=0; i<T; i++) {
cin >> a >> b;
cout << (solve(a,b) ?"First": "Second") << endl;
}
}
return 0;
}
Once again, my explanation is humongous.
