Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### ay2306's blog

By ay2306, history, 2 months ago, ,

I have a few questions:

• When you saw this question, did you already know how to approach it?
• Did you look something up the internet which helped you solve it, if yes then how did you know what to search?
• If you knew how to solve it using common competitive programming Algorithms/Data Structure, then what did you use?

• +27

 » 2 months ago, # |   +3 I think this may be helpful : https://codeforces.com/blog/entry/71545?#comment-597939
 » 2 months ago, # | ← Rev. 2 →   +22 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.
 » 2 months ago, # |   +8 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).
 » 2 months ago, # |   +7 No No Graph and flow