ay2306's blog

A few questions for those who were able to solve CodeJam 2020 Qualification E for heavy testcases.
By ay2306, history, 4 years ago, In English

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?
  • Vote: I like it
  • +27
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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).

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it
  1. No
  2. No
  3. Graph and flow
→ Reply