Saturday, May 26, 2018

An unpublished week

The May 7 - May 13 week was the time for the first regional event of TopCoder Open 2018 in Warsaw. The problems and results seem to be unavailable on the TopCoder website, but you can read the recap here.

On Sunday of the same week the 2017-18 season of the Open Cup was wrapped up with the Grand Prix of Bashkortostan (results with Open Cup login, top 5 on the left). The overall season standings are not yet available, but there's no doubt about the first place of team Past Glory. In this round they have reiterated how huge the gap between them and the rest of the field really is, solving all problems from first attempt in 2 hours and 24 minutes, and having almost half the penalty time of the second-placed team. Huge congratulations!

Problem I in this round was relatively standard, and yet there was a lot of room for coming up with a solution that is easy to implement, as the constraints were relatively low. You are given the coordinates of the vertices of a convex polyhedron in three-dimensional space. You need to determine the horizontal plane that separates the polyhedron's volume 1:9. The number of vertices is at most 100. How would you implement this?

Thanks for reading, and check back for more!

Friday, May 25, 2018

A prefix xor week

The Apr 30 - May 6 week was about early qualification rounds for the major tournaments. TopCoder Open 2018 Round 1B took place on Thursday (problems, results, top 5 on the left, parallel round results, analysis). The medium problem provided ample challenge opportunities, and Michael_Levin has capitalized on those and earned the top spot with quite some margin — congratulations!

In the parallel round, kotamanegi was able to find even more challenges, and thus earned the top spot in the all-time high score list — congratulations as well :)

Google Code Jam 2018 Round 1C followed on Saturday (problems, results, top 5 on the left, analysis). The somewhat unusual interactive second problem did not delay Eryx much, as he finished the round in just over 35 minutes (8 seconds faster than austrin in 3rd place). Well done!

In my previous summary, I have mentioned a cute AtCoder problem: you are given a tree with 200000 vertices, each containing a number, either 0 or 1. We need to put all its vertices in some order in such a way that each vertex except the root appears to the right of its parent. We will then write out a sequence of 0s and 1s corresponding to numbers in the vertices in this order. What is the minimum possible number of inversions in this sequence? An inversion is a pair of positions such that the number in the left position is 1, and the number in the right position is 0.

The key idea that is widely applicable in this type of problems is called the exchange argument. Suppose we have some way to put the vertices in order, which results in some sequences of 1s and 0s. Let's consider two consecutive blocks of numbers in the resulting sequence, for example one block contains a 1s and b 0s, and the following block contains c 1s and d 0s. What happens to the number of inversions if we swap those blocks? It will change by cb-ad. Thus in an optimal sequence for every pair of consecutive blocks that are swappable (with respect to the parent-child constraint) we must have cb-ad>=0, which we can rewrite as c/d-a/b>=0.

Now suppose we have identified the optimal sequence for all children of some vertex, and want to find the optimal sequence for the vertex itself. The number for this vertex needs to go first, and then we need to interleave the sequences for the children somehow. In theory we could also reorder the optimal sequences for the children, but intuitively it is not necessary, and it will become clearer after we complete the solution.

Interleaving the sequences for the children can be viewed as splitting each child sequence into blocks, and then interleaving those blocks. From the exchange argument above, we need to take the block with the lowest fraction of 1s every time (lowest value of a/b).

There are many ways to split each child sequence into blocks, but we can notice that the first block must be at least the prefix p with the lowest fraction of 1s: in case we take a smaller prefix, the remaining part of p has an even lower fraction of 1s, and thus by the exchange argument above we'll be able to drag it to the beginning and improve the solution.

By applying the same argument repeatedly, we arrive at the following solution: each child sequence is split into blocks by taking the prefix with the lowest fraction of 1s as the first block, then the prefix with the lowest fraction of 1s of the remaining sequence as the second block, and so on. It's not hard to see that the fractions of 1s in those blocks for one child sequence will be nondecreasing, so in order to interleave those blocks we just sort them by the fraction, and blocks within one sequence will keep the same order.

It is however too slow to split each child sequence into blocks for every vertex, as potentially each sequence has a linear number of blocks, so the overall algorithm would be quadratic. However, since we interleave the blocks in nondecreasing order of fraction, we can notice that the sequence of blocks for each vertex is obtained by interleaving the sequences for the children — we don't need to re-split it. Then we prepend either a 0 or a 1 in the beginning. If it's a 0, we can simply make it a separate block and we'll still get a nondecreasing sequence. If it's a 1, it will "eat" a few following blocks until our sequence becomes nondecreasing.

This leads to the following approach: for each vertex, we'll build a sequence of blocks, ordered by the fraction of 1s, stored as a balanced search tree or a priority queue. In order to build the sequence for a vertex, we need to merge the sequences from its children, and add a new block in the beginning corresponding to the value in the vertex, and then repeatedly merge that block with the next block while its fraction is higher. When merging, we apply another relatively standard trick and insert blocks from the smaller sequence into the larger sequence, which guarantees that each block would be inserted at most log(n) times, and thus overall running time would be O(n*log2(n)).

I derive additional pleasure from the fact that while building this solution, we have essentially understood the mechanics of the problem in great detail: while initially we had a great deal of freedom in writing out the sequence, and it was not clear why we can even find the optimal sequence in polynomial time, now we realize that we just interleave blocks and merge them.

I have also mentioned a Codeforces problem: you are given 100000 numbers ai, each up to 260. You need to put them in such order that the xors of all prefixes of the resulting sequence form a strictly increasing sequence themselves.

The solution to this problem is quite the opposite to the previous one: instead of building a detailed understanding, we come up with an argument that works somewhat magically. It is not hard to prove that the solution works, but it keeps looking unexpected and magical.

Let's look at the highest bit set in at least one of ai's. Suppose it is set in some subset of numbers. Then the prefix xors will have 0 in this bit before the first such number, 1 in this bit after the first such number but before the second such number, 0 in this bit after the second such number, and so on. Since the resulting sequence must be non-decreasing, we must actually have exactly one such number. Let's start forming our resulting sequence by putting just this number there. Now we have two parts of the sequence, before this number and after it (including the number itself), which are somewhat independent: no matter which numbers go to the before part, its xor has 0 in the highest bit, and after xoring in our number the highest bit becomes 1, so we're guaranteed to have a strict increase on the boundary of the parts.

Now let's look at the next highest bit set in at least one of the remaining ai's, and look at the numbers where this bit is set. Just as before, the prefix xors will have 0 in this bit before the first such number, 1 in this bit after the first such number but before the second such number, 0 in this bit after the second such number, and so on. The only difference is that the set of numbers with this bit set might include the number that we already have in the sequence. If this is the case, then even though our bit will change from 1 to 0, we'd still have an increasing sequence, since a higher bit will change from 0 to 1 at the same point. So in case the already placed number has 1 in our bit, we can add two numbers with our bit as the highest bit: one in the beginning, and one after the already placed number. And in case the already placed number has 0 in our bit, we can add at most one number with our bit as the highest bit. Once again, after doing that, our sequence is guaranteed to be increasing at the boundaries of already placed numbers no matter what we insert between them.

A general step of our algorithm looks like this: we already have all numbers with highest bit higher than x placed, and want to place the numbers where the highest bit is x. We insert one such number in the beginning, and one after each already placed number where bit x is set, going from left to right, until we have no more numbers where the highest bit is x. If we run out of places before we run out of such numbers, there's no solution.

Note that the solution works just barely: for example, we can't put the new numbers after any subset of already placed numbers where bit x is set: we must go from left to right instead, to guarantee that the prefix xor does not have bit x set at each insertion point.  That's why I can't get rid of the feeling that this solution works almost by accident.

Thanks for reading, and check back for more!

Monday, May 14, 2018

A uniform combination week

Most teams have returned home from Beijing by the end of the Apr 23 - Apr 29 week, and the other contests returned in full swing. AtCoder Grand Contest 023 took place on Saturday (problems, results, top 5 on the left, analysis). The round was won by none other than the newly minted World Champion cospleermusora (also known as V--o_o--V and overtroll). yutaka1999 was also able to solve all problems, but required 30 more minutes to do so. Congratulations to both!

Problem F was very cute. You are given a tree with 200000 vertices, each containing a number, either 0 or 1. We need to put all its vertices in some order in such a way each vertex except the root appears to the right of its parent. We will then write out a sequence of 0s and 1s corresponding to numbers in the vertices in this order. What is the minimum possible number of inversions in this sequence? An inversion is a pair of positions such that the number in the left position is 1, and the number in the right position is 0.

Maybe I enjoyed this problem because I have set a problem in the past which involved the same strategy for producing a string from a tree.

VK Cup 2018 Round 3 happened on Sunday (problems, results, top 5 on the left, parallel round resultsanalysis). The ICPC champions, this time two of them, kept with their champion-y ways and solved two more problems than everybody else. Unbelievable!

I found problem C exceedingly beautiful. You are given 100000 numbers up to 260. You need to put them in such order that the xors of all prefixes of the resulting sequence form a strictly increasing sequence themselves.

Right after the Codeforces round ended, Google ran Code Jam 2018 Round 1B (problems, results, top 5 on the left, analysis). overtroll has continued his impressive form (see above) with another victory, this time with a healthy margin of 12 minutes. Well done!

In my previous summary, I have mentioned a World Finals problem: there are n people, each starting with 1 gem. The following operation is repeated d times: take one of the gems uniformly at random, and split it into two gems (so the person holding it will have one more gem). After doing all that we order all people by the number of gems they have in decreasing order, and add up the number of gems of the first r people in that order. What is the expected value of that sum? n and d are at most 500.

The first part of the solution is understanding the sequence generation process. At the first sight, it looks rather complicated, with the probability to get a new gem for each person changing along the way. However, let's look at the process from the following angle: let's put all gems for all people in one sequence, and every time a gem is divided we'll insert a new gem to the right of it. We'll also distinguish the original gems — the ones people start with — from the newly generated ones.

We start by having n original gems, and we can notice now that at each step we simply insert a new gem into a position in our sequence that is picked uniformly at random, except from the position before the first original gem which is never used. This in turn makes it clear that the resulting sequence starts with an original gem, and then has a sequence of n-1 original gems and d new gems picked uniformly at random from all C(n-1+d,d) such sequences. Each person gets all gems from their original gem to the next original gem in this sequence.

A uniformly chosen combination is a well-known object which is easy to work with, which allows us to proceed with solving the problem using either dynamic programming or more combinatorics, as outlined in the semi-official analysis.

Thanks for reading, and check back around the next weekend for more!

Sunday, May 13, 2018

An alma mater week

The Sächsilüüte week started with Codeforces Round 475 (problems, results, top 5 on the left, analysis). Three contestants managed to solve all problems, but some were faster than the others :) In particular, V--o_o--V has finished after just 81 minutes, and thus won with a 500-point margin. Well done!

One of the main competitive programming events of the year, ACM ICPC 2018 World Finals took place on Thursday (problems, results, top 13 on the left, our screencast with commentary, official broadcast, analysis). The deciding events of the competition happened in the last few minutes, when the Moscow State University team managed to squeeze in a solution to roblem E with an extra log factor by changing the number of iterations in binary search and getting something like TLE-TLE-TLE-OK-WA-WA-WA from seven attempts with different values of the magic constant.

That OK might well turn out to be TLE or WA as well, but fortune favors the bold, and what essentially happened was that the Moscow State University team did great in using all their resources and creativity up to the last minute and got a well-deserved victory. Really happy for the team and for my alma mater to finally get the cup that I and many others could not deliver in the past :)

Big congratulations to all other medalists on the great result, too!

Problem D brought the most excitement for me in this problemset. There are n people, each starting with 1 gem. The following operation is repeated d times: take one of the gems uniformly at random, and split it into two gems (so the person holding it will have one more gem). After doing all that we order all people by the number of gems they have in decreasing order, and add up the number of gems of the first r people in that order. What is the expected value of that sum? n and d are at most 500.

I'm also really interested in hearing what do you think about our stream and about the official broadcasts, if you had a chance to check them out, and I'm sure the ICPCLive team is very interested as well. Please share your observations or ideas!

Finally, TopCoder Open 2018 Round 1A took place on Saturday (problems, results, top 5 on the left, analysis). With the problems quite a bit on the easy side, the challenge phase was instrumental in determining the winner — congratulations to Dembel on finding the +125 and the victory!

Thanks for reading, and check back for more!

Changes to commenting system

I've changed the commenting system in this blog from HyperComments (thanks to its authors for making it!) to built-in Blogger comments, because HyperComments is discontinuing free usage. In the past years Blogger has added support for threaded replies which was the main motivation for me to switch to HyperComments in the past, and using an external commenting system brought its own pains, so switching back to the default seems to be the logical thing to do.

Please tell if you encounter some issues with commenting using the new (old?) system!

One side effect is that all comments made through HyperComments are not visible now. I have an xml export of all of them, but it's not clear at this point how to import those back into the Blogger system. Please share ideas if you have them :)

A +300 week

The week before the ICPC World Finals featured two competitions, both on Saturday. First off, Google Code Jam 2018 Round 1A took place very early (problems, results, top 5 on the left, analysis). This was the first round under complete new rules, as the penalty time did not matter in the qualification. The optimal strategy, of course, stayed more or less the same — just solve all problems quickly and without bugs :) vepifanov has executed it really well, congratulations on the victory!

TopCoder SRM 733 followed later that day (problems, results, top 5 on the left, analysis). Kriii has really dominated the proceedings, spending a bit over 18 minutes on all three problems in total Compare that to a bit over 41 minutes that kuniavski needed, and he came in second! Amazing performance by Kriii.

This was the third SRM which doesn't list cgy4ever in its authors, marking the transition to misof as the new TopCoder problem coordinator. Congratulations to misof on the new role, looking forward to the next SRMs!

Thanks for reading this [short] post, check back soon for more!

Friday, May 11, 2018

An elimination week

The Apr 2 - Apr 8 week had a couple of competitions on the weekend. Codeforces Round 474 took place on Saturday (problems, results, top 5 on the left, analysis). Solving eight problems correctly in just over two hours is an amazing feat — OO0OOO00O0OOO0O00OOO0OO was on top of his game this time. Well done!

Yandex.Algorithm 2018 Round 3 on Sunday (problems with Yandex login, results, top 6 on the left, analysis) has completed the Elimination stage. Unlike the first two rounds, this time blind submissions were actually necessary for the victory — congratulations to Merkurev for pulling four of those off !

Here is the final Elimination stage scoreboard (top 5 on the left), with top 25 advancing to the finals held both online and in St Petersburg.

Also on Sunday, Open Cup 2017-18 continued its streak with the Grand Prix of Warsaw (results, top 5 on the left). SPb ITMO U 1 team demonstrated impressive form, solving all 11 problems at the moment when all other teams had at most 9. Three other teams got to 10 problems in the remaining time, but nobody could approach the first place. Congratulations to the ITMO 1 team!

Thanks for reading, and check back for more!