|
Match Editorial |
Online Round 2B
October 7, 2006
Match summary
This online round turned out to be very mathy, with two problems dealing with arithmetics. This caused problems for several high ranked coders. Of 34 "red" coders, 15 were eliminated (5 being current or former 2600+ rated members), while the two most recent TCCC winners, mathijs and tomek, finished modestly in places 34 and 30, respectively.Early on, the match looked like a one-man show from Eryx, who had the fastest submissions on the first two problems as well as a fast submission on the last problem. But a resubmit on the hard problem caused him to drop a few places as other coders catched up. Egor overtook first place for a short while with a very fast submission on the hard, but resubmits on the first two problems spoiled his winning chances. In the end, the round was won by Polish coder jakubr, slightly ahead of superzn and PaulJefferys.
The challenge phase was relatively calm, with few solutions successfully challenged. The system test took a heavier toll, but overall the success rate on the submitted problems was fairly high.
The Problems
BComputation
Used as: Division One - Level One:
Perhaps the hardest part of this problem was understanding it -- or at least that was my impression, as the problem set tester. Since the equation should hold for all positive n, we have an infinite number of equations to satisfy, each equation being a sum of terms -- in other words, we have an infinite linear equation. To get an idea how to solve it, we start by expanding the equation for a couple of different n, starting with n = 1:
Value 250 Submission Rate 124 / 136 (91.18%) Success Rate 112 / 124 (90.32%) High Score Eryx for 227.79 points (9 mins 2 secs) Average Score 158.59 (for 112 correct submissions)
0 = B0 + 2C1B1
Since we know B0 (that was given in the input), and 2C1 can be calculated
either by the formula given in the notes or using Pascals triangle,
we see that B1 = -B0 / 2C1.
For n = 2, the equation becomes
0 = B0 + 3C1B1 + 3C2B2
The only unknown variable in this equation is B2, so we can easily calculate it.
Now a pattern starts to appear: for each n, we can calculate one BN. So to
solve the problem, we loop over all n from 1 to pos, solve the equation pos times, and then return
Bpos.
An extra annoyance in this problem is that all calculations must be done using fractions. Experienced coders most likely had a prewritten fraction class lying around, ready to be used in situations like this. If not, writing one doesn't have to take very much time (it's almost always better to put the fraction logic in a separate class instead of cluttering the code with fraction calculations). The input constraints were set so that using integers for the nominator and denominator in the fraction class would be enough if the fraction was reduced by the gcd after every operation. While this is hard to estimate when coding the problem, the limited input range made it possible to test all inputs and make sure that there were no overflows.
FracSum
Used as: Division One - Level Two:
By simple arithmetic, the equation a/b = c/d + e/f can be rewritten as a/b = (cf + de) / df. We should start by dividing a and b with their greatest common divisor, gcd(a,b). Then df must equal b. Without loss of generality, we can assume that d <= f, and hence that f = b/d. d can then be no greater than the square root of b. The problem constraint guaranteed that b was at most 2 billion, so we can try all divisors less than or equal to sqrt(b) by simply looping up to sqrt(b), skipping all non-divisors. We then get the equation cf + de = a where a, d and f are known integers, and c and e are unknown integers. This is a traditional linear diophantine equation, which is solveable if and only if a is divisible by gcd(d,f). But because of the initial division with gcd(a,b), gcd(d,f) must equal 1 (otherwise cf + de and df would share a common factor), and a is of course always "divisible" by 1.
Value 500 Submission Rate 112 / 136 (82.35%) Success Rate 91 / 112 (81.25%) High Score Eryx for 495.49 points (2 mins 43 secs) Average Score 371.27 (for 91 correct submissions)
Eryx solved this problem blazingly fast. See his solution for a clean implementation of this algorithm.
SplitSubgraphs
Used as: Division One - Level Three:
There are several approaches to this problem, some of them completely wrong. For instance, it might be tempting to count the number of ways to partition the graph into one A partition (the independent set, where none of the vertices are pairwise adjacent), one B partition (the clique partition, where all vertices are pairwise adjacent) and a set of nodes not part of the split graph. This does not work, however, because a split graph generally has several ways of being split up into an A and a B partition.
Value 1000 Submission Rate 31 / 136 (22.79%) Success Rate 20 / 31 (64.52%) High Score Egor for 884.52 points (10 mins 32 secs) Average Score 609.17 (for 20 correct submissions)
One method that obviously is too slow is to test all subgraph (about one million in worst case), and for each subgraph test if it's split. This can't be done very fast, though, because a subproblem to this is to find the maximal clique in the subgraph, a problem that in itself is NP-complete. The trick is to do both of these operations simultaneously.
One important property of a split graph is that all subgraphs of it must also be a split graph (unless the subgraph contains less than two nodes). Conversely, a split graph S' can be generated from a smaller graph S by adding a new vertex (including its edges) to it. This new vertex must then either have no edge to any of the vertices in an A partition of S, or to all vertices in a B partition of S.
But given that we have a split graph, which vertices in it belong to respective partition? As mentioned earlier, a split graph generally can be split into several different A and B partitions. It turns out that if we know one way to split the vertices into an A and a B partition, we can generate the other possible splits fairly easy. Given one possible split A and B, in all other splits A' and B', A' can contain at most one node from B, and B' can contain at most one node from A. This can easily be proved, because if two nodes went from A to B', that means they were not adjacent before, and they must be adjacent for them to be in B'. Similarly if two nodes went from B to A', they must have been adjacent before, but that's not allowed in A'. We end up with the following pseudo code to check if a vertex can be added to a split graph S:
Input: S(A,B) a split graph, where A is the set of nodes in S that
are non-adjacent, and B the set of nodes that are adjacent.
v vertex that should be added to S
Output: S'(A',B') a new split graph with vertex v added to it
or null if v can't be added
Algorithm: for each vertex a in A // move one vertex from A to B'
if a is adjacent to all vertices in B
A' = A - {a}
B' = B + {a}
if v has no edge to any vertex in A'
return S'(A' + {v}, B')
if v has an edge to all vertices in B'
return S'(A', B' + {v})
for each vertex b in B // move one vertex from B to A'
if b has no edge to any vertex in A
A' = A + {b}
B' = B - {b}
if v has no edge to any vertex in A'
return S'(A' + {v}, B')
if v has an edge to all vertices in B'
return S'(A', B' + {v})
for each vertex a in A // move one vertex from A to B'
for each vertex b in B // and one from B' to A
if b has no edge to any vertex in A - {a}
if a has an edge to all vertices in B - {b}
A' = A + {b} - {a}
B' = B - {b} + {a}
if v has no edge to any vertex in A'
return S'(A' + {v}, B')
if v has an edge to all vertices in B'
return S'(A', B' + {v})
return null
Now, counting the number of split graphs among the subgraphs of the input graph is an easy task.
Recursively we can for each vertex decide whether or not we want it in the subgraph. If we
want a vertex in the subgraph, we use the algorithm above to determine in which partition it will
go (and if it is possible at all to include it).
Regarding implementation details, it's convenient to use a bitmask to store the adjacency matrix of the input graph. In that way, operation like if b has no edge to any vertex in A - {a} can be done with logical bitwise operations. Furthermore, the first two parts of the pseudo code above can be incorporated in the last nested loops by simply considering "empty" vertices a and b.
I didn't find an implementation among the contestants that exactly matched this solution description, so for a clean implementation of this algorithm, see my solution in the practice room. But as I said, there are many ways to solve this problem, so it might be useful to check out some of the contestants solutions as well.
