Hmm…I believe, that the problem is OK. Is the testdata weak? Yes. Is author’s solution incorrect? Yes. Is the problem wrong? No. If the testdata was incorrect, or the problem was NP-hard, then would be wrong. The weakness of the testdata isn’t a reason to make this contest unrated.
Just my opinion.
http://www.codechef.com/viewsolution/3785929
this is one of my solutions which got WA, the reason why it was WA was because of the “r < MAXN” condition in the line 40.
I have checked with some more checks that when r = MAXN (in my code MAXN = 202), com[MAXN - 1][i] <= g && com[MAXN][i] <= g but by removing this check I got AC. Which means that com[MAXN-1][i] is not the maximum value which is less than or equal to g. Its hard to find this kind of bugs. I agree with you that the problem is not wrong as the input data is correct. But it is frustrating!
@kostya_by: @gennady.korotkevich’s solution is completely correct. He handles the C=1 case separately and only uses the binary search approach when C>=2. His upper bound in the binary search is 2000000. For the smallest possible value of C (C=2), the binomial coefficient C(2000000,2) is >= 10^12, which makes his solution correct in all cases.
It is guaranteed that if the player will play optimally it is possible to win the game.
This statement is incorrect, for C = 0 and G > 1 it’s not possible, but I didn’t realized from statement… I also somehow assumed, that the requested G is in triangle in described by constraints - 100 rows and 50 columns…
Ok…I agree that the problem is not wrong…but you don’t give a linear search problem and have the key present at the first position in every test case…The test cases should handle the boundary limits at least…
Ok, I tried using ideone, and it seems, that high boundary was chosen well, the worst case for C == 2 is 999999911790 - the result is 999998497578 + 1414212 so the second number is less than 2000000…
It’s clear to me now - calculation of nCr(7, 3) can be done as
7 * 6 * 5
---------
3 * 2 * 1
I knew that, but what I didn’t realize before is, that we can use this with integers, I thought that 7/3 have to return incorrect result.
But he is using different approach
7 * 6 * 5
---------
1 * 2 * 3
…and here it is clear, that when we want to divide by n-th number, we already multiplied n numbers, so no integer division problems here, brilliant 