I solved this with binary search on the time 't' that I start my haircut. For a given time 't' it is easy to calculate the number of haircuts that have been started (i.e. for each barber it's (t + m - 1) / m). Binary search until you find the time that your haircut must have started. It is then true that f(t-1) < n <= f(t). Your barber is the (n - f(t-1))'th free barber. A barber is free at time t if t % m == 0.
On Saturday, April 18, 2015 at 5:02:42 PM UTC-4, /dev/joe wrote: > 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. > > 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/d6b5b425-6a8e-4f01-8aac-87177dea1f6a%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
