A Gomel week

Last week started with the early morning TopCoder SRM 707 on Tuesday (problems, results, top 5 on the left). Nobody has managed to solve all three problems correctly - but not just because the hard problem was on the difficult side: the medium problem had an unusually low 19% success rate, with a deceptively simple statement but quite a few corner cases.

The winner Kriii also couldn't get the medium right, but has managed to get some compensation by successfully challenging two other medium solutions. Congratulations on the win!

Codeforces Round 395 took place on Thursday (problems, results, top 5 on the left, analysis). moejy0viiiiiv has solved everything with 24 minutes to spare, while nobody else was able to get all five. That's a very convincing victory!

AtCoder Grand Contest 010 on Saturday has gathered the top three rated contestants among others, and it was exactly those three contestants who occupied the top of the scoreboard (problems, results, top 5 on the left, analysis). Congratulations to Um_nik on being 8 minutes faster than everybody else!

The last problem turned out a bit easier than the organizers have expected. Two players are playing a game on a tree where each node has some amount of stones. There's also a chip in one of the vertices of the tree. They make moves in turn, and each move consists of removing one stone from the vertex where the chip is, and then moving the chip to an adjacent vertex. When there's no more stones in the vertex where the chip is, the player that needs to make the next move is unable to do so, and thus loses the game. How to determine who will win with optimal play?

And finally, OpenCup 2016-17 Grand Prix of Gomel resumed the Open Cup season on Sunday, featuring Gennady as the problemsetter (results, top 5 on the left). The reigning ACM ICPC world champions SPb SU Base were significantly faster than other teams, and thus found time to solve the hardest problem C in the last hour - great job!

Problem D has disguised a relatively standard idea behind an unusual but very natural background. n<=400 people have participated in a programming contest, and will receive x<=10⁹ roubles of prize money in total. You do not know what is the prize for each place, you only know that each prize is an integer amount of roubles, that they add up to x, and that the prize amounts are in non-increasing order as we go through the ranking list. Given a subset of places in the ranking list (for example the 1st place, the 5th place and the 8th place), what is the smallest possible total prize for those places?

In my previous summary, I have mentioned a Hacker Cup problem: you are given a sequence of n positive integers h_i, and a number k. You're allowed to do the following k times: take an integer, and decrease it by 1 (but it must remain positive). After you do this, we compute the maximum value of h_i+h_j+abs(i-j). How small can this maximum value be?

The first idea is to start with a binary search. Given a value m, can we achieve h_i+h_j+abs(i-j)<=m for all i not equal to j? Since abs(i-j)=max(i-j,j-i), this is equivalent to h_i+h_j+i-j<=m and h_i+h_j+j-i<=m. The second inequality is obtained from the first by swapping i and j, so they're equivalent and we can keep just one: h_i+h_j+i-j<=m. We can now rewrite it as (h_i+i)+(h_j-j)<=m.

Now, if we didn't have the constraint that i is not equal to j, we could define a=max(h_i+i), b=(h_j-j), and simply check if we can make a+b<=m. If we fix the value of a, then we know the (maximum value of) b, and thus know how much each height needs to be decreased, and thus can check if k decreases are enough. Of course we can't check all possible values of a this way, but we can notice that if we go through values of a in increasing order, the contribution of each h_i to the total required decrease will be piecewise-linear with at most 5 pieces, and thus we can add all those piecewise-linear curves together in O(nlogn) time.

Now, what to do with the additional constraint that i is not equal to j? It turns out that it doesn't matter in most cases. More specifically, for this constraint to matter both max(h_i+i) and max(h_j-j) must be achieved in the same point, and only in that point. In that case we have one h_i that is significantly bigger than all others, and thus decreasing this h_i will result in the answer decreasing as well. Because of this, we can always "transfer" one more decrease from any other number to that h_i without making the answer worse, unless all k decreases have been applied to it. And that means that in addition to the piecewise-linear sum mentioned above, it suffices to check just one more case: when all k decreases are applied to the maximum h_i.

Thanks for reading, and check back next week!