 # TWEED - Editorial

Author: Alei Reyes
Editorialist: Praveen Dhinwa

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 is even and starting player is even):
print `even player won`
else
print `odd player won`

``````

### Tester’s Solutions:

2 Likes

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.

24 Likes

Pseudo code should be

``````if n == 1 and pile is even and starting player is even:

print even player won
else

print odd player won``````
1 Like

@ohmankur

1 Like

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.

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

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.

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

@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…

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
{
for(int j=0;j<T;j++)
{
int N= Integer.parseInt(st);
int[]s=new int[N];
for(int i=0;i<N;i++)
s[i]=Integer.parseInt(sb[i]);
if(N==1 && st=="Dee" && (s%2)==0)
System.out.println("Dee");
else
System.out.println("Dum");
}
}
}``````

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

i don’t know why my code is not submitting can you tell me please

#include<stdio.h>
main()
{
int i,j,k;
scanf("%d",&j);
while(j–)
{
int n;
char a;
scanf("%d",&n);
int b;
scanf("%s",a);
for(i=0;i<n;i++)
scanf("%d",b);
if(n==1&&a==‘e’&&b%2==0)
printf(“Dee\n”);
else printf(“Dum\n”);
}
}