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

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

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

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

“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

Why can’t we simply treat each pile as a nim pile and calculate grundy number using DP. We can do this once for odd and once for even. Why will this not work ?

sorry to say this but i am not being able to understand this editorial,please somebody can explain it to me in easy manner.specifically talking about allotting of values to numbers

4 Likes

I think time limit is too strict for some languages.For example My Python code takes 10.249 secs to solve 1000 testcases with k = 100 and ni = 45 and nos in range(2147483648). My algorithm is *correct as i have taken help from editorial. Same algorithm in C gets AC while in Python it gets TLE. Time Limit should be relaxed for some languages.

In fact best C++ solution if coded to Python takes about 11 secs.
And just reading the input and sorting the arrays take about 6 secs.

*Edit : Incorrect - Handle duplicates

http://www.codechef.com/viewsolution/2980782

This is my solution after reading the editorial.Someone please point out where I am going wrong.This is giving correct answer for the sample cases.I can’t think of cases to determine the error.

all those who are not able to understand this may refer to this link:http://discuss.codechef.com/questions/29027/hackenbush. this question has been asked by me at this link

2 Likes

In the editorial in the case 3,pile having the value {2,3},we are considering that if the chef is busy considering the other stalks, than {2 ,3} stalk will give more turns to the apponent and thus the value of the {2 ,3} stalk would be less than +v,but if the chef choses the stalk than the apponent will have not have extra turns which were provided by the stalk,so in that case will the value of the stalk will be equal to +v??

author and tester solutions are not provided

1 Like

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.

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.

Good Point !!!

@sikander_nsit, Correct observation!

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.