Instantly share code, notes, and snippets.

# lava/indicium.md

Last active April 8, 2020 10:01
Show Gist options
• Save lava/22c60606a84eeeea780f21ebfceb4d46 to your computer and use it in GitHub Desktop.
Google Code Jam 2020 Indicium Analysis

# 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
``````