A Russian Code week

Codeforces held two rounds this week, starting with Round 371 on Tuesday (problems, results, top 5 on the left, analysis). Despite quite a few attempts at solving the hardest problem E, only LHiC's solution was correct, and since he didn't solve D, the speed of solving the first four was the deciding factor for the top places in the end. Congratulations to geniucos on the victory!

Codeforces Round 372 on Saturday started the competitive weekend (problems, results, top 5 on the left, analysis). This time TooDifficult left nothing to chance, and claimed the first place by more than a thousand points thanks to being the only contestant to solve four problems. Congratulations!

After a tiny 15-minute pause, TopCoder SRM 698 picked up the flag (problems, results, top 5 on the left, my screencast). With almost an hour left to solve the 1000-pointer, I still could not come up with a single idea that would at least transform the problem into something potentially tractable, and not even with randomized backtracking or "subset" dynamic programming that could be close to passing. I was not the only one feeling this way, and so the contest was decided during the challenge phase. I've managed to find +100 that would've earned me the first place, but also picked up -100 on unsuccessful challenges along the way - I'm lucky that the screencast doesn't capture the sound of cursing - and ended up with the coding phase score. So did rng_58, but his coding phase score was significantly higher and thus he kept the victory. Congratulations!

Here's the stumbling 1000-pointer: you're given a 50x50 grid, with each cell either free or blocked. You're also given at most 100 (potentially overlapping) 3x3 subgrids of this grid, and are looking to draw an L-shape or a C-shape in each of those subgrids in such a way that those shapes do not overlap, and use only free cells. An L-shape or a C-shape consists of 5 consecutive border cells of a 3x3 subgrid (see the example on the left). There are 4 possible different L-shapes in each 3x3 subgrid, and 4 possible different C-shapes. You need to check if such drawing is possible, and if yes, find for each 3x3 subgrid whether it can have a C-shape as part of a valid drawing, and whether it can have an L-shape as part of a valid drawing.

Russian Code Cup 2016 Finals on Sunday has wrapped up the sixth installment of this tournament (problems, results, top 5 on the left, online mirror results, analysis). Extremely technical problems led to a lot of wrong submissions and very slow progress, but tourist still didn't leave any doubt with regard to the winner, solving the required three problems in just over an hour and almost getting the fourth. Congratulations on the second Russian Code Cup victory!

In the last week's summary, I have mentioned an algebraic problem from the TCO Wildcard Round: 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).

Ilya Mironov has pointed out in comments that there's a specialized algorithm for solving just this problem. However, I believe that it's more educational to learn to solve this problem using the understanding of the underlying math structure and standard algorithms that come with it. The object we're studying is remainders modulo p with the operation of multiplication. All remainders except 0 form the multiplicative group modulo p, and there's a well-known theorem that says that this group is always cyclic - in other words, isomorphic to the additive group of remainders modulo p-1. This isomorphism maps taking an element to the power of k to multiplication by k modulo p-1, and we know how to inverse that - it's just division by k modulo p-1.

That gives us a full solution to our problem: first, find out to which remainder modulo p-1 does the isomorphism map a. Then divide that remainder by k. Finally, apply the inverse of the isomorphism to get the answer. We also have to handle the case of a=0 separately since 0 doesn't belong to the multiplicative group, but there the solution is easy: b=0.

Of course, there are still implementation details to figure out. How does the isomorphism work, and how to evaluate it quickly? It's not hard to see that the isomorphism is completely defined by the multiplicative remainder g that maps to 1 in the additive group, as all other elements then have to be some powers of g, since g^d must map to d for each d from 0 to p-2. Such remainder g is called a generator or a primitive root.

Moreover, all powers g^d for d that are relatively prime with p-1 are also generators. Because we need to find any generator, and there are plenty, the most practical strategy for finding one is just trying a few remainders and checking if they are generators. In order to check if a remainder g is a generator, we must see if all its powers from 0 to p-2 are different, but since its order must divide the order of the multiplicative group, it suffices to check that g^d is not equal to 1 for all values of d that are proper divisors of p-1.

Finally, having found a generator g, evaluating the isomorphism is called the discrete logarithm which can be solved using a meet-in-the-middle approach, also known as baby-step-giant-step here. Let's pick a number q around sqrt(p-1), and pre-compute baby steps d⁰, d¹, ..., d^q-1, and giant steps d^q, d^2q, ... (up to the first giant step with power that exceeds p-1). Now it's not hard to see that if we try multiplying our number a by all giant steps we will at some point get a result equal to some baby step: a*d^uq=d^v, and then a=d^v-uq, so a maps to v-uq mod p-1 under our isomorphism. The giant and baby steps can be precomputed since p is fixed.

The final missing trick is dividing a remainder w by k modulo p-1. This also comes naturally with the understanding of remainders modulo p-1. First, let's represent k as m*n where m is gcd(k, p-1), and n is relatively prime with p-1. If m does not divide w, there's no solution. If m does divide w, then we now need to divide w/m by n modulo (p-1)/m. Since n is relatively prime with (p-1)/m, it has an inverse o such that n*o=1 modulo (p-1)/m, and thus our division result can be found as o*(w/m) modulo (p-1)/m. The numbers o and m can be precomputed since k and p are fixed.

Phew! This looks like one hell of a solution, but actually it's much easier to code it than to explain. And since all steps come naturally from understanding of how remainders work, you don't need to memorize any of them - you can construct them on the fly using just a few clues that you remember.

Thanks for reading, and see you next week!

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!