A perfectly matching week

The June 20 - June 26 week was much calmer than the previous one. There were two "regular" rounds, the first being Codeforces Round 359 on Thursday (problems, results, top 5 on the left, analysis).

The second regular round was TopCoder SRM 693 on Saturday (problems, results, top 5 on the left, my screencast).

The medium problem was from the rising category of "constructive" problems. You are given just one integer k between 1 and 10⁹, and need to construct a bipartite graph with exactly k perfect matchings. Not any such graph will do: it must have at most 20 vertices in each part, and at most 120 edges. There can be more than one edge between the same two vertices, and all those edges are distinct for the purpose of counting the number of perfect matchings. Apart from those restrictions, you're free to construct the graph in any way you like. Can you solve this one?

Challenge24 in Budapest was the onsite competition of the week, challenging the brave with 24 hours of problem solving (problems, results, top 5 on the left). The scores were extremely close in the final standings, and the winner was team Dandelion - congratulations!

In the last week's summary, I have once again mentioned quite a few interesting problems - let's analyze the IPSC one here. To remind, we're studying two permutations of 2n objects, called L and R. The permutation L is constructed like this: the first n objects in the old order go to odd-numbered positions in the new order without shuffling, and the last n objects in the old order go to even-numbered positions in the new order, without shuffling. The permutation R does almost the same, but the first n objects go to even-numbered positions, and last n go to odd-numbered positions. You are given three numbers: n, a and b. An object is currently on position a in the permutation of 2n objects, and we want to put it to position b using only operations L and R. Construct any shortest sequence of those two operations that achieves it.

Solving this problem involved studying the properties of operations L and R, trying to understand how they work. Such exploration involved several dead ends which I won't describe here, so it might seem that we're progressing almost miraculously :)

First, we will solve this problem from the end towards the start - in other words, let's consider the reverse operations L' and R'. How do they transform our current position x? It's not hard to see that L' moves odd-numbered positions x to x/2 and even-numbered positions x to x/2+n, and R' maps odd positions to x/2+n and even positions to x/2, where "/" stands for integer division (rounding down), and positions are numbered from 0 to 2n-1.

In other words, we repeatedly do the following: remove the last bit of our number, then choose to add or not to add n. Adding n after removing i last bits can also be viewed as adding n*2ⁱ in the very beginning. Assuming we do k steps in total, we can add n*2, n*4, ..., n*2^k, and that means we can add n*m for any even number m between 0 and 2^k+1-2.

After all the additions are done, we remove k last bits, and want to obtain the given number a. It means that before removing the k last bits, our number has to be between a*2^k and (a+1)*2^k-1.

Which means that the problem has boiled down to: does there exist such even number m between 0 and 2^k+1-2 that a*2^k <= b+n*m <= (a+1)*2^k-1?

This is of course easy to check for any given k. Moreover, we can see now that once n<=2^k and b/(a+1)<2^k there will always be such m, so we need to try only a logarithmic number of k values before we find the answer! Reconstructing the sequence of L and R operations knowing the values of k and m is an exercise in carefully traversing the above reasoning.

I find the way the solution flows from combinatorics to arithmetics in this problem quite beautiful. The solution explained in the official analysis skips the "from the end" part, and thus ends up being even simpler - but then it's not as satisfying to make it work :)

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

Tweet