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…
Can someone describe in more detail gennady’s solution?
There are two things unclear to me:
C == 1 at a very beginning, what happens when C is 2Ok, 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…
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.
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 