According to the analysis of Indicium problem in https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209aa0
I wonder how to prove it. Can someone here write a detailed proof please? In particular, why greedily starting from the rows with B and C on their diagonal is the key here? We can greedily pick any perfect matching for each row *starting with the rows with B and C on their diagonal*. Once we have filled in these two rows, we can use Hall's Marriage Theorem <https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem> to show that we will never run into any issues (so long as the conditions above about A, B, C are met). -- 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/3b23cbf2-1e35-4790-b49a-e0a7e0ba954b%40googlegroups.com.
