search

theXYZT / codejam-2020

Python 3 solutions to Google Code Jam 2020 problems.
MIT License
6 stars 9 forks source link

Any explanation on your Indicium solution? #1

Open blakeex opened 3 years ago

blakeex commented 3 years ago

Hi, sorry to bother you. I like your Indicium solution at the Qualification round as it is short & simple.

Is it possible for you to add more note on how you got to that solution?

I just want to understand how did you solve that problem.

I understand it had been awhile since you uploaded the solution. Appreciate it if you could help. Thanks.

theXYZT commented 3 years ago

Once you have found a valid diagonal for the matrix, you can always greedily fill up the rest of it successfully. That is what generate_latin_square() does. So, the main challenge is to find a valid diagonal.

If a valid Latin square is possible, then it is always possible to generate a diagonal of the form: [a, a, a, ..., a, a, a, b, c] where either a == b == c or a != b and a != c such that the trace constraint is satisfied. This is what get_diagonal() does.

This is the same solution provided by the Codejam team in the problem analysis: https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209aa0#analysis