July 8, 2022 TCO22 Round 3 Editorial
TwoDimensionalSort
Imagine that we label rows of the board A to Z from top to bottom. If we got each rook X into its row X, the board would surely be sorted.
With N rooks we can always achieve that in at most 2*N moves. In the first N moves we’ll move some rooks horizontally to make sure each rook is in a distinct column and then in the next N moves we can freely place each rook into its appropriate row.
For the first phase, let’s label columns 0 to 25 from left to right. Now, let’s go through the board in column major order (i.e., left to right and within each column top to bottom) and label the rooks 0 to N-1 in the order in which we encountered them. I.e., the rooks are numbered 0 to N-1 in their current left-to-right order, with ties broken arbitrarily.
Our goal will be to move rook number x into column x, for each x. One strategy that accomplishes this in at most N moves looks as follows:
- For each x from 0 to N-1, if rook x is in a column y > x, move it left to column x.
- For each x from N-1 down to 0, if rook x is in a column y < x, move it right to column x.
Clearly, each rook is moved at most once during the above process, and each rook ends in its correct column. The thing we need to show is that this generates a valid sequence of moves – i.e., whenever a rook needs to move, all the cells along the way are empty and so the move is valid.
Consider the first pass (from 0 to N-1). When processing rook x and finding we have to move it from column y > x to column x:
- All the rooks that haven’t been processed yet are in columns y and greater and thus they aren’t in the way.
- Each rook that already was processed is now in a column x-1 or smaller (because if it was originally in a greater column, it was in a column greater than its own number and so it already got moved).
After the pass, note that the rooks are still numbered 0 to N-1 from left to right, and so the same argument will work for the second pass (from N-1 down to 0).
Other strategies work as well. For example, we can do the whole first phase by handling the board one row at a time. Within the row, count the rooks, and if you have K rooks, pick any K columns for the rooks. Now assign the rooks (left to right) to their destinations (also left to right). Now the whole movement within the row can be done greedily: while there are some rooks that are not in their desired places, find a rook that can perform a valid move and make it.
(Proof that the above strategy works: A rook that currently cannot move must be blocked by another rook that’s in its way, and that rook must then have the same desired direction of movement. Either that rook can move or we find another rook that’s blocking it, and so on. After finitely many such steps we must eventually find a rook that can move – as we keep moving in the same direction, we can never go back to a rook we already processed.)
public int[] sortLetters(String[] board) {
// make an editable board
char[][] state = new char[26][26];
for (int r=0; r<26; ++r) for (int c=0; c<26; ++c)
state[r][c] = board[r].charAt(c);
// count the rooks
int N = 0;
for (int r=0; r<26; ++r) for (int c=0; c<26; ++c)
if (state[r][c] != '.') ++N;
ArrayList<Integer> answer = new ArrayList<Integer>();
// move all letters that are too far right to the left
{
int seen = 0;
for (int c=0; c<26; ++c) for (int r=0; r<26; ++r) {
if (state[r][c] != '.') {
if (c > seen) {
answer.add(r);
answer.add(c);
answer.add(r);
answer.add(seen);
state[r][seen] = state[r][c];
state[r][c] = '.';
}
++seen;
}
}
}
// move all letters that are too far left to the right
{
int seen = 0;
for (int c=25; c>=0; --c) for (int r=0; r<26; ++r) {
if (state[r][c] != '.') {
if (c < N-1-seen) {
answer.add(r);
answer.add(c);
answer.add(r);
answer.add(N-1-seen);
state[r][N-1-seen] = state[r][c];
state[r][c] = '.';
}
++seen;
}
}
}
// move all letters up or down to the corresponding rows
{
for (int r=0; r<26; ++r) for (int c=0; c<26; ++c) {
if (state[r][c] != '.') {
int newr = state[r][c] - 'A';
answer.add(r);
answer.add(c);
answer.add(newr);
answer.add(c);
}
}
}
int[] finalAnswer = new int[answer.size()];
for (int i=0; i<answer.size(); ++i) finalAnswer[i] = answer.get(i);
return finalAnswer;
}
TwoMazeAlgorithms
It’s probably not too surprising that for large values of D it is much easier to tell which generator produced a given maze. Essentially any parameter that seems different when looking at the mazes also turns out to be different enough when actually computed and compared.
For example, one really simple characteristic is the number of crossroads (i.e., rooms with more than two removed walls). The DFS-generated mazes tend to have fewer crossroads and longer corridors while the MST-generated mazes have more crossroads and shorter corridors. Already for D=10 the number of crossroads in a DFS maze has (mean, stdev) approximately (9.8, 1.8) while for MST mazes it’s approximately (25.1, 2.4). If we take a cutoff somewhere in the middle between the two means, e.g., at 16 crossroads, we’ll only classify about one in 10,000 mazes incorrectly. For D > 10 the gap gets bigger and the misclassification rate goes even further down.
A much stronger and more deterministic observation is that while the MST algorithm can generate any theoretically possible maze (if its edges happen to be the ones that are assigned the smallest weights), the DFS algorithm’s outputs are very restricted. In most cases we can look at a maze and say that it cannot have been generated by the random DFS. The key observation here is that DFS cannot return from a vertex if it still has an unexplored neighbor at that point.
For example, examine this maze:
###########
#...#.....#
###.###.###
#.......#.#
#.#.###.#.#
#.#...#.#.#
#.###.#.#.#
#.#...#...#
#.#.###.#.#
#.#...#.#.#
###########
Can it be a DFS maze? No, it cannot. Here’s one possible argument why:
###########
#...#.....#
###.###.###
#.......#C#
#.#.###.#C#
#.#...#.#C#
#.###.#.#C#
#.#...#ACC#
#.#.###B#C#
#.#...#B#C#
###########
If we suppose this maze was generated by a random DFS, that algorithm at some point entered room A, then it generated the parts labeled B and C in some order, and then it left the subtree rooted at A. But this is clearly impossible. If the DFS had started with part B, the one room labeled B would still have an unexplored neighbor (the lowestmost C in our figure) and thus the DFS would have gone there before returning from room B. And vice versa: if the DFS generated the C part before the B part, at some point it had to leave the bottommost C and this is again a contradiction – at that moment the B room wasn’t visited yet and so the DFS should have gone there.
For D < 10 we don’t have to think about details of an algorithm that would test the above property efficiently, we can easily use brute force instead. If we get a maze that cannot have been produced by any DFS, we are certain that it was generated by MST. And the mazes that are actually valid DFS mazes form such a small fraction of all mazes that whenever we see a valid DFS maze it is very likely that it was actually generated by DFS – it’s very unlikely that we would stumble upon such a maze by using
the other algorithm.
(Already for the invalid D=3 only 14 out 192 mazes are DFS mazes. For the smallest valid D=4 there are 322 valid DFS mazes while over 100,000 mazes total, so out of the <=600 mazes generated by MST about two should be valid DFS mazes. This is well within the given tolerance.)
KingdomSplit
The split can always be done.
Handling a blue-red split is easy if we can already handle a blue-blue split. Just take the original kingdom, add a dummy vertex, connect it to all others, do a blue-blue split and then discard the dummy vertex. The induced subgraph from which you discarded the dummy vertex now has all degrees odd, so you have a valid blue-red split.
Handling self-loops and multiple edges is easy: self-loops can be discarded without changing anything and so can pairs of identical multiple edges. We can go over the input once and do this while converting it into an adjacency matrix of a simple graph.
Finding a valid blue-blue split can be done by solving a suitable system of linear equations modulo 2. Below, we will first explain an alternate solution that also proves that a solution always exists, and then we’ll give the easier approach via Gaussian elimination.
A recursive construction that is guaranteed to work
If at any moment our graph has all degrees even, we split it into everything and nothing, and we are done.
Suppose we have a vertex X in our graph such that the degree D of X is odd. Imagine that we removed X from the graph and we did a blue-blue split of the rest of the graph. This would give us two parts A and B. As D is odd, X has an even number of neighbors in one part and an odd number of neighbors in the other part. Without loss of generality, suppose A is the part with the even number of X’s neighbors.
If we add X to the part A where it has an even number of neighbors, it will be happy. This is almost a valid solution. The only issue is that now the neigbors of X in A have odd degrees.
Thus, in order for the above construction to work we need something else from the recursive call: not exactly a blue-blue split, but an almost blue-blue split in which precisely X’s neighbors in A have odd degrees.
Here’s the main trick of this solution: observe that this can be achieved as follows:
- Remove X from the graph.
- For each pair of neighbors of X, toggle the edge between them (i.e., remove it if it’s there and add it if it isn’t).
- Now do the blue-blue split recursively.
- In each of the two subgraphs, toggle the remaining neighbor-neighbor edges back to their original state.
- In subgraph A (the one with 2k neighbors of X, for some k) we toggled 2k-1 edges from each neighbor, so the degree of each neighbor is now odd.
- In subgraph B (the one with 2k+1 neighbors of X, for some k) we toggle 2k edges from each neighbor, so the degree of each neighbor remains even.
- Thus, subgraph B is a valid blue subgraph, subgraph A becomes a valid blue subgraph when we add X to it, and we are done.
int N;
boolean[][] G;
boolean[] alive;
boolean[] adam;
// solve() does a blue-blue split of the vertices that are still alive
void solve() {
// calculate current degrees and find an odd vertex
int[] degree = new int[N];
int odd = -1;
for (int a=0; a<N; ++a) if (alive[a]) {
for (int b=0; b<N; ++b) if (alive[b]) if (G[a][b]) ++degree[a];
if (degree[a] % 2 == 1) odd = a;
}
// if there are no odd vertices, make the all-nothing split
if (odd == -1) {
for (int n=0; n<N; ++n) if (alive[n]) adam[n] = true;
return;
}
// remove the odd vertex, toggle edges between its neighbors
alive[odd] = false;
int[] neighbors = new int[degree[odd]];
for (int n=0; n<N; ++n) if (alive[n])
if (G[odd][n]) neighbors[--degree[odd]] = n;
int L = neighbors.length;
for (int i=0; i<L; ++i) for (int j=i+1; j<L; ++j) {
int x = neighbors[i], y = neighbors[j];
G[x][y] = !G[x][y];
G[y][x] = !G[y][x];
}
// recursively make the blue-blue split of the rest
solve();
// attach the odd vertex to the correct part
// (we don’t need to actually toggle the edges back)
int adamNeighbors = 0;
for (int x : neighbors) if (adam[x]) ++adamNeighbors;
if (adamNeighbors % 2 == 0) adam[odd] = true;
}
public int[] split(String eyes, int _N, int[] X, int[] Y) {
// simplify the graph and add a dummy vertex if Booboo has red eyes
N = _N;
if (eyes.equals("red")) ++N;
G = new boolean[N][N];
for (int i=0; i<X.length; ++i) {
int x = X[i], y = Y[i];
if (x == y) continue;
G[x][y] = !G[x][y];
G[y][x] = !G[y][x];
}
if (eyes.equals("red")) {
for (int i=0; i<N-1; ++i) G[i][N-1] = G[N-1][i] = true;
}
// find a blue-blue split
alive = new boolean[N];
for (int n=0; n<N; ++n) alive[n] = true;
adam = new boolean[N];
solve();
// take the part that is guaranteed to not contain the dummy vertex
if (adam[N-1]) for (int n=0; n<N; ++n) adam[n] = !adam[n];
int cnt = 0;
for (boolean x : adam) if (x) ++cnt;
int[] answer = new int[cnt];
for (int n=0; n<N; ++n) if (adam[n]) answer[--cnt] = n;
return answer;
}
A solution using equations
Let G[i][j] = 1 if i-j is an edge and 0 otherwise. In other words, G is the adjacency matrix of our graph.
Suppose we have a binary variable a[i] for each vertex i. The variable should be 1 if Adam should get this vertex, or 0 if Booboo should get it. For each vertex we now want to formalize the following statement: “this vertex should have an even number of neighbors in its component”.
Let’s pick a fixed vertex V and let’s consider two cases: the degree of V is either odd or even.
If the degree of V is even: regardless of whether a[V] is 1 or 0, we need V to have an even number of neighbors of the same type, but that also means an even number of neighbors of the opposite type. Thus, we can simplify the condition to “an even number of neighbors should have a[w]=1”, and when computing modulo 2 this gives us the following linear equation:
even V: sum( a[w] * G[V][w] ) = 0, where the sum goes over all neighbors w of the vertex V.
Similarly, if the degree of V is odd we can proceed as follows. Let’s add V to the set of its neighbors. Now we again have a set of an even size. If a[V] = 1, we need an even number of additional 1s and thus the sum has to be odd. And if a[V] = 0, we need an even number of additional 0s. This means that the total number of 0s is odd, and thus the total number of 1s is also odd and again the sum should be 1. Thus, for odd V we get a slightly different equation:
odd V: sum( a[w] * G[V][w] ) = 1, where the sum goes over the vertex V itself and all neighbors w of the vertex V.
Solutions of this system of equations correspond precisely to valid ways to make a blue-blue split.
misof
