Paul's technique is how I solved Bathroom stalls. Because there can be a very large number of stalls, you can't simulate every stall, but if you just keep track of how many intervals of empty stalls of each size that there are, then you can do all intervals of one size at once (which all split the same way), just checking one time whether that number is more than the number of remaining people waiting. If it was, then the answer is how those stalls split, and if it wasn't, then you add the resulting intervals to the list of ones to process, and then look at the next smaller size of intervals. This is O(log N), so it doesn't take too long.
Filip made some bad assumptions about how this works, extrapolating incorrectly from the result for 2^N-1 stalls, and I think Nam Nguyen Hoang's code, asked about in another thread, which I couldn't understand how it was meant to work, was also making this incorrect assumption or a similar one. On Wed, Apr 12, 2017 at 12:08 PM, Paul Smith <[email protected]> wrote: > 500 255. > First step, the 500 turns into a 250 and a 249 (k=1) > Second step, the 250 turns into a 125 and 124, and the 249 turns into 2 > more 124s (k=3) > Third step, the 125 turns into 2 62s, the 3 124s turn into 3 62s and 3 61s > (k=7) > Fourth step, the 5 62s turn into 5 31s and 5 30s, the 3 61s turn into 6 > 30s (k=15) > Fifth step, the 5 31s turn into 10 15s, the 11 30s turn into 11 15s and 11 > 14s (k=31) > Sixth step, the 21 15s turn into 42 7s, the 11 14s turn into 11 7s and 11 > 6s (k=63) > Seventh step, the 53 7s turn into 106 3s and the 11 6s turn into 11 3s and > 11 2s (k=127) > Eight step, the 117 3s turn into 234 1s and the 11 2s turn into 11 1s (and > 11 0s) (k=255) > Ninth step, the remaining 245 1s are filled. > > So, no, it it not the case that with half the stalls filled all remaining > gaps are 1 across, in this case the 255th person is placed into a 2 stall > wide gap. (I believe this means 500 254 should also yield 1 0, only 500 > 256 would yield 0 0) > > On Wed, 12 Apr 2017 at 16:32 Filip Bačić <[email protected]> wrote: > >> 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. :) >> >> -- >> 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/ba3dec8d-5d83-4f1f-9b76-5e9e6822cb10%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/CAJej63%2B5qz4GLOWDKFF3E1USYaPwgN- > FxO6AcBrGUUytN9ouBA%40mail.gmail.com > <https://groups.google.com/d/msgid/google-code/CAJej63%2B5qz4GLOWDKFF3E1USYaPwgN-FxO6AcBrGUUytN9ouBA%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > > 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/CAMAzhziwviUC%2BjcZd2Z4VzS4_VBFcAK7Y8RnX5Z7Xzaski4SZA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
