I am unclear on the analysis of *Testset-2* of Indicium
<https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209aa0>
(Problem-5,
Qualification Round, Codejam 2020).
It is all clear up until the second last paragraph, where we construct a
Latin square matrix out of the given diagonal. (creating a diagonal from
the given trace, by AAAA...AABC, where A is N-2 times, is clear). It says
to construct row by row, by creating a bipartite graph for each row, and
any possible bipartite matching of the said graph can be used as the
solution for the row. It also says that this greedy method for each row
will not lead to any problems for further rows.
I tried the above method, for N=4, K=9. The diagonal for K=9 is chosen as
1,1,3,4 (A=1, B=3, C=4).
Now for the first row, bipartite graph is created as==>
1 = {1}
2 = {2,3,4}
3 = {2,4}
4 = {2,3}
The bipartite matching chosen for this is: 1-1, 2-2, 3-4, 4-3. So first row
becomes {1,2,4,3}.
For second row, bipartite graph is created as==>
1 = {2,3,4}
2 = {1}
3 = {2}
4 = {2}
No bipartite matching exists for above graph.
Where am I going wrong?????
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/4af77908-bee9-4daa-89a8-733cf6b403de%40googlegroups.com.
