I solved Indicium pretty slowly (17 hours after the other problems...) when I had a brainstorm.
It is a lot like what you suggested, but your solution is not complete. (a) if k is a multiple of n, a circulant square with k/n on the diagonal works. (b) When k=n+2, or k=n^2-2, or n=4 and k=10, find a solution with A...ABB on the diagonal (described below). These cases do not work the way you propose; you cannot (for at least some n) swap two rows to get this diagonal. (c) For every other case that has a solution, A...ABC on the diagonal with different A,B,C works; generate it by swapping two rows of the circulant square. (d) Write a testing program which uses the code from Vestigium to confirm that for all 40,000 or so possible inputs, the square output by this procedure is valid. This was how I found 4,10 was a special case. For all three cases, I wrote code that generated one matrix of the each of these three types for each size, and then applied a substitution to maintain the Latin square while putting the desired elements on the diagonal. The A...ABB solutions: The first time I attempted the problem, I came up with a crazy partitioning strategy to do A...AB...B squares. It worked like this: 1. Partition the square into two unequal squares and two rectangles. 2. Fill the smaller square with a circulant square with the number you actually want on the diagonal on the diagonal, and the number you want on the other part of the diagonal elsewhere. 3. Fill the larger square with a back-circulant square using all the numbers not used in step 2 4. Overwrite the main diagonal and some adjacent broken diagonals of the larger square with the numbers from step 2 but this time putting the other number on the diagonal. At this point you have something like this (where the bold shows squares which started as 3, the italic as 4, and the normal characters in the lower square started as 5). 12 21 2*1**3* *4**2*1 *1*5*2* 5. Fill the rectangles. To fill the upper rectangle, look at the first number in each row, then find the places in the lower square where that number overwrite another number, and put the overwritten number into the intersection of this column and row. Fill the lower rectangle the same way by swapping the application of rows and columns. So in my example, the 1 in column 3 overwrote a 3, so row 1, column 3 gets a 3. You end up with this: 12345 21534 452*1**3* 53*4**2*1 34*1*5*2* We're not done yet! This solution works great for some numbers, but before I even wrote the code to generate it, I observed that it doesn't generate a valid Latin square for n=6, k=8 where you need 111122 on the diagonal and divide into a 4x4 and a 2x2. Even when I substituted other Latin square patterns for the back-circulant Latin square, And then I went to sleep, and came back a while later. The technique I proposed above works for odd n divided into 2x2 and (n-2)x(n-2), and probably all divisions where the subsquare sizes are coprime. Having determined A....ABC works for almost all cases, I set about using the above for n=odd, k=n+2 or n^2-2, and generating a different solution for the n=even cases. (Ironically, XYZT's solution does solve these cases - provided you choose the right two rows to swap. You want to choose rows which are half the square apart. It's the odd cases I solved above which *can't* be solved that way. But I didn't see that and came up with something else.) For these cases, make a block-circulant Latin square. This means divide the square up into 2x2 subsquares, and fill each subsquare with a Latin square. The first row of 2x2s (so two rows of the overall Latin square) just use the numbers in order, so 123456 214365 And the subsequent rows, two rows at a time, shift the previous two rows by two elements (one 2x2 square). In this way, it's a size n/2 circulant Latin square made of 2x2 Latin squares as elements. Finally, to get the required diagonal, flip one of the 2x2 squares containing 1 and 2. So for n=6, k=8 you get: 123456 214365 561234 652143 345621 436512 On Mon, Apr 6, 2020 at 8:56 PM XYZT <nikhil...@gmail.com> 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 google-code+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/f668e0d6-70a2-4af6-9e72-f8c7a75162e1%40googlegroups.com > <https://groups.google.com/d/msgid/google-code/f668e0d6-70a2-4af6-9e72-f8c7a75162e1%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- 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 google-code+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMAzhzjb7yTF8yKFygeDbSE2staSG8HmjJ-Aydb6Br02eYxoYA%40mail.gmail.com.
