The LCM of 12...18 is 2*2*2*2 * 3*3 * 5 * 7 * 13 * 17 = 1113840, which is just over 10^6.
[2, 3, 5, 7, 11, 13, 17] was my first attempt, but it only gets you to about 500000. Changing that 2 to a 4 is good enough. And yes, the Chinese Remainder Theorem gets you most of the way there; the requirement in CRT is that the numbers are all co-prime, which is why we take the LCM instead of the product of the numbers you consider. On Mon, Apr 15, 2019 at 12:55 PM kitchent <[email protected]> wrote: > Wasn't patient enough to reach the appendix of the editorial. I tried > implementing a dynamic programming solution based on integer partition from > vague memory of Project Euler Problem 31 Coin Sums and Problem 78 Coin > Partitions. Took a different perspective where my array index indicates > total number of gophers. > > http://ix.io/1Gbe > > It turned out harder than I expected it to be. In particular the part > where n choose r comes into play. Initially I thought those gophers between > different windmills were indistinguishable, and incorrectly used [1] * 18 + > [0] * 83 to begin with. Still a bit hard to depict how they are actually > different. All in all, a fun activity to have. > > By the way, for the problem itself, my attempt was to try my luck with 12 > through 18, after the failure to pass test set 2 with [2, 3, 5, 7, 11, 13, > 17]. And it was a shock to me that it worked. I thought it was pure luck > that could fail with another try, but from the wording of the analysis, it > seemed to be legit. Is Chinese Remainder Theorem relevant here? > > -- > 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 post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/be3aff9e-331b-472b-b49d-56cdda25a2b5%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- 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 post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAHaiWHOzMTCDMMf9C5LT_x-2MtuSMPthHO2TsOxsjo3d_p2PBw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
