I also took the A...ABC approach. It's straightforward to get such a square when A,B,C all equal (circulant) or all different (circulant with swapped rows). Getting A...BB is more tricky. It needs a following square in the bottom right corner:
BA AB This structure in a Latin square is called an *intercalate*, and not all Latin squares have it. Importantly, circulant squares of odd size don't. Since swapping columns/rows/symbols preserves the number of intercalates, we cannot get a desired A..BB square of odd size by just swapping rows of the circulant square. This was the most challenging part for me - how to construct an odd-sized square with an intercalate. I didn't manage to solve it during the round, but the next day I came up with a following scheme. The main idea is to start with a smaller square of size (N-1) and extend it to N in a way that preserves the diagonal. Let's say we want an A...BB square of size 7. We start with a circulant square of size 6 (intercalate marked bold, it will always be columns at indices 0 and n/2): *1* 6 5 *4 *3 2 2 1 6 5 4 3 3 2 1 6 5 4 *4 *3 2 *1 *6 5 5 4 3 2 1 6 6 5 4 3 2 1 Now we swap these two columns to bring both 4's into the diagonal: *4* 6 5 1 3 2 5 *1* 6 2 4 3 6 2 *1* 3 5 4 1 3 2 *4* 6 5 2 4 3 5 *1* 6 3 5 4 6 2 *1* This gives us an A...BB Latin square of size 6. In order to turn it into size 7, we shift the part under the diagonal one cell down and fill the space with the new symbol: 4 6 5 1 3 2 *7* *7* 1 6 2 4 3 5 *7* 1 3 5 4 6 2 *7* 4 6 5 1 3 2 *7* 1 6 2 4 3 5 *7* 1 3 5 4 6 2 *7* 1 In the new last column we can put the new symbol in the first row (since all other rows already contain it), and our "A" from the diagonal in the last row because it doesn't have it. Now comes the dirty part. Notice that by shifting half the square down we broke "latinness" in some rows (marked bold) 4 6 5 1 3 2 7 7 1 6 2 4 3 *5* 7 1 3 *5* 4 *6* 2 7 4 *6* 5 *1* 3 2 7 *1* 6 2 4 3 5 7 1 3 5 4 6 2 7 1 We can fix this by circularly shifting the conflicting symbols up in the first column: 4 6 5 1 3 2 7 7 1 6 2 4 3 *6* 7 1 3 *5* 4 *1* 2 7 4 *6* 5 *5* 3 2 7 *1* 6 2 4 3 5 7 1 3 5 4 6 2 7 1 Now we are left with a partial latin square with the desired diagonal. We just need to fill the last column. One way would be to check for the missing symbol in each row, but I used the following insight for the last column: the first cell is already filled with 7, the second cell is going to have the same symbol as the one that was in the first column, second row before the shift (because it's the one that got replaced by the new symbol, and is now missing). In this example it is 5. The rest of the column can be copied from the previous column in two chunks (marked bold and magenta): 4 6 5 1 3 *2* 7 7 1 6 2 4 *3* 5 6 7 1 3 5 *4* *2* 1 2 7 4 6 5 *3* 5 3 2 7 1 *6* *4* 2 4 3 5 7 *1* *6* 3 5 4 6 2 7 *1* Here you go, an odd-size "A...BB" Latin square :) On Tuesday, 7 April 2020 02:57:02 UTC+2, XYZT wrote: > > *Link to > problem: > https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209aa0 > > <https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209aa0>* > > The "Analysis" section of Code Jam 2020 Qualification Round Problem 5, > "Indicium" says: > > There are many creative ways to solve this test set. The Code Jam forum is >> a good place to share and discuss different solutions! For example, we can >> directly create Latin squares with the appropriate trace by modifying >> structured Latin squares (for example, by modifying *circulant *Latin >> squares). > > > *I am very interested to know what alternative "creative" approaches > people came up with to solve this problem.* > > One alternative solution that I am pretty sure should work is: > Build a simple circulant Latin square. The trivial cases where K % N == 0, > the solution is obvious. > For the non-trivial cases, swap any two rows. This gives a matrix with a > diagonal that has three unique symbols: A, B, and C where there are N - 2 > instances of A, and one instance each of B and C. Then you can find the > right values of A, B and C needed to achieve the right trace (as per the > "Analysis" section) and simply swap symbols in the required way. > > As someone who is uncomfortable around graphs and graph-related > algorithms, I am glad I thought of this solution. I am curious what other > creative solutions people found. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/1fe3ed4d-afde-43d3-82bd-6222d11f6493%40googlegroups.com.
