Indicium

Problem 5 of the Google Code Jam 2020 qualifiers was to construct a N-by-N matrix with trace K, where each row and each column contains every number between 1 and N exactly once (aka a latin square).

The official write-up is pretty sparse, omitting the key insights of how to generate a valid trace pattern for K and how to extend the trace pattern to get a valid partial latin square, so I had to piece together the missing parts from the corresponding codeforces thread. I'm collecting this here, since I still haven't seen a complete, correct analysis.

The key insight here is that we can always get a valid "starter" for our lating square if T distinct values of the trace each occur at least T times. Then we can fill the squares spanned by each of the values by filling up the diagonals and get a valid placement for all the digits part of the trace.

For example:

Trace: A A A B B

A _ B
B A _
_ B A
      B A
      A B

Trace: A A A B B B C C C

A B C
C A B
B C A
      B A C
      C B A
      A C B
            C B A
            A C B
            B A C

From here, we can use Hall's algorithm to extend this to a full latin square, but unlike described in the writeup, we need to go number by number, rather than row by row. (see e.g. https://www.cs.du.edu/~petr/milehigh/2017/kuhl.pdf)

Now we just need to represent each K as a combination of T distinct values occuring at least T times.

Once N gets large enough, we can use a kind of counter to generate each K value:

  K   | Trace
------------------------
 N      1 1 1 ... 1 1 1
 N+1    ?
 N+2    1 1 1 ... 1 2 2
 ...
 2N-2   1 1 2 ... 2 2 2
 2N-1   ?
 2N     2 2 2 ... 2 2 2

We can of course generalize from trace N to trace xN by putting x x ... x on the diagonal.

This also means that we need N >= 10 for this construction to always work.

xN:      x     x     x    x  x    ...  x     x     x     x     x
xN+1:   (x-1) (x-1) (x-1) x  x    ...  x    (x+1) (x+1) (x+1) (x+1)
xN+N-1:  x     x     x    x (x+1) ... (x+1) (x+1) (x+2) (x+2) (x+2)

Of course, (x-1) and (x+2) must not go out of bounds, which would happen for n+1 and n**2-1. Fortunately, these cases are impossible to solve anyways, so we can ignore them and output "IMPOSSIBLE".

For N < 10, I don't have a really smart idea. Probably the A A A A B C pattern from the analysis would work here as well, but the proof is not immediately obvious to me.

PS: After having written the above, I noticed that Google's original solution can also be made to work, since their trace pattern permits expanding into a valid partial latin square by expanding it according to this scheme:

A B
C A B
  C A B
    C A   B
      C B A
        A C

lava/indicium.md

Indicium