Monday, April 25, 2016

0.636 of a week

TopCoder SRM 689 on Saturday presented two very creative problems (problems, results, top 5 on the left). The medium problem required mostly mathematical thinking, while the hard problem involved both mathematics and algorithms. Scott Wu has figured out both, and didn’t forget to add 150 challenge points to stay in the first place – way to go!

The more algorithmic one went like this: you are given 2n points on the plane, no three points on the same line, and a matching between them – n segments connecting the points to each other in such a way that each point is the endpoint of exactly one segment. Your goal is to find another matching with an additional property: the segments must not intersect. That would be a classical problem, but here there’s an extra constraint that changes the problem completely: the total length of the segments in your matching must be at least 0.636 (zero point six three six) times the total length of the segments in the given matching. n is at most 100.

This problem is yet another example of the brilliant problems that the TopCoder admins and problem authors manage to come up with time and time again. Huge kudos to cgy4ever and all the TopCoder problem authors!

VK Cup 2016 Round 2 took place a day later (problems, results, top 5 on the left, parallel round without first problem results) . Team SPb SU Base have continued their super impressive recent form, both in personal and in team competitions – congratulations to -XraY- and ershov.stanislav!

Last week I’ve described a nice problem: you are given a 20x100000 table of zeroes and ones. You are allowed to invert (replace 0s with 1s and vice versa) rows and columns of this table. What is the smallest number of ones you can make the table contain?

The table is hugely asymmetrical: there are a lot of columns but just 20 rows – and we definitely need to exploit that. Since the order of inversions doesn’t change the result, let’s say we start by inverting the columns, and then handle the rows. Consider a column. Let’s say the ones in it form a binary number x. Let’s also say that the ones corresponding to the rows we’re going to invert form another binary number y. Then the ultimate number of ones in this column is the number of ones in x^y (here ^ stands for bitwise exclusive-or), let’s denote it ones(x^y). Note that we can also invert the column before inverting the rows, in which case we will get ones((~x)^y), which is actually equal to n-ones(x^y), where n is the number of rows, and ~ is the bitwise negation of a n-bit number. Our goal is to pick the y that minimizes the sum of min(ones(x^y), n-ones(x^y)) over all columns.

Note that the binary numbers are used here purely for the purposes of an efficient and easy-to-code implementation – fundamentally we’re just operating with sets of rows.

The key insight is: let’s use dynamic programming to count for each y and each number k from 0 to n the number of x’s such that ones(x^y)=k. Let’s call it a(y, k). It’s easy to see that knowing these numbers allows counting the above sum easily, and thus picking the value of y that minimizes it.

For k=0, this is easy – we just need to count the number of times each bit pattern appears in a column (we can just iterate over all 100000 columns and increment the corresponding value in an array). For k=1, it’s also somewhat easy: a(y, 1) is equal to the sum over all y’ that differ from y in exactly one bit of a(y’, 0). Continuing this idea to larger values of k is not as easy, though: we will count each way of flipping two bits twice, depending on the order in which we flip the bits, and even more worryingly we might flip the same bit twice, thus declaring that a number differs from itself in two bits. One can probably account for this via some clever combinatorics, but there’s a better way.

It’s actually quite logical: since we don’t want to overcount different orders of flipping the bits, let’s always flip the bits in a pre-determined order. In other words, we add another dimension to our dynamic programming: b(y, k, t) is the number of x’s (remember, those are the bit patterns of columns of the input matrix) such that ones(x^y)=k, with an additional restriction that x and y may only differ in the first t bits. Now we can easily see that b(y, k, t+1) = b(y, k, t) + b(y ^ (1 << t), k - 1, t): we either flip the t-th bit, or we don’t. And the number a(y, k) that we need is simply found as b(y, k, n). This solution needs O(2nn2) very simple operations, which fits in time for n=20.

As shown on the picture on the left, this dynamic programming is similar in spirit to the discrete Fourier transformation. I’m not sure if that similarity has something meaningful behind it.

There was also an Open Cup round this Sunday, sharing the problems with an international (ex-USSR) onsite competition called Vekua Cup, but its results are still not available, so I will cover it next week.

I was preparing this post on a plane, so instead of the usual nature photo I only have this :) Thanks for reading, and check back next week!