August 19, 2021 TCO Wildcard Elimination Rounds

Round 1 200: FindStringBetween

Valid strings are strings of length at most L of lowercase letters. We are given two valid strings A and B, and we are asked to find any one valid string C such that A<C<B, or say that such a string does not exist.

In the round the task has seen a bunch of resubmissions and then still a bunch of failures by many of the top competitors, so it clearly isn’t as easy as it seems. It pays off to be careful.

Our approach will be as follows:

• If A >= B, there is clearly no solution.
• Now that we know that A < B, there are some valid strings lexicographically greater than A. Let succ(A) be the successor of A in the sorted list of all valid strings. We will construct succ(A). If succ(A) < B, it’s a valid answer, otherwise we know that a valid answer does not exist.

What does succ(A) look like? If |A| < L, then succ(A) = A + ‘a’. And if |A|=L, we can construct succ(A) as follows:

1. While the last letter of A is ‘z’: remove it.
2. Increment the last letter of A.

For example, succ(“buzz”) = “bv”.

(Note that the order in which we made the previous steps guarantees that A does not consist of ‘z’s only, so step 1 will eventually terminate and A will still be non-empty. This was one of the spots where it was really easy to make a mistake in the implementation.)

public String generate(int L, String A, String B) {
    if (A.length() < L) {
        String C = A + 'a';
        if (C.compareTo(B) < 0) return C;
        return "ERROR";
    } else {
        int n = L;
        while (A.charAt(n-1) == 'z') --n;
        String kept = A.substring(0, n-1);
        char increase = A.charAt(n-1);
        ++increase;
        String C = kept + increase;
        if (C.compareTo(B) < 0) return C;
        return "ERROR";
    }
}

Round 1 500: ExamSeating

The task: Given a collection of letters, choose the dimensions R, C <= 50 of a rectangle and place all the letters into the rectangle in such a way that no two equal letters are horizontally or vertically adjacent. Some cells may remain empty. Minimize the area of the rectangle.

Let N[x] denote the number of copies of letter x we have.

There are two necessary conditions for an RxC rectangle to be a valid choice:

• We must fit all letters inside the rectangle: sum(N) <= R*C.
• We must fit all letters x into the rectangle in such a way that no two touch.

The second condition is satisfied if and only if max(N) is at most ceil(RC/2). Proof: if RC is even, we can tile the entire rectangle using RC/2 dominoes. If RC is odd, we can do the same and have a single cell left over. Each domino can contain at most one letter of the type that has the most occurrences.

We will now show that these two conditions together are not just necessary but also sufficient for a solution to exist.

Main claim: Among all valid rectangles whose area satisfies the above conditions, let’s pick the one with the smallest area, and in case of a tie the one with most rows. This rectangle can always be filled correctly.

Constructive proof: We will fill the letters in using the following algorithm:

1. Let x be the letter with the most occurrences. Going row by row from the top to the bottom, place x onto “black” cells = those with even sum of coordinates.
2. Let y be the letter with the second most occurrences. Going row by row from the bottom to the top, place y onto the “white” cells.
3. Going row by row from the top to the bottom, each time you encounter an empty “black” cell, place the smallest available letter.
4. Going row by row from the top to the bottom, each time you encounter an empty “white” cell, place the smallest available letter.

We can now argue as follows:

• We know that we have enough black cells to fit all x.
• We can easily verify that we have enough while cells to fit all y.
• Each letter except for at most one has all its occurrences on squares of the same color, and therefore no two are adjacent.
• There can be one letter z such that its occurrences are on black cells (in the last few rows of the rectangle) and then also on white cells (in the first few rows of the rectangle). We need to make sure the bottom white ones cannot touch the top black ones.

Let’s look at that last claim in detail. If rectangle area is at most 50, we have picked a rectangle with 1 column and the claim is obvious. Otherwise, as by symmetry R >= C, our rectangle clearly has at least 8 rows. As N[z] <= N[x] and N[z] <= N[y], we know that N[z] <= RC/3. Each pair of consecutive complete rows has C occurrences of a letter, and thus all occurrences of z will be in at most 2R/3 + 1 < R consecutive rows. Thus, there are always some rows with no z between the top (white) and bottom (black) set of zs.

To conclude this solution, we note that the simpler strategy given below sometimes fails. Can you find an input where it produces an invalid solution? Hint: make a “black” and a “white” copy of the same letter touch.

1. Sort the letters by number of occurrences in decreasing order.
2. Going row by row from the top to the bottom, each time you encounter an empty “black” cell, place the letter of the first type that is still available.
3. Going row by row from the top to the bottom, each time you encounter an empty “white” cell, place the letter of the first type that is still available.

Round 2 200: HangmanSolver

We are essentially implementing a simple routine that can check whether a given string can be the solution to a partially-played game of Hangman. There is essentially only one catch that we should not miss: each time we guess a letter, all copies of that letter are revealed. Thus, if the word we are guessing is ?????a, this cannot be “banana”, because we know that the second and fourth letter cannot be ‘a’.

The sample implementation shown below avoids all complicated deductions by simply implementing a function that simulates the game for a given hidden word. We then try each of the candidate answers as the hidden word, feed in the set of guessed letters and compare whether the revealed part of the word exactly matches the one we actually see.

public String show(String secretWord, String lettersGuessed) {
    String answer = "";
    for (char c : secretWord.toCharArray()) {
        if (lettersGuessed.indexOf(c) == -1) {
            answer += '_';
        } else {
            answer += c;
        }
    }
    return answer;
}

public String guess(String lettersGuessed, String revealed, String[] possibleAnswers) {
    String answer = "";
    int countMatching = 0;
    for (String candidate : possibleAnswers) {
        if (revealed.equals( show( candidate, lettersGuessed ) )) {
            ++countMatching;
            answer = candidate;
        }
    }
    if (countMatching == 1) return answer; else return "";
}

Round 2 500: CoverSquare

Given are square blankets with total area at least 3. Can we cover a unit square completely? The sides of each square are be parallel to coordinate axes.

One strategy that always works looks as follows: Sort the blankets in decreasing order. Then, repeat the following: take blankets until you get total width >= 1. Let S be the side of the last blanket taken. Use these blankets side-by-side to cover an S times 1 rectangle of the unit square (and pretend their other parts don’t exist, i.e., treat the rest of the square as uncovered).

Below, in the top part of the figure, is what a covering by this strategy may look like. The unused parts of squares that are in the vertical strip with the square are shown in red, the unused parts outside this strip are shown in yellow. Note that if there is an incomplete last row of squares, it’s all in red, in all other rows only the part that overlaps the previous row is red.

We now claim that this strategy always covers the whole square.

Proof: If there is a blanket with side 1 or more, the first blanket is already enough. Otherwise, suppose the total height of all fully-covered rows is H, as shown in the figure above. We can now argue as follows:

• The total covered area is 1*H.
• The total wasted area shown in yellow is less than 1*H (its height is H and its width is less than 1 everywhere).
• The total wasted area shown in red is at most 1. This is because if we do what’s shown in the figure below (move all rows of squares so that they share the same bottom), we see that the wasted area in different rows does not overlap. This is because if the last square in some row has side S, all wasted area in that row is at height S and more, while all wasted area in the next row is at height at most S (above the corresponding row’s bottom).

Thus, the total area of all blankets is less than 1+2H. And as we know that the area is at least 3, it follows that H is more than 1, i.e., the entire square is covered.

Final Round 200: MinimizeSortedness

There is a well-known mathematical puzzle: show that from any sequence of distinct elements of length n^2 + 1 we can select either an increasing or a decreasing sequence of length at least n+1. The construction asked for in this task is a constructive proof that this bound is as tight as possible.

If we are told that both LIS and LDS should have length at most n, the maximum length of our sequence is at most n^2.

On one hand, if we have at most n^2 elements, we can create a valid sequence as follows: sort the elements into increasing order, divide them into blocks of length n (the last block is shorter if necessary) and reverse each block. Clearly, each decreasing sequence must be contained in a single block and each increasing sequence can contain at most one element from each block.

On the other hand, suppose we have a sequence and we go through that sequence from the left to the right. For each index n we will write two numbers I[n] and D[n]: the length of the longest increasing sequence and the longest decreasing sequence that ends at index n.

For any sequence of distinct elements the pairs (I[n], D[n]) must all be distinct: we cannot have (I[n], D[n]) = (I[m], D[m]) for some n<m. This is because the element at index m is either greater than the element at index n (in which case we can find a longer increasing sequence that ends at index m by appending that element to the longest sequence ending at index n) or vice versa (in which case we can extend the decreasing sequence).

Thus, we just need to find the smallest n such that n^2 is greater than or equal to the length of the given sequence, and then we do the construction with reversing blocks of length n, as described above.

public int[] permute(int[] sequence) {
    int N = sequence.length;
    Arrays.sort(sequence);
    int ceilsqrt = 1; 
    while (ceilsqrt * ceilsqrt < N) ++ceilsqrt;
    for (int i=0; i<N; i+=ceilsqrt) reverse( sequence, i, Math.min(N,i+ceilsqrt) );
    return sequence;
}

Final Round 500: ManhattanSnowPlow

This problem is a special case of a problem called the Chinese Postman Problem. (Etymological note: the name should be read as “a Chinese problem about a postman”, not as “a problem about a postman in China”.) This problem is a generalization of the Euler tour: we want to find the shortest walk that traverses each edge of the given graph at least once.

Clearly, if our graph is Eulerian, an Euler tour is the optimal solution. Now, suppose we have a connected graph with 2k vertices of an odd degree (“odd vertices”) for some k > 1. Take any optimal solution. For each edge of the graph, color its first appearance blue and the others red. It can be shown that the red edges must form k-1 edge-disjoint paths, each connecting two odd vertices. And vice versa, we can take any such collection of paths and turn it into a valid solution by realizing that once we duplicate the edges of each path in our collection, we obtain an Eulerian graph. Thus, the extra cost paid by the optimal solution is the minimum cost of such a collection of k-1 paths.

This is solvable for general graphs in polynomial time: we can compute all-pairs shortest paths and then we are looking for the minimum cost matching of size k-1. However, the algorithm to do that in general is quite complicated.

Probably the easiest approach to solving this problem is to use the very specific structure of our problem to construct the cheapest matching explicitly, duplicate the corresponding edges, and then to use a general Euler tour algorithm to construct the snow plow program itself.

If we have a RxC grid, all odd vertices are on its sides: R-2 on each vertical side and C-2 on each horizontal side. As they are next to each other, we will usually take two neighbors and connect them by a path of length 1.

The cheapest set of paths that connects all but two odd vertices in a grid looks as follows:

• If both R and C are even, we can make pairs along each side separately. The last two odd vertices will remain unpaired, they will be the start and the end of the snow plow’s tour. This is clearly optimal: each path has length 1.
• If one of R and C is even and the other odd: we connect all pairs on the even-length sides and we leave one unpaired odd vertex on each odd-length side. Again, clearly optimal.
• If both R and C are odd, after we make some length-1 paths, we must still have at least one unpaired odd vertex on each side. As we need to pair at least two of them, we need to have at least one path of length at least 2. And that is also sufficient: we connect two odd vertices that are both neighbors of the same corner of the grid by a path of length 2, then we pair up everything else on those two sides, and finally we leave one unpaired odd vertex on each of the other two sides.