I shared your intuition, but actually it's incorrect. Start with N=23. Add a person. Now you have 2 gaps of size 11. Add two people. Now you have 4 gaps of size 5. Add four people. Now you have 8 gaps of size 2.
You've added seven people already. You'll add eight more before you get to the last eight gaps, which are all of size 1. If you think about it a little more, you'll see that size 1 gaps generally start between N/2 and N/3, when N is large, depending on N. In particular, if G1(x) = G(x) = 2x+1, and Gn(x) = G(Gn-1(x)), then Gn(2) takes the longest to get to gaps of size 1, with the remaining stalls approaching N/3 from above as n increases, and Gn(1) takes the least time, with the remaining stalls approaching N/2 from above as n increases. I hope that helps! Bartholomew On Wed, Apr 12, 2017, 09:32 Filip Bačić, <[email protected]> wrote: Hi, I am trying to figure out why my solution wasn't right. I couldn't even solve Small Input 1 and now I took someones solution from the scoreboard who solved it and when I compared my output with that one (on C-small-1-attempt0.in) I found out that on 100 cases my output is different on 5 of them: Case # N K My solution Correct solution 10 500 255 0 0 1 0 16 999 508 0 0 1 0 34 500 254 0 0 1 0 68 999 511 0 0 1 0 91 1000 511 0 0 1 0 Problem is that I still do not understand these results :) And for example for case 500 254 then we both get 0 0 as solution. My reasoning was that whenever K > N/2 then answer is 0 0 because after half of stalls are taken then there can only be left empty stall between two which are taken. Could you please explain me how my reasoning is wrong? It bothers me really. :) Best Regards, Filip Bacic -- 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/23868698-c860-44fd-be3e-521d9e334843%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/CAHaiWHPbh_8D0mcCFmokTUumhicM5HPuuHsxVNA%2BQD6ianX1EQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
