June 9, 2021 Single Round Match 806 Editorials

SudokuTypo

There are MANY different ways to solve this problem, and they can have VERY different amounts of code. This is definitely one of the problems where it pays off to stop and think before we start coding.

For example, we may observe that we don’t have to do anything with columns and 3×3 squares, those can safely be ignored. All information we need can already be determined by looking at the rows. Exactly one of the rows is broken, and that row will have the bad value twice and the good value (the one we should return) is the one that’s missing from that row. (If we had to say where exactly is the incorrect cell, we would also need to examine the columns, but we just need the value and for that we don’t need to do so.)

And we can do even better than that. There’s no need to divide the input into rows and process each row separately. In the correct sudoku each digit appears 9 times. If we change one digit into an incorrect one, the incorrect one now has 10 appearances while the correct one has only 8. Thus, we can simply find and return the value that has fewer than 9 occurrences in the given array.

LimitedDifferences

The key to an easy solution is to find a simple pattern that will allow us to create an arbitrary number of distinct differences.

One way to discover such patterns is to think about extremes. As we are shown in one of the examples, having the smallest number of differences is easy: just go with step 1. So let’s look at the opposite end: what is the maximum number of distinct differences? If we want to have N-1 distinct differences, we need to use all numbers from 1 to N-1, each of them exactly once. And using the number N-1 means that in our sequence the values 1 and N have to be next to each other.

We also need a difference of N-2. That can be between 1 and N-1, or between N and 2. Either option works, the second one is nicer. So, let’s take that one. Now we have a piece of a sequence that starts {1, N, 2}. How shall we continue? Well, exactly in the same way, always making the next largest jump: {1, N, 2, N-1, 3, N-2, …}

And what to do in the general case? We can simply combine those two approaches. For example, if I have N=12 and I want V=4 distinct differences, I can start {1, 12, 2, 11}. At this moment I have used the differences 11, 10 and 9, so I have three distinct differences. My last difference will then always be the difference 1, and I’ll use it to fill the remaining values into the sequence: {1, 12, 2, 11, 10, 9, 8, 7, 6, 5, 4, 3}.

In general, we will first use the V-1 biggest possible differences once, and then the difference 1 for the rest. Note that as we were jumping from smallest to largest and back, the unused values always formed a contiguous segment, which is why we can always switch to difference 1 and finish the construction.

TransposeColors

In the initial grid we have N*N tokens. Out of them, N (the ones on the main diagonal) already have the color we want in that position, and the remaining N(N-1) tokens don’t.

For N = 1 we are already done. In all other scenarios we need to make at least one move.

The very first move must be the move of a token onto the extra location. After this move, we still have at least N(N-1) tokens which are not in their correct column, and therefore we’ll need at least N(N-1) additional moves. In other words, the optimal solution must have at least N(N-1) + 1 moves. And at this point probably everybody already suspects that this lower bound can actually be reached – so we are looking for a solution that moves each incorrectly placed token exactly once.

To do that, a necessary condition is that whenever we are putting a token into the array, we must always put it into the correct column. However, this condition is not sufficient, we need to pay attention so that we don’t get to the situation where the only misplaced token of the color we need is the one on the temporary space. If that happens before we have swapped everything else, we will need to waste one more move swapping some other token away from the array, and thus we will use too many moves in total.

You may now think that this resembles those puzzles where you have to draw a picture in one continuous stroke – if you take a wrong turn and end up where you started too early, there are still some parts of the picture you haven’t drawn. If you did make this observation, you were certainly on the right track. One possible way of making sure that we move all tokens is to visualize the situation as a graph: colors are vertices, each token that needs to be moved is a directed edge from its color to the color whose place it occupies. Then, valid sequences of swaps correspond to Euler tours in this graph.

Of course, given that we essentially have a complete graph (one pair of tokens for each pair of colors), we don’t have to use a general Euler tour algorithm to find a good sequence of swaps. Instead, we can simply find some specific sequence of swaps that works for inputs of this special type only.

Below we describe one possible deterministic pattern of swaps that makes sure we don’t forget anything. This is just one of many possible solutions.

We will write a function that will start with a grid in a state like this:

AAAAA
BBBBB
CCCCC
DDDDD
.EEEE

and it will transform it, using an optimal number of moves, into a state like this:

ABCDE
ABCDE
ABCDE
ABCD.
ABCDE

For N=2 this requires just a single move: the A from the top right corner goes to the bottom left corner. For larger values of N we will solve the problem recursively. We will start by moving the values from the rightmost column to the bottommost row and vice versa:

AAAAA  AAAA.  AAAAE  AAAAE  AAAAE  AAAAE  AAAAE
BBBBB  BBBBB  BBBBB  BBBB.  BBBBE  BBBBE  BBBBE
CCCCC  CCCCC  CCCCC  CCCCC  CCCCC  CCCC.  CCCCE
DDDDD  DDDDD  DDDDD  DDDDD  DDDDD  DDDDD  DDDDD
.EEEE  AEEEE  A.EEE  ABEEE  AB.EE  ABCEE  ABC.E

Once we get to letter N-1, we do something slightly different: now we will move the leftmost of those letters into the empty space:

AAAAE
BBBBE
CCCCE
.DDDD
ABCDE

The top left (N-1) x (N-1) square is now exactly in the same setup we need, so we will make a recursive call to make all the swaps in this area. Once those terminate, we are left with this:

ABCDE
ABCDE
ABC.E
ABCDD
ABCDE

and now all that’s left to do is to place the last token of color N-1 into its place and we are done.

MostSubstrings

For this task a painless way to a good solution is to resist the temptation to try going greedy and analyzing various patterns in which copies of a string can overlap. Instead, we will go for dynamic programming.

Imagine the finite automaton that looks for occurrences of a specific needle of length N in its input. The states of this automaton correspond to all N+1 possible prefixes of the needle. Whenever we read the next character from the input, the new state is always computed as the longest prefix of needle that can appear as the suffix of the string we read from the input.

For example, if we are looking for the string “abacaba” and we are in the state “aba”, reading ‘c’ puts us into “abac”, reading ‘b’ puts us into “ab”, reading ‘a’ puts us into “a”, and reading any other character puts us into the state “”.

If our old state was “aba”, it means that the input read until then ends in “…aba”. After the next character ‘b’ we see that now it ends in “…abab”. At this moment, the most optimistic conclusion is that the last two characters of input are the first two characters of our needle. In general, the new state after reading x in an old state is the largest suffix of (old state + x) that is a prefix of the needle.

(This is essentially the same thing the KMP algorithm does.)

We will start by precomputing the transitions of this automaton. As everything is reasonably small, we can do so using a lot of brute force.

Once we have it, we can now iterate over all string lengths from 0 to the given length L. For each length, we will divide all possible strings of this length into groups according to two things: in which state of the automaton do we end after reading the string, and what is the number of needles it already contained. Clearly, once we know these two things about a string, we can tell how they change after we append the next letter, so all strings of the same type can be bundled together.

One final observation we can now make is that for each state of the automaton we are only interested in strings that reach it and have the largest possible number of matches. This is because from those other strings we can never make a string with the most occurrences of our needle: if you append the same suffix to two strings that are currently in the same state of the automaton, you will get the same number of additional occurrences of the needle.

Thus, for each of the L lengths we are only maintaining 2*(N+1) values: for each state the maximum number of occurrences of the needle among all strings that end in this state, and the number of such strings.

In the end, we sum the strings with the most occurrences of the needle over all states of the automaton.

SevenSegmentDisplayNim

Losing positions in this game are rather sparse. They all look as follows:

   *---x---*
   |       |
   x       x
   |       |
   *---y---*   (x xor y xor z) = 0
   |       |
   z       z
   |       |
   *---z---*

Once we discover this (e.g., by examining all losing positions with a small numbers of pebbles and looking for patterns similar to a standard game of NIM), the proof should not be that difficult. We give it below.

Once we know for sure that these are precisely our losing positions, we can count all of them. The constraints were fairly kind and allowed use of reasonable brute force to do that. For example, you could determine the allowed intervals for x, y, z and then iterate over all options for x,y and each time check whether (x xor y) falls into the allowed range for z. (Of course, if you like symmetry, you’ll probably iterate over options for x and z and then compute the corresponding y.)

In order to show that the set of positions above (let’s call them “red positions”) are the losing positions of this game, we need to show two things: that all moves from a red position lead to other (“blue”) positions, and that for each blue position there is a move to a red position.

The first part is obvious: the only way to change a red position into another red position is to change exactly all the edges from two or three groups (e.g., all x and y edges) to new values – but that is not allowed as those edges form a cycle.

For the second part, let’s distinguish two cases:

• Suppose we have a configuration of the red type but the xor of the three values is non-zero. In this case we can play 3-pile NIM and change one of x,y,z to bring the xor to zero.
• In all other cases, look at three values: (minimum of top three, middle, minimum of bottom three). If their xor is zero, we just need to reduce all the other segments on the top and bottom to these values, which is clearly a valid move. Otherwise we also need to decrease one of the three values to make their xor zero, but that is also always a valid move. (Only in one of the three parts all edges will be decreasing, in the other two at least one edge remains unchanged, so we don’t have any cycle.)