@priyanshu2501: @setter: I also tried a binary search approach in the last minutes after some WAs. The problem statement is seriously misleading.
2 Likes
My approach: “I have no idea what to do, but there are a lot of AC’d solutions, so I guess the dumbest greedy approach will work? Lol, it works.”
Sometimes, having others’ behaviour determine the solution can be invaluable 
Still, it’s even better if you know other contestants’ strong and weak points and are able to determine what the solution is likely not to be
3 Likes
Despite running out of time before getting AC I enjoyed attempting this problem, and have now solved it. I would argue that by drawing out a small version of the grid on paper and solving the given cases the greedy approach is intuitive. I don’t think I am an exceptional competitive programmer but I had the correct strategy and feel like with a little more time I would have definitely gotten it during the contest.
Can someone describe in more detail gennady’s solution?
There are two things unclear to me:
- he is handling case
C == 1at a very beginning, what happens when C is 2 - how the calculations of nCr is done in runtime? Can I generate the column in the table above without previous columns?What formula is used for that?
The editorials have been updated…but I guess the solutions should be rejudged according to the new test cases that incorporate the boundary cases… Even the best solution of @BICO is wrong according to the update…
I don’t think the statement was misleading. The only problem was that the test data was weak. It was given that the matrix is infinite. So it is clear that for any column C we can take any row>=C.
The proof for the greedy approach is also fairly simple. If the statement didn’t have the constraint that the no. of coins taken from subsequent columns should form a decreasing sequence, then the solution would be “take 1 from every column until you reach column 1. Then take the no. of coins needed from the first column, since the first column has every possible no. of coins available.” The greedy approach follows from this constraint.
Suppose C=7.
for C=7, the no. of coins available are: 1, 8, 36, 120, 330 …
for C=6, the no. of coins available are: 1, 7, 28, 84, 210 …
for C=5, the no. of coins available are: 1, 6, 21, 56, 126 …
for C=4, the no. of coins available are: 1, 5, 15, 35, 70 …
for C=3, the no. of coins available are: 1, 4, 10, 20, 35 …
for C=2, the no. of coins available are: 1, 3, 6, 10, 15 …
for C=1, the no. of coins available are: 1, 2, 3, 4, 5 …
for C=0, the no. of coins available are: 1, 1, 1, 1, 1 …
If G was 330, we could have directly taken 330 coins from 7th column.
If G was 329, and we take 120 coins from the 7th column, we need 209 more coins now.
We took 10C7 = 120 coins from the 7th column. Now we cannot take 10C6 = 210 coins from the 6th column because if that would have been the case then we could have taken
10C7 + 10C6 = 11C7 = 330 coins directly from the 7th column. Thus we have to take 9C6 = 84 coins from the 6th column which will always be less than 10C7.
Thus in this way we can collect any number of coins while satisfying this constraint for C>0.
Also see that when C>0, we will never actually need 0th column.
This pseudocode works in O(G). It also assumes that G and X are changed inside “add cell (X, Y) to CELLS”, which is… not really obvious.
Sorry, it was incorrect. Now it should work just fine.
Can you provide a rough sketch of the proof for greedy algorithm here?
Well, both setter’s and tester’s solutions don’t work when the test is “1
0 1 1000000000000”. Not to mention that links to them are relative, so they are just redirected to this editorial.
5 Likes
The problem statement was incomplete.It was nowhere mentioned that we have to choose a row between 1 and r…An input like the above mentioned and many others is perfectly correct and your algo fails in the case.
5 Likes
Hmm…I have to admit, that the solution is not really OK. Nevertheless, it’s possible to use a binary search for small R and this bruteforce otherwise. Will update the editorial soon. Thanks for pointing this out.
I didn’t assume that we have to choose a row between 1 and R, and got AC. So I don’t think that’s the case. But the statement was obfuscated by the remark about “optimal strategy” (which lacks meaning for a 1-player game) and the blocked cells. It could’ve just said “express G as sum of bin. coef. blablabla”.
1 Like
But what to do if the problem is itself wrongly written…
One cannot guess everything
2 Likes
I don’t think it should be unrated. It’s not a NP-hard problem or something like that. Moreover, a lot of contestants were able to solve the problem properly for any kind of input data.
The problem itself is wrong. The solutions that have been accepted will WA on giving a simple enough input…The problem should at least be removed from the rankings…
Yeah well, too bad in that case. Shit happens. We try things, and sometimes they actually work.
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.
1 Like
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.
3 Likes