PROBLEM LINK:
Author: Sergey Nagin
Tester: Sergey Kulik
Editorialist: Lalit Kundu
DIFFICULTY:
MEDIUM
PREREQUISITES:
dynamic programming, 2 player games, basic understanding of gcd.
PROBLEM:
Given n numbers a[1] to a[n], 2 player play a game alternately as follows. In the beginning of game, we have a number g = 0.
They chose one of the numbers in the array a which is not thrown out and replace g by gcd(g, a[i]). After that they throw a[i].
If at any time in the game g becomes 1, the person who made the value g of equal to 1 loses. If a person is not able to move, then also he loses.
There are two questions to answer.
- Who will win if they play optimally.
- What is probability of winning of first player if they play randomly.
QUICK EXPLANATION
We can do a dynamic programming with state (g, taken) : g = gcd of numbers thrown out. taken = number of elements thrown out.
For understanding the reasoning behind this, please view next section.
EXPLANATION:
Lemma 1:
Note that gcd(a[1], a[2], , a[n]) = gcd (gcd(a[1], a[2], a[n - 1]), a[n])).
Proof:
We can do a simple proof by using induction on n. Proof is left to reader for nice exercise.
Lemma 2
Assume all a[i]‘s are positive integers.
Let set S = {a[1], a[2], , a[n]}, Let S’ = {a[1], a[2], , a[n], a[n + 1]}.
Then gcd(S’) <= gcd(S).
More accurately gcd(S’) divides gcd(S).
Intuitively, let us say you have a set S containing some elements, if you are going to add more elements to set S, your gcd can never increase.
Proof
Note that if elements are not positive, then the above Lemma is not correct. A counter example: S = {0} and S’ = {0, 4}.
gcd (S’) = 4 whereas gcd(S) = 0.
The above calculation is based on following assumptions that gcd(0) = 0 and gcd(0, g) = g.
We can formally prove this Lemma by contradiction.
Let gcd(S’) = g’ and gcd(S) = g. g’ > g. But Then g’ will also be gcd be S (because S is subset of S’), hence g >= g’, which is a contradiction.
Note that we can apply this Lemma in our question. Initially value of g is 0. But after we throw out the first number our gcd becomes positive, after that it is always
going to remain positive. Hence we can use this Lemma.
Two Player Games optimally Condition
If from a current game position, all the moveable game positions are winning, then
current position is losing. If there is at least one losing moveable position,then current position is winning.
Slow Solution.
Now let us try to think about simplest dp solution, let S denote the set containing the the elements from a[1] to a[n] which are thrown out.
We dont need to store any other information as our dp state anything except set S. eg we dont need to store value of g, because we can compute
g by simply computing gcd of set S. (Use Lemma 1 for gcd computation of a set S).
Base Cases:
- If the gcd(S) = 1, then the state is losing. (According to question.)
- If the set is full, ie #S = n (#S denotes number of elements in set S), then we can not make a move. In other words, if all the numbers has been thrown out, it means that there are no more numbers
to play with. Hence the last person who has played this turn will lose because he wont be able to make any move.
Transitions
Now let us think about transitions of our dp solution.
Our transitions will be done by choosing the number a[i] from array a such that it is not included in the set of thrown numbers S and our new state
will be S’ = S + a[i]. Here + operation denotes adding of a[i] into set S.
Look at the pseudo code to get more understanding of what is stated above.
def winning(S):
win = false // denotes whether the current player is going to win or not.
if (gcd(S) == 1): // Base Case 1.
return true;
if #S == N: // Base Case 2
return false;
for i = 1 to N:
if a[i] is not in set S. // Transition.
S' = S + a[i]
if (!winning(S')) // 2 Player game Rule. If there is a losing move from our current state, player at current state will win.
win = true;
return win;
Note that we can memoize the above function by using concept of bitmask. Use these links to understand more about bitmask link 1 link 2.
Solving 2nd Part
For second part of the question, solution is very similar, Only difference is instead of playing optimally we are playing the game randomly.
This time our dynamic programming function (probWinning) will return a double denoting probability of winning the person with given state.
In the Base cases, probability of winning is very easy to find. In transitions, probability of winning will be (1 - probWinning(new State ie S’)).
If from the current state, we have x possible transitions, we will divide the sum of (1 - probWinning(new State ie S’)) by x. (This is due to condition that we
will make only 1 move and our move will be randomly from the possible set of moves). See pseudo code for more details.
def probWinning(S):
answer = 0.0 // denotes whether the current player is going to win or not.
if (gcd(S) == 1): // Base Case 1
return 1.0;
if #S == N: // Base Case 2.
return 0.0;
for i = 1 to N:
if a[i] is not in set S.
S' = S + a[i]
answer += probWinning(S');
answer /= (N - #S).
// Note that (N - #S) denotes possible number of moves from out state S.
return answer;
Complexity:
states: O(2^N). as they are represented by bitmask.
transition time: O(N)
Hence Complexity of our dp solution is O(2^N * N) which is way too slow for N = 100.
Fast Solution:
Now we are wondering how can we optimize the slow solution. Can we somehow get rid of not storing the entire set S as our dp state.
Now let us pay more attention to Lemma 2, we will see whether we are able to get something out of it or not.
As Lemma 2 says, that gcd(S’) divides gcd(S) too.
Can we use above this information somehow ?
Let us say that we store gcd of S (denote by g) as our state parameter, Can we somehow identify which of the elements were thrown out in all the previous steps before reaching the current
position of the game. If we can do so, then we are done, because we will have essentially all the information required about the game.
Here are the crucial points.
-
All the numbers thrown out are multiples of g.
This point is very easy to prove and it is too easy to prove that it is left for readers :P. -
If from current gcd g, you are going to throw away a[i]’ which are multiples of g, then your gcd wont change and will remain equal to g.
Again this fact is also too easy to prove :). Now how can we use these facts?
Now we know that if our one of the state parameter is g, then we know that all the numbers which are not multiples of g are not taken upto now. But what
about the numbers which are multiples of g, do we need to store all of them ?. Can’t we do by just storing their count. It turns out that we can :), because
all those numbers (multiples of g) can not change our gcd (use point 2) and hence their exact values of are not needed in the game, only thing needed is count of them :). Hence we will just maintain count of them.
So if we maintain dp state as isWinning(g, taken): where g is current gcd of elements thrown away. taken is number of elements thrown away.
Base Cases:
They will be similar to base cases of slower solution.
- If the g = 1, then the state is losing. (According to question.)
- If the set is full, (taken = n), then we can not make a move and our state is losing.
Transitions
Note that from a state (g, taken) we can do following transitions.
Let V denotes set containing elements in the array a whom g divides. (ie set of multiples of g in the array a)
There are two possibilities
- taken < #V : In this case, we can still an element from the set V, by taking this number we will go to state (g, taken + 1).
because by application of point 2, we know that gcd is not going to change (hence gcd = g). As we have taken this element we increase the
thrown away elements by 1 in new state, hence taken is increased by 1.
We will also try to take element a[i] which are not multiple of t, our new state will be isWinning(gcd(g, a[i]), taken + 1).
2. If taken = #V:
Then we can not take any multiple of g, now we can try to take element a[i] which are not multiple of t, our new state will be
isWinning(gcd(g, a[i]), taken + 1).
3. Other probability wont be there, because then it will be invalid state. We are only making moves to valid states. Hence this kind of states will be
unreachable.
Pseudo Code:
def isWinning (int g, int taken):
win = false;
// if all the numbers has been taken out, first player will lose.
// base cases.
if (taken == n):
res = 0;
if (g == 1):
win = true;
else:
// tot denotes number of multiples of g in the array a.
tot = 0;
for i = 1 to N:
if (__gcd(g, a[i]) == g):
tot++;
// if not all multiples of g are thrown out, it means that there are still multiples of g currently in the array a.
// we can use them in the game.
if (taken < tot):
// we have found a losing state, it means we are winning.
if (taken < tot && !isWinning(g, taken + 1)):
win = true;
// Now we will iterate over the numbers which are having gcd with g not equal to 1 (because we will lose in that case) and
// not equal to g (ie we wont consider the multiples of g) because we have already considered that case before.
for i = 1 to N:
if (a[i] % g != 0) {
if (!isWinning(__gcd(g, a[i]), taken + 1)):
win = true;
Complexity of our dp solution is O(N^3), have O(N^2) states and transition time is O(N), hence overall time complexity is O(N^3).
Solving Second part of the problem:
For solving the problem when both the player play randomly, we can use a similar dp algorithm.
Entire solution idea is similar to above, just the transition states will change. Instead of computing
who will be winner, you dp function will return the probability of winning of currently moving player. For transition from the current state, we can move to
new state, probability of winning will be (sum of (1.0 - probability of winning states) ) / (n - taken). As we can only make (n - taken) moves,
for computing probability of winning of current state, we have to divide by (n - taken) as all the newer state transitions are equally likely.
Please see editorialist’s well commented solution given at the end of the editorial. It also explains transition states clearly.
Let tot denotes number of multiples of g in the array a (ie tot = #V). Note that if taken < tot, we will try to take multiples of g, We know that there are
tot - taken multiples of g still remaining to chose, by chosing anyone of them with equal probability, we can make a transition to next state.
Pseudo Code:
def probWinning (int g, int taken):
res = 0.0;
// if all the numbers has been taken out, first player will lose.
// base cases.
if (taken == n):
res = 0;
if (g == 1):
res = 1.0;
else:
// tot denotes number of multiples of g in the array a.
tot = 0;
for i = 1 to N:
if (__gcd(g, a[i]) == g):
tot++;
if (taken < tot):
res += (1 - probWinning(g, taken + 1)) * (tot - taken);
for i = 1 to N:
if (a[i] % g != 0):
res += (1 - probWinning(gcd(g, a[i]), taken + 1));
res /= (N - taken);
Alternate Solution.
You can solve the problem if you consider what are the possible gcds just one step before the ending of the game(ie step before g became 1). Let S denote the set of all such possible gcds. It is easy to fact to prove that all elements in S are mutually co-prime.
For each possible g, make a list of all the a[i]'s such that a[i] is a multiple of g.
Now we will check for searching for the first number that we(first player) will throw. If for any possible first move, first player is going to win, then he is going to win the game by playing that number.
Now way of deciding the outcome of the game for given first player move.
Assume that player started with x, let there are some lists L[g_1], L[g_2] , , L[g_k] which contains x.
Now if all the size of lists of L[g_1], , L[g_k] is odd, then you know that first player is always going to win because the second player is forced to play from one of these given lists only and length of that list is odd. (When the second player the one of the list from L[g_1] to L[g_k], then he can not change the list once selected, hence both the players will be forced to play in that list only.)
If all the sizes of lists are even, then first player is going to lose if he starts his game from any element any of lists L[g_1] to L[g_k].
If assume there are both even and odd size lists, then you can easily prove that second player always force first player to play only in the even sized pile, hence first player will lose.
eg. a = {2, 3, 5, 10, 15}
3 -> 15, 3
5 -> 15, 10, 5
2 -> 2, 10
So there are 3 lists, first list has gcd = 3, second one = 5, third one = 2.
Note that if 1st player moves 15, then second player can force just play in first list and can win.
Same is the case with 10, but in case when 1st player moves 5, then second player is forced to play in that pile itself, hence he will win if starts his game with throwing 5.
So overall your solution goes like this
win = false
for i = 1 to N:
ok = true;
// because 1 is not in any list.
if (a[i] != 1):
for all possilbe gcds g such that a[i] is in their list:
if (size(list(g)) % 2 = 0)
ok = false;
if (ok):
win = true;
break;
In the case of randomly play, you have to count number of ways of getting final gcd g with how many of elements of list corresponding to g you are selecting. You can see reference solution of triveni
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon.
Author’s solution
Tester’s solution
Editorialist’s well commented solution