SRM 581: Did I solve the 500?

So I continued with the so-called suicidal strategy, which was so successful last match.

I opened the div1 500 problem, it seemed like ultra hard, full of cycles and trees. Decided to check if the 900 points problem was approachable. Well, maybe it is approachable, but not to me. Decided to go back to div1 500.

Div1 500: The one with two trees and cycles

You got two trees, each with N nodes (up to 301). The nodes from one tree will be randomly connected with some of the other tree. Each node from tree A will be assigned a unique node from tree B and they will be connected. Each permutation has the same probability. Return the expected number of unique simple cycles of length K in the resulting graph . Two cycles are the same if you can rotate and/or reverse one to make the other.

I didn't notice at first, but the constraints say that K is at most 7. That is quite the small constraint. My first idea was to iterate through each possible cycle of length K. Because of the magic of the expected value, the sum of the probabilities that each of these cycles happens in the final graph is the result. Of course, iterating is not possible, even with small K. But this is still a good start.

It turns out that K is convenient for another reason. The cycle will be composed of exactly one continuous fragment (line of nodes) from tree 1 and one continous fragment from tree 2. It is possible to prove that any other configuration cannot happen with 7 nodes. Both fragments need at least 2 nodes

So we can just focus on the fragments. For example, take two fragments, one from tree A has length 3, and one from B has length 4. There are exactly two different cycles that contain these fragments. The probability that each of these cycles will happen is 1 / (N*(N-1)). This is valid for any pair of fragment lengths (with length at least 2).

We can actually just count the total number of fragments of each length from 2 to K-2 that are possible in each of the trees. Then take the pairs of lengths of fragments, and multiply the probability with the number of ways to make those pairs.

The last complication of the problem is to count the number of fragments of each length. This requires dynamic programming and was actually the thing that took me (by far) the most time to think of and code.

vector<int> countPieces(const vector<int>& tree, int K)
{
    int N = tree.size() + 1;
    vector<int> children[N];
    for (int i=0; i<tree.size(); i++) {
        children[tree[i]].push_back(i + 1);
    }
    int paths[N][K+1];
    
    vector<int> c(10, 0);
    for (int i = N-1; i >= 0; i--) { //300
        for (int k=0; k<=K; k++) { //7
            paths[i][k] = 0;
            // how many paths finish here?
            if (k > 0) {
                for (int j=0; j<children[i].size(); j++) {
                    paths[i][k] += paths[children[i][j]][k-1];
                }
            }
        }
        paths[i][1] = 1;
        for (int k=0; k<=K; k++) {
            c[k] += paths[i][k];
        }
        
        int total[K+1];
        for (int k=0; k<=K; k++) {
            total[k] = 0;
        }
        for (int j=0; j<children[i].size(); j++) {
            for (int k1=0; k1<=K; k1++) {                
                for (int k2=0; k2 + k1 + 1<=K; k2++) {
                    c[k1 + k2 + 1] += paths[children[i][j]][k1] * total[k2];
                }
            }
            for (int k=0; k<=K; k++) {
                total[k] += paths[children[i][j]][k];
            }
        }
    }
    return c;
}

double expectedCycles(vector<int> tree1, vector<int> tree2, int K)
{
    //both trees are topsorted, tree1[i] returns the parent of i+1.
    
    // Each cycle must contain exactly two pieces:
    // "A piece from A and a piece from B"
    // It is impossible to have a cycle that works otherwise. Because K <= 7
    vector<int> c1 = countPieces(tree1, K);
    vector<int> c2 = countPieces(tree2, K);
    
    int N = tree1.size() + 1;
    double res = 0;
    for (int a=2; a<=K-2; a++) {
        int b = K-a;

        // A piece of length a from A, and a piece of length b from B.
        // what is the probability these are joined?
        // a0..an ... b0..bn  |
        //                     _
        // a0..an ... bn..b0  |
        double p = 1 / (double)(N * (N - 1));
        res += 2*p * c1[a] * c2[b];
    }
    return res;
}

I took long as usual to code this solution and it had bugs. By the time there were less than 10 minutes left before the end of the match, I still had bugs. I decided to keep on solving this problem instead of opening the easy problem. I was able to fix the last few bugs and submit. The score was quite low though.

I tried to solve the easy problem in less than 8 minutes, but that was just not possible.

This problem alone was very cool. I am happy to dedicate most of the match solving it.