CHEFGM - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

EASY-MEDIUM

PROBLEM:

2-player game played on k piles of integers where in each turn a player chooses one pile and a number in that pile; all numbers greater than or equal to the chosen number are deleted from the chosen pile. Before the game starts, player 1 will decide to choose either EVEN or ODD numbers throughout the game and the other choice goes to player 2. Both players take turns alternately and the player who can not make move loses. Find if it is possible for player 1 to always win the game by choosing EVEN or ODD.

QUICK EXPLANATION:

The problem is reducible to blue-red hackenbush where each pile is equivalent to a hackenbush stalk. Even and Odd numbers can be mapped to blue and red line segments in the original version of the game. The overall game value can be calculated as a sum of all the game values corresponding to each stalk.
Very good explanation of hackenbush game and calculating the game values can be found here

EXPLANATION:

Let’s assume if game is in favour of EVEN we’ll give it positive value and otherwise negative.
This means:

if(GameValue > 0 ) printf("EVEN\n");
else if(GameValue < 0 ) printf("ODD\n");
else printf("DON'T PLAY\n");

Let observe some simple cases:

Case 1: Only one pile containing {2} -> Since game is clearly in favor of EVEN, we can assign it value V

Case 2: Only one pile containing {3} -> we can assign it value -V

Case 3: Only one pile containing {2, 3} -> Chef can win this game by choosing EVEN so game is in favor of even(hence +ve value) but should we give this case value less than V? Let’s try to answer this question by comparing case 1 and case 3.

If chef has both piles {2}, {2, 3} and some more piles such that overall game is in favor of EVEN then pile {2, 3} is less desirable than pile {2}; because when chef is playing on some other more critical pile, second player has a “free” move to play on pile {2,3}. Lets give this pile a value of V/2

Now if we can ensure that the values we assign to the piles are such that their relative order is always consistent with their ability to turn the game in favor of EVEN or ODD, then we can calculate the overall game value as a sum of all values assigned to individual piles. [This means if 2 piles p1 and p2 both have smallest number EVEN but p1 has more possible moves for ODD than p2, then value assigned to p1 < p2 but it is +ve]

Now the only thing left in this problem is to determine how to calculate the value for any given pile. We can use this scheme to calculate value of each pile:

  • Until the parity changes for the first time, each number is worth +V or -V (depending on whether it is Even or Odd, respectively).
  • Once parity change occurs, each subsequent number (regardless of being Even or Odd), is worth half of the previous value, with a +/- corresponding to the parity

Lets take this pile for example {4, 8, 9, 11, 16}. Its value can be calculated as: +V +V -V/2 -V/4 +V/8 = 11V/8
See section 11.1 here to read more about this value calculation.

Algorithm to calculate GameValue:

GameValue = 0;
For each pile:
    Read the pile and sort
    v = Calculate the value as explained above
    GameValue += v

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here
Testers’ solution can be found here and here

2 Likes

author and tester solutions are not provided

1 Like

One important observation is that duplicate values in a pile are irrelevant as if a value is selected to be removed from the pile then all the values which are equal to it are ensured to be taken away from the pile!

So suppose we have a pile {4, 4, 9, 11, 16}

assume even to be B, odd to be R!

Converting it to a stalk we have BBRRB so its stalk value is +V +V -V/2 -V/4 +V/8 ----(i)

But according to me the stalk formed should be BRRB (as we only count one instance of 4)

so here the stalk value comes out to be BRRB = +V -V/2 -V/4 +V/8 (WHICH DIFFERS FROM (i) by V)

I want to know which one is correct!

p.s - Both approaches were giving AC, but I am not convinced that the first one is correct!

3 Likes

you are right…duplicate values are irrelevant. Even I am surprised you got AC for the first approach. The first approach has to be wrong. Compare your answers on this test case: 1 2 5 4 4 9 11 16 2 9 10
The first one will give “even” but the second will give “odd”. And obviously the correct answer is odd.

As pointed out by @v_akshay This case is missing from the test cases in CHEFGAME.
1 2 5 4 4 9 11 16 2 9 10
I am sure many AC solutions will fail on this test case.
I found one such solution on the first page itself.
http://www.codechef.com/viewsolution/2949873
This solution gives “even” while the correct answer is “odd”.

Whoever didn’t remove the duplicates from the piles is almost sure to get a wrong answer on this test case.

15 Likes

On searching a little more, I was surprised to see that almost all the solutions on the first page are failing on this test case.

I also found solutions which are giving wrong answer for such a simple test case.
1
2
3 3 3 3
2 2 4
Many accepted solutions are giving ODD for this test while the correct answer should be EVEN

6 Likes

Good Point !!!

@sikander_nsit, Correct observation!

1 Like

“After that, all the numbers which are greater than or equal to chosen number will be removed from that pile.”

I don’t think method of value calculation in editorial takes this into consideration. Either that or all numbers in the input are different. Or the test cases are simply wrong.

Until the parity changes for the first time, each number is worth +V or -V (depending on whether it is Even or Odd, respectively).
Once parity change occurs, each subsequent number (regardless of being Even or Odd), is worth half of the previous value, with a +/- corresponding to the parity.

I didn’t even see this constraint during the contest and my solution passed no problem (which is the same as the solution in editorial which isn’t correct).

For example in pile {1, 1, 1} a player who is playing ODD has three moves, when in reality he has only one move. (value is +V not +3V)

I assume most solutions (including the official) will fail on:

1

2

3 1 1 1

1 2

Output should be “DON’T PLAY” instead of ODD or EVEN.

In the question it is mentioned that “all the numbers which are greater than or equal to chosen number will be removed from that pile.”
I guess while making test cases, they only considered elimination of numbers greater than the current number and not equal to the current number.

1 Like

Correct answer to this case should actually be DON’T PLAY. We have two piles {3,3,3} and {2,4}. If you take ODD then the opponent will select 2 from second pile and you will lose. If you take EVEN and chose 2 then opponent will chose 3 from first pile and you will be left with nothing.

even is correct!!! select 4 1st!!!

@mayank2k11 correct answer is even. If you take 4 your opponent takes 3 and then you take 2.

may be you are correct.
But the example provided by you… the answer is ODD.
Please try.

The answer should be “don’t play” as if the player chooses odd he will have to remove all ones and then the opponent will win by removing 2 from the other pile. If the player chooses even then he will have to remove 2 and the opponent will win by removing all ones from the other pile.

1 Like

Updated links for Author’s and Tester’s solutions

Looks like the condition that pile contains only unique numbers got missed. I can see assert in Setter’s code that numbers are unique. I will let setter comment on this.

@shaleen did you intend to say that the pile contains “only unique numbers” ?

@kcahdog, yes! I just edited my comment…

//