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!
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.
0 komentar:
Post a Comment