I think this may be helpful : https://codeforces.net/blog/entry/71545?#comment-597939

I haven't solve E, but here are my thoughts process if that helps.

• Run some brute force on small numbers. Get a hypothesis that for $$$N \geq 4$$$ only $$$N+1$$$ and $$$N^2-1$$$ traces aren't possible.
• Read from Wikipedia that "The problem of determining if a partially filled square can be completed to form a Latin square is NP-complete".
• From there you can guess that it's likely not some algorithmic problem (at the top level), but a construction one.
• Then I decided I have better things to do. :D

Now, after reading the analysis, turns out it was indeed construction problem at the top level.

For me, I just tried to see what numbers I can put on the diagonal. From there (and sample 2), it is easy to see that we cannot have exactly $$$n-1$$$ same numbers on the diagonal. Note that if we fix the diagonals and add the numbers one by one, it becomes a standard matching problem so I just used flow to solve from there like in the editorial (after finding a greedy assignment for the diagonal).

1. No
2. No
3. Graph and flow