I also wonder how can we make this assumption? " In particular, we may assume that at least N-2 values are the same: AAAA ... AABC for some A, B, C (not necessarily all different)."
Can anyone give me some explanation? On Friday, April 10, 2020 at 10:55:13 PM UTC+7, James Prudd wrote: > > 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 google-code+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/3c2afb2c-fec3-42b1-9f80-60be5e17d510%40googlegroups.com.
