CHEFGM - Editorial

@shaleen if the test cases are wrong or if their is any missing assertion with the problem statement than it’s purely not the participant’s problem. I was thinking that i was wrong, even I created more than 400 test cases of my own, but as we all have noticed a large group of submission are giving WA on very simple test cases. All the solutions must be rejudged.

I don’t think the solutions can be rejudged now because many of the users whose solutions are failing would have been able to correct their code if their solutions were judged WA. This is the problem setter’s mistake and nothing can be done about this now. This is actually a grave issue as it seems there is one problem in every month’s contest which has some missing test cases(remember KAMEHAMEHA).

@sikander_nsit In that case,let all WA submissions must be rejudged because as you said we cannot do anything after the contest for successful submissions which I also consider ok, but by rejudging the WA solutions with Correct Test Files, will reward with a fruit of green tick for their work which they did for the rest of the contest. I consider that if you are making a jugdement on the basis of the thing that now the contest is finished,then I can also say that ‘If I had known that a Wrong submission will give me a Correct Answer I would have done the same, but Alas the contest is finished.’

The present test files are not wrong but merely missing some test cases. So any solution which got WA during the contest will still be judged WA after rejudging. Your second point is valid generally but in this particular problem, the missing test case is not such as to prevent someone from submitting because their solution would have failed on the missing case but otherwise were correct. Only adding a single statement(std::unique) to the failing solution will make them correct.

According to question “all the numbers which are greater than or equal to chosen number will be removed from that pile”. Clearly saying that the number will be removed from that pile only ! So, ODD will be correct answer !

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

Grundy Theorem is applicable to only impartial games. This game is partial.

@devanshug I agree with your say…But rejudging the problem during the contest would have been a solution to it…Rejudging after the contest would not give a second chance to those who got AC initially…As the change in code is not a major one(just removing the repeated entries from each pile)…almost all would have corrected it during the contest.

@sikander_nsit how did you manage to submit this solution

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

@ 8 PM 11-11-13… ??
i cant figure out

There must be some bug…I m seeing 10-11-13 only.

CodeChef submission 2974228 (C++ 4.3.2) plaintext list. Status: AC, problem CHEFGM, contest NOV13. By sikander_nsit (sikander_nsit), 2013-11-10 20:27:57.

my version shows yesterday… don’t knw wat it is…

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.

You are printing the value of “add” at several places.

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??

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??

//