A discrete logarithm week

For the third week in a row, this week's Saturday was about qualifying for TopCoder Open 2016. This time the final two lucky contestants were chosen via the Wildcard Round (problems, results, top 5 on the left, parallel round results, my screencast). In the official round, nobody solved 1000, and in both rounds there were only a few solutions to 500. Both were solvable, but together probably just outside the 1 hour and 15 minutes timeframe. xudyh and tourist were the only two official round contestants to get two problems correctly, and thus qualified for the onsite without any close calls. Congratulations!

The current set of 10 finalists (including the changes I'm aware of because of inability to travel) is: Petr, HellKitsune, knightL, eatmore, rng_58, Um_nik, scott_wu, Enot, xudyh, tourist. Please tell if somebody else from this list is not coming!

The reason nobody got the 1000 in the official round is probably twofold: first, the problem statement is long and a bit convoluted. Then, since none of the top scorers went to the 1000 from the start, there were no successful solutions on the scoreboard, which led people to believe that the problem was harder than it really was.

After dissecting the problem statement, it boiled down to this classical algebra task: finding roots modulo a prime. More precisely, given three integers a, k and p, where p is a prime (more precisely, 10⁹+7), find any integer b such that b^k=a (mod p), or report that there isn't any. You also need to do it relatively fast, as one needs to solve this equation 300 times for different values of a (but k and p stay the same). Do you know how to do it?

Thanks for reading, and check back next week for the solution!

A regional week

On Saturday, September 3, TopCoder held its TCO16 Russia event in St Petersburg (problems, results, top 5 on the left, official blog, my screencast). For the second year in a row, those provide an opportunity for people who don't qualify for the onsite to get together, but this year one could also qualify for a special Wildcard round from the regional event, in order to compete for 2 extra spots in the onsite. That resulted in much more serious competition, but the social element was still there, and I've enjoyed meeting many of my old and new friends in St Petersburg - thanks a lot to TopCoder for organizing the regionals!

On the following Sunday, AtCoder Grand Contest 004 took place (problems, results, top 5 on the left, analysis). semiexp has won his second Grand Contest, and reclaimed the top spot in the rankings - congratulations!

Thanks for reading this super short summary, and check back soon for this week's contests! Please remember that I'm happy to answer your questions in comments to this or any other summary.

A Reichenbach week

The fourth August week has marked the start of the Petrozavodsk training camp, and with it came newly traditional AIM Tech Round 3 (problems, results, top 5 on the left). Quite fittingly, the winner was present in Petrozavodsk - congratulations Um_nik!

On Saturday evening TopCoder Open 2016 Round 3B has selected four more contestants for the onsite round in Washington (problems, results, top 5 on the left). The 1000-pointer did not give this time, and thus the key was in solving the 500-pointer fast. The challenge phase did not affect the top four - congratulations to rng_58, Um_nik, scott_wu and Enot on qualifying!

In my previous summary, I've mentioned an interesting AtCoder problem. Initially, one was given a sequence of length n. Then m transformations were applied. After the i-th transformation the new length of the sequence became a_i. If the new length was shorter than the current length, the sequence was simply truncated. If the new length was longer than the current length, then we repeated the current sequence periodically to get to the new length. Given n, m, and the numbers a_i, one needed to find how many times each element of the original sequence appears in the final sequence. n and m are up to 10⁵, a_i are up to 10¹⁸.

The first step in solving this problem is: if a certain value a_i is smaller than or equal to the previous value a_i-1, then the previous value can be removed, as we will truncate the result of (i-1)-st operation to a_i numbers anyway. After repeating this several times, we arrive at a strictly increasing sequence a_i, which effectively contains those numbers from the original sequence that are smaller than all following numbers.

The next idea is to look at this problem from the end: instead of unfolding the short sequence into a long one, we will fold the long one. We start with one long sequence of length a_m. What does it fold to? Let's divide a_m by a_m-1, and get the quotient x and the remainder y. Then we get x copies of the sequence at step m-1, and one more copy of its prefix of length y. What will happen to this prefix of length y later? It will stay unchanged until we reach some a_j that is less than y, after which it will again transform into several copies of a_j plus some smaller remainder. By continuing this process, we will have decomposed our initial long sequence a_m into a few copies of the sequences of length a_j where j is less than m, plus some prefix of the original sequence.

Now we can decompose the resulting sequences of length a_m-1 in the same way, then sequences of length a_m-2, remembering how many copies of each length we have, until we've left with just a collection of prefixes (with counts) of the original sequence, which allows us to compute the answer easily.

At first sight, it seems that we have a O(m²) solution since each length decomposes into some set of smaller lengths. However, we can note that the remainder y decreases at least twice in each step, so we have at most log(a_m) steps, and we can perform each step in O(log(m)) time by doing a binary search for the next suitable a_j. In total, that leads to a running time of O(n+m*log(m)*log(a_m)), where the O(n) part is for computing and printing the answer.

A beautiful fact is that, despite such fancy complexity, the solution itself is very simple and easy to code, as it only uses arrays as data structures, and simple binary search as the most advanced algorithm.

Thanks for reading, and check back soon for the next week's summary!

A squeezing week

The third August week featured TopCoder SRM 697 on Thursday (problems, results, top 5 on the left, analysis). I've wasted most of my time trying to solve the hard problem and couldn't squeeze my approach into the time limit, but matthew99a turned out to be better at squeezing - congratulations!

Later that week, AtCoder Grand Contest 003 has ended with a tiny 16-second margin between the first two places (problems, results, top 5 on the left, analysis).

Problem E "Sequential operations on Sequence" required a few ideas to get both the right asymptotic complexity, and an easy-to-code implementation. Initially, one was given a sequence of length n. Then m transformations were applied. After the i-th transformation the new length of the sequence became a_i. If the new length was shorter than the current length, the sequence was simply truncated. If the new length was longer than the current length, then we repeated the current sequence periodically to get to the new length. Given n, m, and the numbers a_i, one needed to find how many times each element of the original sequence appears in the final sequence. n and m are up to 10⁵, a_i are up to 10¹⁸.

Thanks for reading, and check back soon for the next week's summary!

A circular week

The second week of August was relatively calm, with just the early morning TopCoder SRM 696 on the agenda (problems, results, top 5 on the left). Swistakk was the only contestant to solve the hard problem correctly, but anta has earned his second SRM victory thanks to being the fastest on the medium problem. Great job!

In the previous week's summary, I have shared a very nice Code Jam problem: you are given two numbers n and r. There's a nxn grid of pillars, with a pillar of radius r centered in each point of the grid except the bottom-left corner. How many pillars are visible from the bottom-left corner?

Which seems to be a geometry problem at the first glance, turns out to be solely about number theory when it comes to the implementation. The first observation that leads us there is the fact that if we can see any point of a column, then we can see its center. To prove that, suppose the column at (x, y) obstructs some part of the view of the column at (a, b) including its center. The column at (a-x, b-y) is in a symmetric location, and thus also obstructs the view of the center of (a, b), but from the other side. As a result, the view of the entire column at (a, b) is obstructed. So instead of having to carefully track which part of a column is visible, we just need to check if its center is visible.

Now, when does the column at (x, y) obstruct the center of the column at (a, b)? It happens if x<=a, y<=b, and the distance d from the point (x, y) to the line connecting the point (0, 0) with the point (a, b) is less than or equal to r - the radius of each column. Now, consider the triangle with vertices (0, 0), (x, y) and (a, b). Its area s can be found by multiplying 0.5 by its base and height, in other words, it is equal to 0.5*sqrt(a*a+b*b)*d, so d=2*s/sqrt(a*a+b*b). On the other hand, its vertices have integer coordinates, and Pick's formula tells us that s is a half-integer: either 0, or at least 0.5. Because of this, d is either 0 or at least 1/sqrt(a*a+b*b).

When can d be equal to 0? It happens if an only if a and b are not relatively prime: in that case there's a column blocking the view directly. In all other cases, d is at least 1/sqrt(a*a+b*b). Moreover, this lower bound is tight: we can always find a point (x, y) that makes d equal to 1/sqrt(a*a+b*b). For example, let's consider the point that's closest to the segment (0, 0) - (a, b) inside its bounding box. It's not hard to see that the resulting triangle does not have any other integer points inside or on its boundary (otherwise those would be closer), and thus its area is 0.5 by Pick's formula, which yields the required value of d.

Now we can finally write down a very simple description of the columns we see: we need a and b to be relative prime, and have 1/sqrt(a*a+b*b)>r, in other words a*a+b*b<1/(r*r). The latter formula simply describes a circle with radius 1/r, so the problem boils down to counting integer points inside an intersection of a square and a quarter-circle, which is a relatively standard number theory problem.

The simple circular shape of the set of the visible columns is one of the beautiful sides of this problem, as it enables a different way of solving it: implementing a slow solution, such as the one for the small input, and then visualizing the result to get an insight. For example, plotting a grid corresponding to all visible columns with r=0.01 results in the picture above, which clearly suggests the idea of a circle with radius 1/r.

Thanks for reading, and check back soon for the next week's summary!

A jam week

Google Code Jam 2016 Finals was the main event of the first August week (problems, results, top 5 on the left, analysis, live stream recording). There was very close competition at the top during the entire contest, but in the end the favorite Gennady.Korotkevich has pulled quite a bit ahead of the field - congratulations!

The problems were interesting in different ways this time, and it's hard to pick a single most beautiful one - but I will choose problem C "Gallery of Pillars". You are given two numbers n and r. There's a nxn grid of pillars, with a pillar of radius r centered in each point of the grid except the bottom-left corner. How many pillars are visible from the bottom-left corner?

This could initially seem to be a tedious but standard geometry problem, but the constraints were very high: n is up to 10⁹, and r is between 10^-6 and 0.5. These constraints eliminate any chance of passing for any solution that just tries to enumerate all visible pillars. Can you count them faster?

Distributed Google Code Jam 2016 Finals continued the exploration of the new field on Saturday (problems, results, top 5 on the left, analysis). Just like in non-distributed Code Jam, the last year's winner could retain the crown, but the fight was even more fierce this time. Congratulations Bruce!

This was also the first time I took a stab at solving distributed problems myself. My result was nothing too impressive (39 points from B-small, E-small and E-large), but now I can appreciate and share with you the nicer problems :)

The only problem I solved, problem E "gold", was very nice. You were looking for gold in a sequence of 10¹¹ cells. You was also given the number of cells that contain gold, which was up to 10⁷. Your program was executed on 100 machines. Each machine could ask questions about the location of the gold in the following way: given a cell number, the reply was either "this cell contains gold", "the closest cell with gold is to the left", "the closest cell with gold is to the right", or "the closest cells with gold to the left and to the right are at the same distance". One question took 0.2 microseconds, and the time limit was 15 seconds, so each worker could use at most 750000 questions, meaning that even between all 100 workers there was no time to query all 10¹¹ input cells. The workers could also communicate with each other, each worker sending at most 8MB of data distributed between at most 5000 messages to other workers. How does one find all gold so quickly?

Finally, Codeforces Round 366 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). The problems turned out to be very tough, with two problems enough for second place, but it was of course better to solve three and win, just like kcm1700 did - congratulations!

In my last summary I've mentioned an unsolved Yandex problem: consider sequences of 2n parentheses of n different types such that there's exactly one opening and exactly one closing parenthesis of each type. A sequence is considered good if the parentheses can be colored with two colors in such a way that the subsequences formed by each color are balanced parenthesis sequences. How many good sequences exist for the given n? n is up to 500.

The first approach that comes to one's mind might be: let's consider the number of ways to pick two balanced parenthesis sequences of lengths k and n-k, and then multiply that by the number of ways to interleave them, and then by n! to assign the parentheses types.

This solution is incorrect because it might count a good sequence more than once, as there might be more than one way to color it with two colors in the way described above. In fact, each good sequence is counted at least twice, as we can swap the two interleaved sequences and get the same result! And in general, each good sequence is counted as many times as the number of valid colorings it has.

The next natural question is: how many valid colorings does a given good sequence have? This is relatively easy to determine: we can draw a graph between parentheses types, connecting two types if the corresponding parentheses must have different colors, which happens if the corresponding segments are intersecting but not containing one another. Now valid colorings of the parentheses correspond to colorings of this graph without two vertices of the same color sharing an edge. And that, in turn, is either 0 (in case the graph is not bipartite), or 2 to the power of the number of its connected components otherwise.

Even though the last observation doesn't lead to a solution directly, it provides valuable insight into the structure of the problem. We will call the sequences corresponding to a connected bipartite graph simple, and the rest complex. Each simple sequence has exactly two valid colorings. Each complex sequence can be decomposed in the following way: the connected component containing the first parenthesis, and the remaining connected components. That connected component corresponds to a simple sequence of smaller length, and the rest correspond to simple sequences that can be inserted anywhere into it.

Now we finally have a clear path towards the solution. We will count the number of colored simple and complex sequences of each length (so each sequence will be counted the number of times equal to its number of valid colorings). In order to count the number of simple sequences, we will subtract the number of complex sequences from the total number of sequences which we've determined above. And in order to count the complex sequences, we will try all possible sizes for the simple sequence containing the first parenthesis, and multiply the number of simple sequences of that size by the number of ways to insert more simple sequences into it.

The latter can be counted using two-dimensional dynamic programming: how many ways are there to insert several sequences with a total of n parentheses into a simple sequence with length k (in other words, with 2k+1 different available insertion positions).

And finally, after knowing the number of simple sequences, we need to find the total number of sequences, but without counting different colorings of the same sequence multiple times. This is counted by analogous two-dimensional dynamic programming, but without multiplying by 2 each time we add a new sub-sequence.

Thanks for reading, and check back later for the next week's summary!

Google Code Jam 2016 finals live stream

The final round of Google Code Jam 2016 has just started, and you can follow along the live stream. Enjoy!