You can't use [2, 3, 5, 7, 11, 13, 17] because it only guarantees a unique solution modulo LCM(2, 3, 5, 7, 11, 13, 17) = 510510 and the maximum number of gophers in the problem is 1000000. Using [3, 4, 5, 7, 11, 13, 17] works though. You can use Chinese Remainder Theorem to solve the problem.
On Mon, Apr 15, 2019 at 2: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/CAOOYsbjQSp1pXhDc%3DX0bD-0FUfN_oQgj7UPLh%3D8rrfSOsi0PvA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
