A week without centroids

The Jul 2 - Jul 8 week upped the stakes in the TopCoder Open 2018 race: only the top 50 would advance from Round 3A on Saturday (problems, results, top 5 on the left, parallel round results, analysis). With the hard problem having a much simpler solution than the one the problemsetters have anticipated, the scores were a lot higher than usual, and seeing this simple solution quickly was the key to victory. Congratulations to Blue.Mary on the win!

In my previous summary, I have mentioned a Codeforces problem: you are given a tree with n<=2000 vertices. How many cycles of length 1, 2, ..., k (k<=75) does it have, modulo 998244353? A tree does not have simple cycles, so we're interested in non-simple cycles of course. Two cycles that differ only by choosing the starting point and direction are still considered different.

The general approach is somewhat on the surface: let's do dynamic programming that would count said cycles for each subtree. When we're processing the subtree rooted at some vertex v, each cycle either doesn't touch v, in which case it's a cycle in one of the smaller subtrees, or it does touch v, in which case it looks like v->u (some child of v)->some cycle passing through u->u->v->...

In order to be able to count the cycles of each length passing through v, we need to know the number of cycles of each length passing through each of its children, so we need to compute two things in our dynamic programming for each subtree: the total number of cycles, and the number of cycles passing through the root of the subtree.

This gives a rough overview of the solution, but the details of the dynamic programming transition are still unclear: how do we make sure we correctly count the cycles differing only by the starting point?

Each cycle passing through v can decomposed into blocks between consecutive occurrences of v in the cycle. Each such block is obtained by taking a cycle passing through some child u of v, and adding a v->u edge in the beginning and a u->v edge in the end, so for a child cycle of length x the block has x+2 edges.

Actually, to make the previous statement entirely correct in the world where cycles differing by the starting point are considered different, we need to adjust it a bit: replace "cycle passing through v" and "cycle passing through u" by "cycle starting and finishing in v" and "cycle starting and finishing in u". Then our dynamic programming checks out, and we can find the answer for v given the answers for all its children by first adding up the answers for children to obtain the number of blocks of each size, and then doing an inner knapsack-style dynamic programming that counts the ways to combine the blocks.

However, since we have changed the definition of what we compute, we can no longer just add up those numbers to get the overall number of cycles in the tree. Here comes the most magic part of the solution in my opinion: in order to get the overall number of cycles in the subtree passing through v from the number of cycles that start and end in v, we need to just multiply that number by the size of the last block in the inner knapsack dynamic programming!

Indeed, this way we count the ways to choose the starting point within the last block. Why must it be within the last block? Because the cases where the starting point is in another block will be counted when we consider a cyclical shift of the blocks. To look at this from another angle, any cycle passing through v can be transformed into a cycle starting and ending in v by cyclically shifting it so that the first occurrence of v becomes the beginning of the cycle, and the number of ways to get each cycle doing this is equal to the size of the last block.

Here's the relevant part from my solution during the round:

static class Vertex {
    List adj = new ArrayList<>();

    public Description doit(Vertex skip, int k) {
        Description res = new Description();
        res.overallCycles = new long[k + 1];
        res.cyclesFromRoot = new long[k + 1];
        res.cyclesFromRoot[0] = 1;
        res.overallCycles[0] = 1;
        long[] singleStep = new long[k + 1];
        for (Vertex child : adj) {
            if (child == skip) continue;
            Description desc = child.doit(this, k);
            for (int i = 0; i <= k; ++i) {
                res.overallCycles[i] = (res.overallCycles[i] + desc.overallCycles[i]) % MODULO;
                if (i + 2 <= k) singleStep[i + 2] = (singleStep[i + 2] + desc.cyclesFromRoot[i]) % MODULO;
            }
        }
        for (int old = 0; old <= k; ++old) {
            long w = res.cyclesFromRoot[old];
            for (int a = 2; old + a <= k; ++a) {
                res.cyclesFromRoot[old + a] = (res.cyclesFromRoot[old + a] + w * singleStep[a]) % MODULO;
                res.overallCycles[old + a] = (res.overallCycles[old +a] + w * singleStep[a] % MODULO * a) % MODULO;
            }
        }
        return res;
    }
}

Thanks for reading, and check back for more!