Solving problem E involved this wonderful feeling where a relatively natural statement hides a solution with multiple interesting layers that "click" together. You are given k (k<=200) distinct positive integers ai (ai<=105). Consider all sequences of length n (n<=1018) with all elements equal to one of the given integers. Count the number of those sequences with the given sum s (s<=1018). Is that number odd or even?
First, let's deal with the k-th power. Consider a set S of vertices of the power graph. Each of those vertices is a k-tuple of vertices of the original graph. Let's consider the first position p in those tuples which has at least two different vertices. For example, if S has vertices (a, b, a, c), (a, b, a, d) and (a, b, b, c), then we're interested in the third position since both a and b appear there, while in the first position we always have a, and in the second position we always have b.
Now let's consider the set T of all vertices of the original graph that appear in this position. If S is strongly connected, then T is also strongly connected, because any path can be "projected" to T and still be a valid path due to the construction of the power graph.
Now suppose T is strongly connected. It turns out that then S is strongly connected as well, because when there's an edge from a to b in the original graph, there's an edge from any vertex with a in position p to any vertex with b in position p, therefore in order to find a path from any vertex in S to any other vertex in S it suffices to find a path between the corresponding vertices in the p-th position, and then pick any matching vertices for the intermediate stopping points. Note that we rely on the fact that T has at least two vertices here, as we need a cycle in T to build a path between two vertices in S that have the same vertex in the p-th position.
We have found that the strong connectivities (is there such a word?) of S and T are equivalent. Therefore if we can solve our problem for k=1, we can solve it for any k: consider a subset T of size m>=2 of the original graph that is strongly connected. How many sets S correspond to T in the p-th position? For each of the m vertices of T we have nk-p vertices of the power graph with this vertex in the p-th position, and we need to take any non-empty subset of those, so in total we get (2nk-p-1)m subsets.
Here comes the more interesting part of the problem: what to do for k=1? More specifically, how to count the number sets of vertices of each size that induce a strongly connected subgraph in a given graph with n<=23 vertices?
My approach was based on the Floyd-Warshall algorithm. We would like to run it on all 2n subsets, which would take O(2n*n3), which is too slow for n=23. We can replace the inner loop with one bitwise or operation, bringing the running time down to O(2n*n2) — still too slow.
However, we can now merge the iteration over subsets with the Floyd-Warshall algorithm! The outer loop of Floyd-Warshall iterates over intermediate vertices, so if we take a recursive algorithm that iterates over the 2n subsets, we can do one iteration of Floyd-Warshall outer loop as soon as we've decided that a vertex belongs to the subset. Therefore we will need to do at most one iteration of the Floyd-Warshall outer loop at each level of recursion, bringing our running time to O(2n*n+2n-1*n+2n-2*n+...)=O(2n*n)!
Here is the relevant part of my contest submission with some comments:
// Recursive search: we have decided that from the first
// "at" vertices we have taken the subset "mask",
// and the intermediate state of Floyd-Warshall after
// iterating over them is in "preach".
private void rec(int at, int mask, int[] preach) {
if (at >= n) {
// Check if the graph is strongly connected.
// "preach" already has the transitive closure for the
// chosen subset, so we check if it's complete.
int count = 0;
for (int i = 0; i < n; ++i) if ((mask & (1 << i)) != 0) {
++count;
if ((preach[i] & mask) != mask) {
return;
}
}
if (count >= 2) {
++res[count];
}
return;
}
// Do not take at-th vertex.
rec(at + 1, mask, preach);
// Take at-th vertex, meaning that we need to do one more
// iteration of Floyd-Warshall outer loop.
// To avoid allocating new arrays in Java too often,
// I have pre-allocated one array per level of recursion
// which I overwrite here.
int[] nreach = reach[at + 1];
System.arraycopy(preach, 0, nreach, 0, n);
for (int i = 0; i < n; ++i) if ((nreach[i] & (1 << at)) != 0) {
nreach[i] |= nreach[at];
}
rec(at + 1, mask | (1 << at), nreach);
}
The space of possibilities for drawing arbitrary curves on the plane is enormous, so it's not clear how to approach this problem. First, we can notice that the curves for adjacent vertices intersect, and therefore can't be nested in one another. Is that the only restriction? In other words, can we choose the curves in such a way that any two curves either intersect (when the corresponding vertices are adjacent) or are nested (if they're not)? At first I believed it was always possible, then finding the size of the longest chain is just finding the size of the largest independent set in a tree, which can be done with a simple greedy from the leaves. I made a quick submission, which turned out to be incorrect :)
Finding the size of the largest independent set in all sub-caterpillars of the given tree is slightly more tricky, but still doable with dynamic programming on the tree. However, is it the correct solution? I did not have a proof, but after so much doodling that didn't provide a counterexample it felt right, so I decided to try with another submission, which worked. You can find the proof in the editorial :)
Thanks for reading, and check back for this week's summary!
No comments:
Post a Comment