SEAGM - Editorial

PROBLEM LINK:

Practice
Contest

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.

  1. Who will win if they play optimally.
  2. 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:

  1. If the gcd(S) = 1, then the state is losing. (According to question.)
  2. 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.

  1. 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.
  2. 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.

  1. If the g = 1, then the state is losing. (According to question.)
  2. 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

  1. 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

16 Likes

My solution is somewhat different.

This game will always be played with cards that are divisible by a prime number in common. For instance, we the cards 2, 6, 6, 9, 10, 17, 18, 34, 34, 50 we have the following games:

  • Game in which all the cards have 2: {2, 6, 6, 10, 18, 34, 34, 50}
  • Game in which all the cards have 3: {6, 6, 9, 18}
  • Game in which all the cards have 5: {10}
  • Game in which all the cards have 17: {17, 34, 34}

In this case the first player wins if he plays a game of 17. He can’t win in a game of 5 because the game of 5 can and will lead to a game of 2. Another thing we should notice is a player will always make a move that translates the game unless he absolutely wins that game. For the first player if he chooses 2 as the first card he’ll lose since the game of 2 has an even size and he won’t make the last valid move. But if he chooses 17 he’ll win because this game can’t be translated. If he chooses 34 the second player can translate this game to a game of 2 by playing other card besides 17 and 34 (among the valid ones).

Since a game will always be based on a prime number, a move that translates a game is a move in which a prime or more are eliminated. For instance if 18 is the first move we can translate this game into a game of 2 or a game of 3. To translate it into a game of 2 we have to eliminate the 3, for that we just have to choose 2. To translate it into a game of 3 we just have to choose 9 witch will eliminate the 2. Keeping this in mind we don’t have to keep the track of the numbers that were played, we just have to keep track of the most basic form of the gcd being played and the player. A player only wins if all the games of the primes contained in the gcd have a size that favors him. The first player wins in a game of even size while the second one wins in a game of odd size.

The most basic form as a gcd is simply the lowest divisor of a gcd which has all the primes the gcd has. For instance 18 (3x3x2) can be reduce to 6 (3x2), 4 (2x2) can be reduced to 2 and 100 (2x2x5x5) can be reduced to 10 (2x5). This can be accomplished by keeping one of each prime. In every move a player checks if the current game is already decided, if it only contains primes with even size games or odd size games. If it does, the outcome has been decided, if it doesn’t just try each a[i] that can reduce the gcd and loop until all the numbers have been checked or a winning position has been found. Note that if a[i] can reduce the gcd it means it wasn’t played yet.

public static int play(int player, int gcd) {
	int tempWinner = getWinner(gcd);
	
	if(tempWinner < 0) for(int i=0; i<N && tempWinner!=player; i++) {
		int nextGcd = gcd(A[i], gcd);
		if(nextGcd > 1 && nextGcd < gcd && play(player^1, nextGcd)==player) {
			tempWinner = player;
		}
	}
	
	if(tempWinner == -1) tempWinner = player ^ 1;
	
	return tempWinner;
}

The method getWinner returns 0 if the first player wins, 1 if the second one does and -1 if the game can go both ways. This method simply checks the game sizes of the prime numbers currently being played. Full solution.

2 Likes

I was thinking during the contest that if probability of winning of first player is >=0.50000 , then in optimal game , first player will win. On the other hand if probability of winning is <0.50000, then first player will lose in an optimal game.
Can you please reveal a case where it is not true??

Input:

2

6

5 45 34 2 28 46

8

93 81 30 54 63 86 46 57

Output:

0 0.6667

0 0.5571

Input:

1

3

2 1 1

Output:

1 0.3333

2 Likes

Here’s another solution for the second part. For formula in LaTeX, see http://codeforces.com/blog/entry/12279

Any game they play is a permutation of a[i], say perm[i] (let them play all n numbers, even someone already lose). Since they play uniformly randomly, the permutation is also chosen uniformly randomly from all n! permutations.

Let prob[k] = probability that gcd(perm[1], perm[2], … perm[k]) > 1.

If the game ends exactly on the k’th turn, that means gcd(perm[1], perm[2], …, perm[k]) = 1, but gcd(perm[1], perm[2], …, perm[k-1]) > 1. Therefore the probability is prob[k-1] - prob[k]. If prob[n + 1] is defined as 0, then k = n + 1 is also applied. Sereja wins if and only if the game ends on even number turns, so the probability is (prob[1] - prob[2]) + (prob[3] - prob[4]) + …

All that’s left is calculate prob[k]. Let g[k] = gcd(perm[1], perm[2], …, perm[k]), we can calculate separately the probability that g[k] is a multiple of p, where p is a prime, and add them up. By the inclusion-exclusion principle, we also have to subtract the probability that g[k] is a multiple of p1 * p2, where p1 and p2 are primes, and add back the probability that g[k] is a multiple of p1 * p2 * p3, where p1, p2 and p3 are primes. Fortunately, there is no number under 100 having 4 different prime factors.

Finally, to calculate the probability that g[k] is a multiple of m, say there are C numbers in a that are multiples of m. Note that perm[1], perm[2], …, perm[k] must all be multiples of m, so all chosen from these C numbers. The number of combination is C!/k!(C-k)! and the number of permutations is C!/k!(C-k)! * k! * (n-k)!. So the probability is C!/k!(C-k)! * k!(n-k)!/n! = (C choose k) / (n choose k).

A solution: http://www.codechef.com/viewsolution/3906540
The input is read into a map b, which maps each prime p to the number of its occurrence C. The code mentioned above is at the last 20 lines.

6 Likes

Can you share your submission please?

1 Like

In the editorialist soln , why we need to check explicitly if gcd of all numbers is greater than 1 except reducing the time ? If I don’t check it , it should be handled by the recursive function automatically. But I get WA when not checking this explicitly. WHY?

@tamimcsedu19, Hi, I did not understand your question, can you please explain your problem slightly more?

EDIT: Hi tamimcsedu19, please check editorialist solution, it will pass if you dont take total gcd > 1 as special case and let it compute in the dp itself.

PS. I am not able to add new comments, but I am able to post answers.

@tamimcsedu19 done

Question is , In my first submission , Why should I add this code ?
if (g > 1) { cout << n % 2 << " " << (n % 2) << ".0000" << endl; continue; } , why can’t DP handle it?

actually dp can handle that. You can see by testing editorialists solution by removing this condition.