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

2 Likes

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.

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

3 Likes

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

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

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.

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

2 Likes

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:

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!

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.

@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