Div. 1: 1000-1500-1500-1000-???

Div. 2: 500-500-1500-2000-2000

That's why I don't very like this contest. But, once again, problems were interesting, thanks to the author!

Now short editorial.

Problem A - Cableway (div. 2)

The only thing in this problem is to write expression for time of the arrival for final group of students of each color. This could be done with the following code:

Problem B - African crossword (div. 2)

Due to the small restrictions, the problem could be solved with the straightforward O(n*m*(n+m)) algo of finding for each symbol whether there is other such symbol in the corresponding row or column. More fast approach is to count for each symbol how many times it appears in any row/column, and do corresponding checks in O(1) instead.

Problem A (div. 1) / C (div. 2) - Robbery

Good problem, and I don't agree with scoring of 500 for div. 1, I think the optimal score for this problem is 1000. The idea is the following: if n is even, then the answer is 0. If n is odd, then the answer is min (mn, (m/(n/2+1))*k), where mn is the minimum number of diamonds in some odd cell i. Now let's explain this formula.

If n is even, then all cells may be divided into pairs, and sum in each pair should remain constant => sum in all cells should remain constant => Joe cannot steal anything!

If n is odd, suppose Joe managed to steal D diamonds before some check. Let's prove that he should rearrange diamonds in cells so that any odd cell now contains D diamonds less, and any even cell - D diamonds more. Why so? Consider any odd cell. Again, remaining cells could be divided into neighboring pairs (n/2 of them) such that sum in every pair should remain constant => if Joe has stolen D diamonds, cell that we consider (any odd cell) should contain D diamonds less after robbery! But this entails (since pairsums should remain constant) that even cells should contain D diamonds more now. So, thus we proved first part of the formula under min() - Joe cannot steal more diamond than there is at any odd cell. But this is not the only restriction. In each of the k turns he may perform not more than m operations. How to economize operations to steal more diamonds? Well, the minimum number of operations to steal 1 diamond is n/2+1 (try to think why), so in every turn Joe may steal not more than m/(n/2+1) diamonds, and since there are only k turns, we get second part of the formula under min() function at the beginning.

Problem B (div. 1) / D (div. 2) - Widget Library

Pretty straightforward realization. Things to remember are:

 - sizes of widgets can be as large as 100*2^30+

 - when evaluate sizes of widgets recursively, memorize answers that are already evaluated. Otherwise you will need up to 2^30+ operations to get answers

"Bad" tests are of the following type:

76

Widget a(100,100)

HBox b

b.pack(a)

b.pack(a)

HBox c

c.pack(b)

c.pack(b)

...

HBox z

z.pack(y)

z.pack(y)

Problem C (div. 1) / E (div. 2) - Chip Play

From test 1 it becomes clear that the game process is dependent on history, so any DP schemes will not work. So, we perform straightforward simulation: take every chip and go. But the following test shows that straightforward simulation can take O(n^3) time to finish:

1 5000

R(2500 times)L(2500 times)

Answer: 5000 2

To speed the process up, one can use linked lists to get next cell with chip in O(1). The more tricky and easy-to-write approach is in my solution. It fits in timelimit, unfortunately, I can't prove complexity easily: http://pastebin.com/3KB7s0Le

Problem D - Space mines (div. 1)

I can't understand why it's D. It's pretty straightforward, it's easy to write. The only thing to understand is that it cannot be the case when Death Star intersects some spike and doesn't intersect its endpoint. Why? Remember: radius the the Star is not less than radius of any mine, and length of each spike is at most 3/2 of radius of mine. Then show by yourself that the situation described above is improssible.

That's all! Now just find all times where Death Star touches mine surface or touches spike end and take minimum of those. Pretty easy (one quadratic equation), I think - on the level of problem A: http://pastebin.com/YCSAbju1

Problem E - Fire and Ice (div. 1)

Who can explain this to me?