Monday, September 19, 2016

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, 109+7), find any integer b such that bk=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 gd 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 gd 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 gd 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 d0, d1, ..., dq-1, and giant steps dq, d2q, ... (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*duq=dv, and then a=dv-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!

No comments:

Post a Comment