Saturday, February 11, 2017

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<=109 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 hi, 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 hi+hj+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 hi+hj+abs(i-j)<=m for all i not equal to j? Since abs(i-j)=max(i-j,j-i), this is equivalent to hi+hj+i-j<=m and hi+hj+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: hi+hj+i-j<=m. We can now rewrite it as (hi+i)+(hj-j)<=m.

Now, if we didn't have the constraint that i is not equal to j, we could define a=max(hi+i), b=(hj-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 hi 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(hi+i) and max(hj-j) must be achieved in the same point, and only in that point. In that case we have one hi that is significantly bigger than all others, and thus decreasing this hi will result in the answer decreasing as well. Because of this, we can always "transfer" one more decrease from any other number to that hi 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 hi.

Thanks for reading, and check back next week!

No comments:

Post a Comment