A...ABC: The n-2 A's give us n possible values from n-2 to (n-2)n as A varies from 1 to n. The B and C can independently vary from 1 to n. If they are both n, then the sum is (n-2)A +2n = nA + 2n - 2A When you increase A by 1 and reduce B and C to 1, then the sum becomes (n-2)(A+1) + 2 = nA + n - 2A + 1 So the ranges of sums you can get by choosing A, B, and C overlap, and you can reach every value.
It's a little more complicated than this, because B and C aren't completely independent. You can't have only one of B and C equal to A, because you can't have only one number different on the diagonal; the Latin square condition forces the last number on the diagonal to also match. However, you can avoid this in most cases by increasing or decreasing one of B,C by 1 and moving the other in the other direction. This only fails near the top and bottom of the range: When A=1, B,C=1,2 or A=n, B,C=n,n-1. It's clearly impossible to find an alternative in these cases. But it's just as impossible for any other diagonal. On Mon, Apr 13, 2020 at 12:08 PM Pakawat Nakwijit <[email protected]> wrote: > 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 [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/3c2afb2c-fec3-42b1-9f80-60be5e17d510%40googlegroups.com > <https://groups.google.com/d/msgid/google-code/3c2afb2c-fec3-42b1-9f80-60be5e17d510%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- 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/CAMAzhzg%3DRtHL%2Bai%2BZBfF9xXmFPcKjXNL8DT%2B8d7QxkPvMVDghg%40mail.gmail.com.
