November 21, 2020 2020 TCO Algorithm Semi Final 2 Editorials

CaterpillarSpanningTrees

In this problem, you are given a graph with N nodes and some edges, and you would like to count the number of caterpillar spanning trees in this graph. A caterpillar is an undirected tree where there exists a path that includes all vertices of degree two or more.

To solve this problem, we first handle the special case N <= 2. 

For all other cases, imagine that we took a caterpillar and erased all leaves. The part that remained will be called the core path. If the core path is just a single vertex, the caterpillar is a star. We’ll count these separately. We now have to count caterpillars with a non-trivial core path.

We can build the core path one vertex at a time. At the beginning we need to make sure that we add at least one leaf to its first vertex, and at the end we need to do the same for the last vertex.

For the counting we can have O(2^n * n) states of the form (set of vertices already connected, the last vertex on the core path, did we already attach some leaf to the last vertex on the core path?). We can propagate the counts forward, alternating between a step in which we add new leaves to the current last vertex and a step in which we add a new bare vertex to the core path. After the k-th such iteration we can determine the count of caterpillar spanning trees in which the core path has k edges.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 14;
long long dp[1<<MAXN][MAXN];

struct CaterpillarSpanningTrees {
long long count(vector<string> SG) {
    int N = SG.size();
    vector<int> G(N);
    for (int a=0; a<N; ++a) for (int b=0; b<N; ++b) if (SG[a][b] == 'Y') G[a] |= 1 << b;

    long long answer = 0;

    // count non-stars via DP
    for (int covered = 1; covered < (1 << N); ++covered) for (int last = 0; last < N; ++last) if (covered & 1<<last) {
        dp[covered][last] = 0;
        vector<int> neighbors;
        for (int n=0; n<N; ++n) if (covered & 1<<n) if (G[last] & 1<<n) neighbors.push_back(n);
        int NC = neighbors.size();
        int neighbor_pattern = 0;
        for (int n : neighbors) neighbor_pattern |= 1<<n;
        if (neighbor_pattern == (covered ^ 1<<last)) if (NC > 0 && NC < N-1) ++dp[covered][last];
        for (int select=0; select<(1<<NC); ++select) {
            if (covered == (1<<N)-1 && select == 0) continue; // last path vertex must have a neighbor
            int leaves = 0;
            for (int n=0; n<NC; ++n) if (select & 1<<n) leaves |= 1 << neighbors[n];
            for (int prev : neighbors) if ((leaves & (1<<prev)) == 0) {
                dp[covered][last] += dp[covered ^ (1<<last) ^ leaves][prev];
            }
        }
        // cout << "dp[" << covered << "][" << last << "] = " << dp[covered][last] << endl;
    }
    for (int last=0; last<N; ++last) answer += dp[(1<<N)-1][last];
    answer /= 2;

    // count stars
    for (int n=0; n<N; ++n) if (G[n] == (1 << N) - 1 - (1 << n)) ++answer;

    if (N == 1 || N == 2) answer = 1;

    return answer;
}
};

IDZToICE

In this problem, you are given two programming languages, IDZ and ICE and you would like to translate a program in IDZ to ICE. The full list of operations are as follows:

• “INC x”: Increment register x and continue to the next instruction.”DEC x”: Decrement register x and continue to the next instruction.
• (Decrementing a register with a zero leaves it at zero.)”ZERO x y z”: If register x contains a zero, continue to instruction y, otherwise continue to instruction z.
• (The numbers y and z must be between 0 and n, inclusive. Jumping to instruction n terminates the program.)”CLEAR x”: Set register x to zero and continue to the next instruction.”EQUAL x y u v”: If registers x and y contain the same value, continue to instruction u, otherwise continue to instruction v.
• (The numbers u and v must be between 0 and n, inclusive. Jumping to instruction n terminates the program.)

IDZ only contains instructions INC, DEC and ZERO, while ICE contains instructions INC, CLEAR, EQUAL.

The key part of the problem is finding a good way to simulate DEC. To do that, we can use the difference between two registers to represent one: increment one to do INC, increment the other to do DEC. 

E.g., the value A-M in the new program will correspond to the value A in the old program. 

We then translate “INC A” into “INC A ; NOP”, “DEC A” into “if not EQUAL A M then INC M” and “ZERO A” into “EQUAL A M ; NOP” (a suitable NOP is for example “INC Y”).

This way we replaced each old instruction with two new ones, so we simply double all instruction numbers in the program’s jumps.

In the end, we have the output value in C-M. We copy it to Z by doing “while not EQUAL C M: inc M, inc Z” and we are done.

    public String[] transform(String[] program) {
        int[][] machineCode = parse(program, false);
        int N = machineCode.length;
        
        int[] newOffset = new int[N+1];
        for (int n=0; n<N; ++n) newOffset[n+1] = newOffset[n] + ( machineCode[n][0] == 1 ? 2 : 1 );
        
        String[] answer = new String[ newOffset[N] + 4 ];
        for (int n=0; n<N; ++n) {
            if (machineCode[n][0] == 0) answer[ newOffset[n] ] = program[n]; // copy INC
            if (machineCode[n][0] == 1) {
                answer[ newOffset[n] ] = "EQUAL " + ((char)(65+machineCode[n][1])) + " " + ((char)(75+machineCode[n][1])) + " " + (newOffset[n]+2) + " " + (newOffset[n]+1);
                answer[ newOffset[n]+1 ] = "INC " + ((char)(75+machineCode[n][1]));
            }
            if (machineCode[n][0] == 2) {
                answer[ newOffset[n] ] = "EQUAL " + ((char)(65+machineCode[n][1])) + " " + ((char)(75+machineCode[n][1])) + " " + newOffset[machineCode[n][2]] + " " + newOffset[machineCode[n][3]];
            }
        }
        int end = newOffset[N];
        answer[end] = "EQUAL C M " + (end+4) + " " + (end+1);
        answer[end+1] = "INC M";
        answer[end+2] = "INC Z";
        answer[end+3] = "EQUAL C M " + (end+4) + " " + (end+1);
        return answer;
    }

RainbowNim

In this problem, you are given a modification on the problem of Nim. Each pile contains some number of stones with a certain color. In a single turn, a player has two types of moves

• Take any number of stones from a single pile
• Take at most m stones from piles of the same color

You would like to count the number of subsets of initial piles where the first player has a winning strategy.

To solve this, first, let’s try to find the sprague-grundy numbers (or “nimbers”) for a configuration of piles of a single color. Each color is independent, so for the original problem, we can take the XOR of all these nimbers to get the nimber for the overall game.

For a single color, we claim the nimber for piles of sizes a_1, a_2, … a_n, and a number m is equal to (xor of floor(a_i / (m+1)) * (m+1) + (sum a_i) mod (m+1). For motivation, we can think about winning states for the single color game. If the total number of stones mod (m+1) is not zero, then the first player can always guarantee a win (this is because they always have an option for a move that makes the sum equal to zero mod (m+1)). The inverse does not happen to be true, but what the original statement lets us do is say if the sum of piles is divisible by m+1, then it is only ever optimal to do moves on a single pile with a multiple of (m+1) stones, so you need to look at pile sizes divided by m+1. 

You don’t need to do this proof during a contest, but proving it actually works requires some casework, and I’ll quickly go over the high level intuition on it. First, let’s say f(a_1, a_2, …, a_n) = (xor of floor(a_i / (m+1)) * (m+1) + (sum a_i) mod (m+1).

• For any other position that we can reach from b_1, b_2, …, b_n that we can reach from a_1, a_2, …, a_n, f(a_1, a_2, …, a_n) != f(b_1, b_2, …, b_n)
• For any k < f (a_1, a_2, …, a_n), there exists some position b_1, b_2, …, b_n that we can reach with k = f(b_1, b_2, …, b_n).

For the first statement, if we do a move of the second type, the lower part of the sum must change. If we do a move of the first type, we can show if we don’t change the mod (by taking a multiple of (m+1) stones), then we must have changed the xor.

For the second statement, there are two cases

• floor(k / m+1) = xor of floor(a_i / m+1). In this case, there is some move we can do of the second type that will reduce the mod sum to any number without changing the xor part.
• floor(k / m+1) < xor of floor(a_i / m+1). In this case, we can look at regular nim wil pile sizes floor(a_i / m+1) and see that there is some pile in which we can do a move on that will reduce the xor. We can map this back to the original configuration and do a move of the first type on this pile. This move can also fix the mod (m+1 to be anything.

To get the number of winning subsets, we can do a dp where dp[x] that says how many ways are there to choose piles so that the resulting nimber is dp[x]. This results in a runtime that is O((max nimber)^2 * (number of colors)). This can be sped up even further using an FWHT convolution to combine the dp tables from different colors, but this was not needed for this problem.

import java.util.Arrays;

public class RainbowNim {
    public int MAXC = 250, MAXD = 1 << 9;
    public long mod = 998244353;

    public int combine(int x, int y, int m) {
        int ax = x % m, ay = y % m, bx = x / m, by = y / m;
        return ((ax + ay) % m) + m * (bx ^ by);
    }

    public int countSubsets(int[] pile, int[] color, int m) {
        m++;
        int n = pile.length;
        long[] dp = new long[MAXD];
        long[] tx = new long[MAXD];
        tx[0] = 1;
        for (int i = 1; i <= MAXC; i++) {
            Arrays.fill(dp, 0);
            dp[0] = 1;
            for (int j = 0; j < n; j++) {
                if (color[j] == i) {
                    long[] ndp = new long[MAXD];
                    for (int k = 0; k < MAXD; k++) {
                        if (dp[k] == 0) continue;
                        ndp[k] += dp[k];
                        if (ndp[k] >= mod) ndp[k] -= mod;
                        int t = combine(k, pile[j], m);
                        ndp[t] += dp[k];
                        if (ndp[t] >= mod) ndp[t] -= mod;
                    }
                    dp = ndp;
                }
            }
            long[] nx = new long[MAXD];
            for (int a = 0; a < MAXD; a++) {
                for (int b = 0; b < MAXD; b++) {
                    nx[a^b] += tx[a] * dp[b];
                    nx[a^b] %= mod;
                }
            }
            tx = nx;
        }
        long res = 1;
        for (int i = 0; i < n; i++) res = res * 2 % mod;
        res -= tx[0];
        if (res < 0) res += mod;
        return (int)res;
    }
}