Problem Link: contest, practice
Difficulty: Simple
Pre-requisites: Combinatorics, Greedy
Problem:
We are given two integers G and R. Our task is to find the representation of G according to the following pattern: CRnR + CR-1nR-1 + … + CLnL, where L ≥ 0 and CRnR ≥ CR-1nR-1 ≥ … ≥ CLnL
Explanation:
Firstly, let’s generate Pascal’s triangle. The cell in the left top corner has coordinates (0, 0).
For better understanding, let’s assume that G equals to 15 and R equals to 3. Our starting cell has coordinates (4, 3) and marked green on the picture. As we see from the picture, one of the optimal solutions is to pick cells (5, 3), (3, 2) and (2, 1)(marked red). The sum of the values in this cells equals to 10 + 3 + 2 = 15 and the second condition(C53 ≥ C32 ≥ C21) holds as well.
OK, the example is clear. But how does the solution look like in general?
Quite surprisingly, but the following greedy approach will do quite fine in this problem:
While G is greater than 0, let’s subtract the largest number in the column R from it, then decrease R by 1 and repeat this algorithm again.
Here is a pseudocode, that shows the implementation of the algorithm described above.
CELLS = {}
while G > 0 do
begin
N = R
K = R
while C( N + 1, K ) <= G do
begin
N = N + 1
end
G = G - C( N, K )
add cell (N, K) to set CELLS
end
When the algorithm is done, in set CELLS we have the cells, which represent G according to the required pattern.
The total complexity is O(R * R) per testcase.
Some notes from the author:
- Take care to use 64 bit integer to calculate G and values in Pascal’s triangle.
- The greedy algorithm comes from Kruskal Katona theorem.
- The row given in input is not required for solving the problem.
UPD!
The solution described above is not complete. I.e. in case R = 1 and G = 1012 the solution works in O(G) time, unfortunately.
BUT!
There’s nothing to be worry about. 
We can use the idea of binary search in order to improve the solution.
Formally, instead of the following part of code we can use a binary search.
while C( N + 1, K ) <= G do
begin
N = N + 1
end
Please, check out the solution of gennady.korotkevich.
I’m deeply sorry for that terrible situation around this problem. We should have pointed this pitfall out during the preparation stage, not now. I just hope that you’ve enjoyed the contest despite of this terrible mistake.
Setter’s Solution: link
Tester’s Solution: link
