Here's how I solved haircut. First, write a function which calculates the number of haircuts which have started at or before m minutes after the store opens. A barber who takes mk minutes to do one haircut will have started 1+floor(m/mk) haircuts by minute m. Add this up over all barbers.
Then look at the actual data. Special case: If we are one of the first b people in line, we start our haircut at time 0 and barber number n cuts us. Otherwise, estimate the time at which our hair gets cut by calculating the number of haircuts which start per minute, the sum of 1/mk over all barbers, so our haircut will start around (n-b)/haircuts_per_minute minutes after the store opens. Use the function to calculate the actual number of haircuts started by this time. If it turns out we haven't started our haircut, add b/haircuts_per_minute and try again. This will soon find a time when our haircut has started. Now use interval halving between 0 and the time estimates above, or between the next-to-last and last estimates, to find the exact moment when our haircut starts. Calculate the number of haircuts which started the previous minute, and subtract from n to determine which of the barbers starting haircuts the same minute as our haircut starts we will go to. Then traverse the list of barbers once more; for each one where the time our haircut starts is divisible by his mk, he started a haircut that minute. Pick the appropriate one. On Sat, Apr 18, 2015 at 2:47 PM, Harsh Vardhan <[email protected]> wrote: > Can anybody explain the solution of Haircut ? > > -- > 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/CAKDd-nzxY8OSQL85-xLrMFb-0rUc0PkXOudi9%3DJyYmPLt28ngw%40mail.gmail.com > <https://groups.google.com/d/msgid/google-code/CAKDd-nzxY8OSQL85-xLrMFb-0rUc0PkXOudi9%3DJyYmPLt28ngw%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/CAMAzhzh-%2Bbr3Q6SmYnhyO5DVZpu_Dw7FHaVtZhPUHFX_o1Q5Lg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
