CHEFGM - Editorial

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:Hackenbush - general - CodeChef Discuss. 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.

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