Wednesday, April 18, 2018

A second extremal week

The last week of March featured more contests from the regular platforms. First off, TopCoder SRM 732 took place very early on Friday (problems, results, top 5 on the left). Both the medium and the hard problem involved asymmetric games requiring quite some insight to solve, and thus only two contestants were able to solve each (top 4 in the table to the left). Congratulations to all four, and especially to pashka on the win!

Then AtCoder held its Grand Contest 022 on Saturday (problems, results, top 5 on the left, analysis). The contest had three relatively easy problems, and three very hard ones. Only a few contestants were able to solve one of the three (I couldn't solve any, for that matter), so it is extremely impressive that Um_nik got all three — huge congratulations on very well deserved victory!

Problem E was the most approachable of the three. Consider a string of 0s, 1s and ?s of odd length up to 300000. First, we need to replace each ? with a 0 or a 1. Then, we repeatedly do the following operation: take any 3 consecutive characters, and replace them with the most frequent character among them. For example, 001 is replaced with 0. In the end we end up with a string of length 1, and our goal is to get the string 1. How many ways are there to replace the ?s so that it's possible to get the 1 after all reductions?

And finally, Open Cup 2017-18 Grand Prix of Moscow on Sunday wrapped up the week, but its results have not yet been published.

In my previous summary, I have mentioned an Open Cup problem: you are given n points p1p2, ..., pn on the plane and q queries (n, q <= 100000). Each query is defined by two numbers a, b, and you need to print the size of the smallest square with sides parallel to coordinate axes that contains all points from a-th to b-th (from the list papa+1, ..., pb) except maybe one.

Assuming we forget about "except maybe one" part, we need to find the bounding box of a segment of points, which can be done by finding the leftmost, rightmost, topmost and bottom-most points using interval trees in O(n*log(n)).

Now we can notice that when the skipped point is not one of the four extremal points, then the bounding box does not change, so we need to check at most four possibilities for the skipped point. In order to be able to find extremal points after skipping one point, our interval trees will need hold two extremal points instead of one, but otherwise the solution stays the same.

Thanks for reading, and check back for more!

No comments:

Post a Comment