An open week

The September 19 - September 25 week contained the first stage of Open Cup 2016-17: Grand Prix of Japan (results, top 5 on the left). Some teams have competed on this problemset earlier during the Petrozavodsk camp, and two of those teams remained in first two places after everybody else joined - congratulations to Moscow SU Trinity and KTH Omogen Heap!

Problem I in this round possessed the right mix of simple statement and interesting solution, while not being very hard: you are given a connected undirected graph with at most 2000 vertices and 2000 edges, where each edge needs to be colored either red or blue. You need to do the coloring using a single alternating walk: you start in some vertex, then keep moving along the edges, coloring the first edge you pass red, the second blue, the third red again, and so on. You are allowed to pass the same vertex and even the same edge twice, and when you pass the same edge multiple times, the last color used stays. Is it possible to obtain the required coloring?

In my previous summary, I've mentioned a super hard SRM problem: 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. 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.

The last part, which asks to see which shape each particular subgrid can have, does not really change the problem a lot - if we can solve the "is it possible" version fast enough, then we can just try placing each shape in each subgrid, and solve the same problem for the rest. So in the rest of this explanation I will concentrate on the "is it possible" part.

The key that opens this problem is: let's replace the 5-cell shape into four dominoes: a C-shape or an L-shape consisting of cells A,B,C,D,E in this order, can be viewed as a union of four dominoes: AB, BC, CD and DE. The eight possible dominoes along the border of a 3x3 subgrid can be split into four pairs of opposite dominoes (see an example on the left). Each 5-cell shape then corresponds to picking one domino in each pair of opposite dominoes.

One might say that this transformation is not accurate: not every way of picking one domino in each pair of opposites yields a valid 5-cell shape. However, it turns out that every way of picking one domino in each pair of opposites yields a set of cells that contains a valid 5-cell shape inside (see an example on the right).

Because of this, the following reformulation always has the same answer as the original problem: can we pick four border dominoes in each 3x3 subgrid, one from each pair of opposites, in such a way that dominoes from different subgrids do not overlap?

Finally, now it's not that hard that we have an instance of the 2-SAT problem: we have a few boolean variables (which domino to pick for each pair of opposites), and a few restrictions on pairs of values (stemming from the intersections). We can solve this problem in linear time.

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

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!