BICO - Editorial

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. :slight_smile: 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

3 Likes

Is there any other approach to solve this question except the Greedy approach? The greedy approach is highly non intuitive!

5 Likes

If this is the solution, the problem statement was misleading and wrong.Its nowhere mentioned in the problem that we have to choose a row between 1 and R ( its an infinite matrix and so we can choose any row in a given column)
And so an input like
1 1 1000000000000
is perfectly correct to which the answer should be
1
1000000000000
However, the given approach will obviously fail to give the above answer.
I developed an algorithm which would give correct answer in all cases (using binary search) but it timed out.

Please make the problem statements totally correct from now on…

4 Likes

@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 :smiley:

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 :smiley:

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 == 1 at 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. :smiley: