TWEED - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Alei Reyes
Tester: Hasan Jaddouh
Editorialist: Praveen Dhinwa

DIFFICULTY:

cakewalk

PREREQUISITES:

game theory, parity, understanding invariant

PROBLEM:

Two players play a game on n piles. Let us characterize the player into two categories even player and odd player. The even player selects a pile and remove some even number of coins from it. Similarly, odd player can only remove odd number of coins. The player who is not able to make a move loses. You have to tell who will win the game depending on who takes the first turn?

EXPLANATION:

Understand the simplest example
Let us check the smallest example n = 1.

If the pile contains odd number of coins

  • If odd player plays first, he will win.
  • If even player plays first, he will lose. It is due to the fact that he can’t take all the coins of the pile as the total number of coins in the pile are odd. So, the number of coins left after his move will always be odd. In the next turn, the odd player will remove the entire pile left and win the game.

So, odd player will win the game regardless of whether he plays first or second.

If the pile contains even number of coins

  • If even player plays first, he will win in the very first move.
  • If odd player plays first, he will win. He will remove all but one coins from the pile. As the pile contains even number of coins, he can do so. Now, the pile will contain only 1 coin, on which the even player won’t be able to make any move.

Let us make more observations

From the previous example, we have realized that if a pile contains odd number of coins, then the even player can’t make the number of coins in the pile to be even. In general, you can realize that for a even player it is impossible to change the parity of the number of coins of the pile. But, for an odd player, it is quite easy to change the parity.

This makes us to make the following important claim.
Claim : If there is a pile containing odd number of coins, then the odd player will always win regardless of whether he takes first turn or not.
Proof : It is impossible for even player to make last move on it, because he can’t change the parity of pile from odd to even in his move. Also, the odd player will also not make any move in this pile until the last. The odd player can make moves in the other remaining piles (whether they be even or odd), he can always make moves in those. Finally, if it is odd player’s turn, he will remove this entire pile. If, it is even player’s turn, he has no option other than to remove some even number of coins, after that pile will contain odd number of coins and in the next turn odd player will win by removing the entire pile.

Towards the full solution
Previous observation suggest that it is very important for the odd player to have some odd pile. If he has one such odd pile, he will win.

If the odd player moves first, then he can always make a pile odd. He will choose some even pile and remove 1 coin from it.
If the even player moves first, then if he can’t win in the first move, then he can never win, because now the turn of odd player comes and he will win the game. The even player can win in the first move, if and only if there is only one pile containing even number of coins.

Pseudo Code


if n == 1 and pile[1] is even and starting player is even):
   print `even player won`
else 
  print `odd player won`

Tester’s Solutions:

Setter’s solution
Tester’s solution

2 Likes
2

This definitely wasn’t Cakewalk. There are many ways to think, none of them anything like obvious. (Modified Grundy numbers? Do only the numbers of even/odd piles matter? - This is hard to check, since brute force is exponentially slow. Does the parity of their difference? Which one is larger? Should the piles be split in some way, e.g. into pairs and single pieces? Greedy? Clever backtracking, since the bounds are rather small? Is this supposed to be the easiest problem or the hardest? etc.)

I authored a similar problem (an ad-hoc game, TWONIM) and it had a similar solving time, but the inteded difficulty was much larger because ad-hoc.

19 Likes
3

Pseudo code should be

if n == 1 and pile[1] is even and starting player is even:

print even player won
else 

print odd player won
1 Like
4

@ohmankur
Below is the link for your code that gives AC.

1 Like
5

what if there is a pile with odd number of coins say 3, If odd moves first and picks up one of the coins then Even can win picking up the left two. Isn’t this possible? Or is it necessary here for the odd player to make a wining move in the first move itself?

I don’t get it please explain.

6

they both played optimally . . so whenever odd plays he left 1 coin for the even …so that even can never win the game…

7

i thought another way to solve this, if the xor opertion of piles gives non zero value, then person who started the game, will win, was i right? I read about this on geeksforgeeks.

8

1 2 DUM 3 2 i think this editorial will not pass this test case

9

@rupali_patel

For each heap, the value are all the same… It was stated within the problem… Your test case isn’t valid… Just clarifying…

10

Can someone tell me why i am not getting the desired output

import java.io.*;
import java.lang.*;
import java.util.*;
 
import javax.net.ssl.ExtendedSSLSession;
 
class universe
{
    public static void main(String args[])throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        for(int j=0;j<T;j++)
        {
            String[] st=br.readLine().split(" ");
           int N= Integer.parseInt(st[0]);
           int[]s=new int[N];
           String[] sb= br.readLine().split(" ");
           for(int i=0;i<N;i++)
           s[i]=Integer.parseInt(sb[i]);
           if(N==1 && st[1]=="Dee" && (s[0]%2)==0)
           System.out.println("Dee");
           else
           System.out.println("Dum");
        }
    }
}
11

You have written st[1]==“Dee” . This is an incorrect way to compare Strings in Java. Use the equals() method instead. That will give the correct answer.