November 16, 2018 TCO Semifinals 1 Editorial

The competitors of this round are ACRush, Egor, Errichto, Marcin_smu, mjhun, tourist, Um_nik, and Vasyl[alphacom]. The easy is a simple constructive problem with a tricky edge case when the number of rows or columns is small. The medium is also a constructive problem that is the reverse of a classic problem. Finally, the last is a counting problem that requires a few observations to get it to run fast enough.
Congratulations to the advancers:

1. tourist
2. Errichto
3. Um_nik
4. ACRush

Lilypads (misof):

For this problem, we are given a 2D grid, where each grid cell contains a lilypad. We have a frog that can jump in any of the four cardinal directions (i.e. up, down, left, right) arbitrarily far away. We are given the initial location of the frog, and we would like to find any sequence of jumps that visits all lilypads exactly once, given that the frog cannot jump in the same direction more than once.
There are many different approaches to this problem.
One way is that we can solve this row by row. We can solve a single row from any starting position by repeatedly jumping to the leftmost and the rightmost unvisited cell. (If we start at the left end, the first jump has to be to the rightmost cell.)
Then, we can do a jump up or down to any unvisited row to continue. However, this approach might be incorrect when we have exactly one column (since we may be doing multiple jumps in the same direction if we are not careful).
To get around this, one way is to solve for rows and columns independently. Two 1D solutions can be used to construct a 2D solution. For instance always solve your whole current row according to the row sequence (alternately using it forwards and backwards) and then jump to the next column according to the column sequence.
For example, refer to the following picture. We have two 1-d solutions in grey, and the combination of the two solutions in the middle. Arrows are alternating colors for clarity.

This can be implemented with the sample code:

import java.util.*;
public class Lilypads {
    public int[] traverse1D(int R, int r0) {
        boolean[] visited = new boolean[R];
        for (int r=0; r<R; ++r) visited[r] = false;
        visited[r0] = true;
        int[] answer = new int[R];
        answer[0] = r0;
        boolean nextLeft = true;
        if (r0 == 0) nextLeft = false;
        for (int n=1; n< ++n) {
            int x;
            if (nextLeft) {
                x = 0; while (visited[x]) ++x;
            } else {
                x = R-1; while (visited[x]) --x;
            }
            answer[n] = x;
            visited[x] = true;
            nextLeft = !nextLeft;
        }
        return answer;
    }
    public int[] traverse(int R, int C, int r0, int c0) {
        int[] rows = traverse1D(R,r0), cols = traverse1D(C,c0);
        int[] answer = new int[2*R*C];
        for (int r=0, n=0; r< ++r) for (int c=0; c< ++c) {
            answer[n++] = rows[r];
            answer[n++] = (r%2 == 0 ? cols : cols[C-1-c]);
        }
        return answer;
    }
};

DominoTiling (Alex_2oo8):

You are given a number up to . You would like to construct a 2d board with a small number of rows so that the number of domino tilings in the board is exactly . Some of the grid cells can be blocked, but you need to make sure that the unblocked part remains connected.
There are many possible solutions. We will show two of them.
Our first solution is based on the observation that a 2×2 square has 2 tilings, and thus a connection of n independent 2×2 squares has 2^n tilings. Of course, our area has to be connected, but that’s really easy to accomplish. Below is a board with 2^5 tilings.

..................
..##..##..##..##..

Now that we can create a valid board for each power of two, all we need is an “add” operation to construct a board with any general number of tilings. We will show this operation in the next solution. Instead, we will produce a more compact version. First, convince yourself that the following board has 2^5 + 1 tilings, as the loop adds exactly one new tiling:

.....................
.###################.
.###################.
.....................
..##..##..##..##..###

The board below has 2^5 + 2 tilings: 2 tilings for the left four columns, multiplied by 2^4 + 1 tilings for the rest.

####.................
####.###############.
####.###############.
.....................
..##..##..##..##..###

One final board we will show you is the following one, with 2^5 + 3 tilings. This should give you enough to be able to generalize the pattern.

.....................
.###.###############.
.###.###############.
.....................
..##..##..##..##..###

Our second solution will be based on the “add” operation we mentioned above and on another class of boards that have nice numbers of tilings. It is easy to show that for any n, the 2xn rectangle has F_{n+1} tilings, where F are the Fibonacci numbers. These grow exponentially. Below we show a pattern with 21 + 21 + 3 tilings. Note that the rectangles in the middle two rows have 21, 21, and 3 tilings.

...................
######.#######.###.
.......#.......#...
.......#.......#...
.#######.#######.##
...................

This can be generalized to any collection of odd-length rectangles. Hence, given any n we can do the following: greedily write n as a sum of (not necessarily distinct) even-indexed Fibonacci numbers, take the corresponding rectangles, and add the pattern that forces you to tile exactly one of them. This produces a pattern with O(log^2(n)) columns, as the sum will have O(log(n)) Fibonacci numbers and each of them will produce a rectangle with O(log(n)) columns.
This is a solution for the first method

unsigned logceil(long long x) {
    return x ? 8*sizeof(ll)-__builtin_clzll(x) : 0;
}
struct DominoTilings {
    vector<string> solve(long long n) {
        int s = logceil(n)-1;
        vector<string> S(5, string(4*s+1, '#'));
        for (int i = 0; i < s; ++i) {
            S[0][4*i] = S[0][4*i+1] = S[0][4*i+2] =
            S[0][4*i+3] = S[3][4*i] = S[3][4*i+1] =
            S[3][4*i+2] = S[3][4*i+3] = S[4][4*i] =
            S[4][4*i+1] = '.';
        }
        S[0][4*s] = S[1][4*s] = S[2][4*s] = S[3][4*s] = '.';
        for (int i = 0; i < s; ++i) {
            if (n & (1LL<<i)) {
                S[1][4*i] = S[2][4*i] = '.';
            }
        }
        return S;
    }
};

This is a solution for the second method

def solve(self, N):
    	fib = [0,1]
    	for _ in range(2,100): fib.append( fib[-1] + fib[-2] )
    	fibrepr = []
    	for n in range(98,0,-2):
        	while N >= fib[n]:
            	fibrepr.append(n-1)
            	N -= fib[n]
    	second_row = '#'.join([ '#'*(n-1)+'.' for n in fibrepr ])
    	middle_row = '#'.join([ '.'*n for n in fibrepr ])
    	fifth_row  = '#'.join([ '.'+'#'*(n-1) for n in fibrepr ])
    	empty_row  = '.'*len(second_row)
    	return [empty_row, second_row, middle_row, middle_row, fifth_row, empty_row]

FillInTheGraph (lg5293):

In this problem, we are given a directed graph. We would like to color the nodes of this graph so the following conditions are satisfied
– Each node is a color between and .
– For each i between and , if there is any node with color , then there must be at least one node with color that has an edge pointing to some node with color .
Two colorings are different if there exists a node with a different color in both colorings. The task is to count the number of colorings.
Let’s come up with a dp. We will first select which nodes get the number 1, then the nodes with number 2, and so on. In order to count these, we will have a dp that has states. The states are (a mask of nodes that already have a number, a mask of nodes that received the last number). In order to solve a given state we can iterate through all subsets of unlabeled nodes, check if the last group has at least one edge to this subset, and update our dp table if so.
The above runs in because whenever we try to label some new nodes, each node is in one of four states (colored long ago / colored in previous step / being colored / being left uncolored).
To speed this up, we can speed up the step of iterating through all subsets of the free nodes.
Instead of summing over subsets of free nodes that have at least one edge from the last group, let’s instead subtract from the total the number of subsets of free nodes that have no edges to the last group. This simplifies the problem by a little bit, since any subset of bad nodes must necessarily be a submask of the complement of nodes adjacent to the last group. So, this reduces to maintaining a subset sum for a fixed mask of nodes that have been taken. Thus, this reduces the overall running time to .
Example code below. In the implementation below, I add the two masks in base 3 which doesn’t overflow in each digit. Otherwise, you might need to compress the submasks into an array to get it to run fast enough.

public class FillInTheGraph {
    public int count(int n, int[] a, int[] b) {
        int m = a.length;
        int[] outes = new int[1<<n];
        for (int mask = 0; mask < 1 << n; mask++) {
            for (int i = 0; i < m; i++) {
                if (((mask>>a[i])&1) == 1)
                    outes[mask] |= 1 << b[i];
            }
        }
        int len = 1;
        for (int i = 1; i <= n; i++) len *= 3;
        int[] dp = new int[len];
        dp[0] = 1;
        int[] ss = new int[1<<n];
        for (int use = 1; use < 1 << n; use++) {
            ss[use] = ss[use>>1] * 3 + (use&1);
            for (int sub = 0; (sub = (sub - use) & use) != 0; ) {
                int msk = ss[use] + ss[sub];
                int d = use ^ sub;
                int need = outes[sub]&d;
                dp[msk] = dp[ss[d] + ss[d^need]];
            }
            for (int i = 0; i < n; i++) {
                if (((use>>i)&1) == 1) {
                    for (int sub = 0; (sub = (sub-use)&use) != 0; ) {
                        if (((sub>>i)&1) == 1) {
                            int msk = ss[use] + ss[sub];
                            dp[msk] += dp[ss[use] + ss[sub^(1<<i)]];
                            if (dp[msk] >= mod) dp[msk] -= mod;
                        }
                    }
                }
            }
            dp[ss[use]] = dp[ss[use]<<1];
            for (int sub = 0; (sub = (sub - use) & use) != 0; ) {
                int msk = ss[use] + ss[sub];
                dp[msk] = dp[ss[use]<<1] - dp[msk];
                if (dp[msk] < 0) dp[msk] += mod;
            }
        }
        return dp[ss[(1<<n)-1]];
	}
}