Question: Given a $N \times N$ circulant Latin square, $M$, is there a sequence of algorithmic modifications that one can make to $M$ such that the main diagonal will consist of exactly $2$ distinct values, $a$ and $b$, such that there are exactly $N - 2$ instances of $a$ and $2$ instances of $b$.
Context: I am trying to derive an alternative solution to this problem from the Code Jam 2020 Qualification Round.
The problem statement: Given two integers $N$ and $K$ such that $N \ge 2$ and $N \le K \le N^2$, construct an $N \times N$ Latin square with a trace (sum of elements along the main diagonal) of $K$.
My incomplete solution: We can ignore the cases where this is not possible: $K \in \{N + 1, N^2 - 1\}$ for all $N$ as well as $K \in \{5, 7\}$ for $N = 3$.
For the rest of the cases, I construct a simple circulant Latin square (example for $N = 5$): $$ M = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 2 & 3 & 4 \\ 4 & 5 & 1 & 2 & 3 \\ 3 & 4 & 5 & 1 & 2 \\ 2 & 3 & 4 & 5 & 1 \\ \end{bmatrix} $$
For any $K \equiv 0 \pmod {N}$, the solution is a trivial cyclic permutation of the rows/columns of $M$.
For most other values of $K$, all you need is for the main diagonal to consist of $3$ distinct values: $a$, $b$, and $c$ such that there are exactly $N-2$ instances of $a$, and $1$ instance each of $b$ and $c$. So, the main diagonal looks like $aaaa \dots aaabc$. You can achieve this configuration in $M$ by swapping any two rows or columns. Then, finding the answer is a simple matter of solving for the triple $(a, b, c)$ that satisfies $K$ and then cyclically permuting the "symbols" in $M$ so that the correct values are in the correct positions.
However, there is an edge case that eludes me: $K \in {N + 2, N^2 - 2}$. For this case, you require the main diagonal to have a configuration of $aaaa \dots aaabb$.
Unfortunately, I have found no meaningfully deterministic way to modify some constructed circulant Latin square $M$ such that you end up with a main diagonal with exactly $2$ distinct values, $a$ and $b$ such that there are exactly $N - 2$ instances of $a$ and $2$ instances of $b$.
Is there a relatively deterministic way to construct such a Latin square from a different constructed circulant Latin square?
Here's one deterministic way. The first part, before the line, is a hint extending your line of thought if you want to solve it yourself. The solution is after the line.
As you've noticed, the main difficult of this problem lies in constructing a matrix with diagonal $aaaa\dots aaabb$. You have addressed the other simpler case of matrix with diagonal $aaaa\dots aaabc$, which can be done simply by swapping rows 1 and 2 of a circulant matrix.
Now for the $aaaa\dots aaabb$ case, notice that for circulant matrices you always have on the top left hand corner $$ \begin{matrix} 1 & 2 & 3 &\cdots \\ N & 1 & 2 & \cdots \end{matrix} $$ so a natural consideration is to swap row 2's first and third element, which will always be $N$ and $2$ respectively. Switching rows 1 and 2 after that gives you the desired diagonal $1111\dots 11122$. This does not work directly but we can make it work starting from here.
Solution below.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
This of course does not work directly since it conflicts with the lower rows, but then you can try to rearrange the lower rows one by one. If you can somehow fix this, then switching rows 1 and 2 after that gives you the $1111\dots 11122$ diagonal.
Now the easy case comes when $N=2n$ is even. In this case it's straightforward to show that it suffices to swap every even row's first element with the third element. For example for $N=6$ this is $$ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 6 & 1 & 2 & 3 & 4 & 5\\ 5 & 6 & 1 & 2 & 3 & 4\\ 4 & 5 & 6 & 1 & 2 & 3\\ 3 & 4 & 5 & 6 & 1 & 2\\ 2 & 3 & 4 & 5 & 6 & 1\\ \end{bmatrix} \Longrightarrow \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 6 & 3 & 4 & 5\\ 5 & 6 & 1 & 2 & 3 & 4\\ 6 & 5 & 4 & 1 & 2 & 3\\ 3 & 4 & 5 & 6 & 1 & 2\\ 4 & 3 & 2 & 5 & 6 & 1\\ \end{bmatrix} $$ This works because every even values of column 1 is moved to column 3 and vice versa, so the Latin square property must hold column wise. (Clearly row-wise it's never a problem.)
On the other hand for odd $N=2n+1$ this does not work directly. For instance, since $N$ is odd, switching $N$ and $2$ for row two is no longer just switching even values. However with a bit of extra work this can still work. I claim that the following algorithm works:
Algorithm 1 (Construct odd Latin square of dimension $N=2n+1$ with diagonal $\{2,2,1,1,1,\dots,1\}$)
0. Start with a circulant matrix of odd dimension $N = 2n+1\geq 5$.
1. Switch first and third element for every even row except the last (So rows $2,4,\dots,2n-2$).
2. Do a right rotation of the first 3 elements on the 2nd last row (row $2n$). This will always be $(3,4,5)\longrightarrow (5,3,4)$.
3. Do a left rotation of the first 3 elements on the last row. This will always be $(2,3,4)\longrightarrow (3,4,2)$.
(Steps 1 and 2 are not independent when $N=3$, which will create problems. This is why we'll assume $N\geq 5$.)
Using $N=7$ as an example: $$ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 7 & 1 & 2 & 3 & 4 & 5 & 6\\ 6 & 7 & 1 & 2 & 3 & 4 & 5\\ 5 & 6 & 7 & 1 & 2 & 3 & 4\\ 4 & 5 & 6 & 7 & 1 & 2 & 1\\ 3 & 4 & 5 & 6 & 7 & 1 & 2\\ 2 & 3 & 4 & 5 & 6 & 7 & 1 \end{bmatrix} \xrightarrow[\text{}]{\text{(step 1)}} \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 2 & 1 & 7 & 3 & 4 & 5 & 6\\ 6 & 7 & 1 & 2 & 3 & 4 & 5\\ 7 & 6 & 5 & 1 & 2 & 3 & 4\\ 4 & 5 & 6 & 7 & 1 & 2 & 1\\ 3 & 4 & 5 & 6 & 7 & 1 & 2\\ 2 & 3 & 4 & 5 & 6 & 7 & 1 \end{bmatrix} \xrightarrow[\text{}]{\text{(step 2)}} \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 2 & 1 & 7 & 3 & 4 & 5 & 6\\ 6 & 7 & 1 & 2 & 3 & 4 & 5\\ 7 & 6 & 5 & 1 & 2 & 3 & 4\\ 4 & 5 & 6 & 7 & 1 & 2 & 1\\ 5 & 3 & 4 & 6 & 7 & 1 & 2\\ 2 & 3 & 4 & 5 & 6 & 7 & 1 \end{bmatrix} \xrightarrow[\text{}]{\text{(step 3)}} \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 2 & 1 & 7 & 3 & 4 & 5 & 6\\ 6 & 7 & 1 & 2 & 3 & 4 & 5\\ 7 & 6 & 5 & 1 & 2 & 3 & 4\\ 4 & 5 & 6 & 7 & 1 & 2 & 1\\ 5 & 3 & 4 & 6 & 7 & 1 & 2\\ 3 & 4 & 2 & 5 & 6 & 7 & 1 \end{bmatrix} $$
Remark: For the sake of application on the contest, it suffices to check for up to $N=49$ that this works. So if you want to, you can just check all the cases yourself and call it a day.
Proof (Algorithm 1). Or, we can opt to prove this in general for $N\geq 5$. We do this by checking that the Latin square property holds for columns 1 to 3, which are clearly the only columns involved in these operations.
The easy case is column two. Row $2n+1$ changes from $3$ to $4$ due to left rotation. Row $2n$ changes from $4$ to $3$ due to right rotation. Hence Latin square property holds.
Now for the last step it actually suffices to check for just column 1, since it is not possible for just column 3 to fail Latin square property (since that requires duplicates which is not possible when all other $N-1$ columns are complete).
Since the matrix is circulant, column 1's row $2k$ is the same as column 3's row $2k+2$ (two columns and two rows away). Hence the effect of the algorithm's step 1 is to move elements in row $2,4,6\dots,2n-4$ to rows $4,6,\dots,2n-2$ and also replacing row $2$ with the element $2$. i.e. pictorially we have: $$ \begin{bmatrix} 1\\N\\N-1\\N-2\\N-3\\N-4\\\vdots\\7\\6\\5\\4\\3\\2\end{bmatrix} \xrightarrow[\text{}]{\text{(steps 1)}} \begin{bmatrix} 1\\2\\N-1\\N\\N-3\\N-2\\\vdots\\9\\6\\7\\4\\3\\2\end{bmatrix} $$ (Recall that step 1 does not involve the last 2 rows.)
At this point, column does not satisfy the Latin square property because (1) there are two elements equal to $2$ and (2) the element $5$ is missing.
Next, step 2 of the algorithm replaces row $2n$'s from $3$ to $5$ due to a right rotation of row elements $$(3,4,5)\longrightarrow (5,3,4)$$ So still a duplicate of value $2$ and we have no values $3$ now, but we gained the missing $5$.
Finally, step 3 of the algorithm does a left rotation of the last row on three elements, which are $$(2,3,4)\longrightarrow(3,4,2)$$ This gets rid of the extra $2$ and gives us the missing $3$, hence the Latin square property is now satisfied and we are done.
$$ \tag*{$\square$} $$