I found same problem with the trace pattern (AAA... BC), like N=4, K=10 and A=1, B=2, C=3, 1 4 3 2 0 1 0 0 0 0 2 0 0 0 0 3
or N=5, K=7, and A=1, B=2, C=2, 1 5 2 4 3 2 1 5 3 4 0 0 1 0 0 0 0 0 2 0 0 0 0 0 2. But weird thing is, that I *can fill rows from the bottom*. I think we need a mathematical proof with Hall-marriage theory, Does anybody know? On Monday, April 6, 2020 at 9:05:20 PM UTC-4, Maverick wrote: > > 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 google-code+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/2ba0f033-c05b-441e-a046-43b2a21534b2%40googlegroups.com.
