[Haskell-beginners] : GCJ 2015 - Round 1A Problem - Haircut

[Kostiantyn Rybnikov]

Instead of looking at it as an estimate, you can look at it as a
"summarized speed of all barbers".

It would let you know much time would it take to cut everyone before you.
Afterwards you'd need to go through barbers and find the first one that
would become available after this time-period.

Do you think this makes sense?
27 квіт. 2015 05:40 "Gregory Guthrie" <guthrie at mum.edu> пише:

> Seems to me that an estimate won't help, one has to know exactly how much
> to skip over.
>
> I did this:
>    Find the lowest common multiple (lcm), and then from that the shortest
> cycle of services,
>    And then skip any multiple of those from the customer queue.
>
> sim :: Problem -> [Result]
> sim (n, ts) = serve tSkip (servers ts)
>     --  optimize; skip ahead over server cycles...
>     where tsLcm  = (foldl lcm $ head ts) $ tail ts
>           tCycle = sum $ map (div tsLcm) ts
>           tSkip  = n - (div n tCycle)*tCycle
>
> (Some fixup is needed for tSkip=0, one easy one is to force an extra
> cycle.)
> > ----------------------------------------------------------------------
> > Message: 1
> > Date: Sat, 18 Apr 2015 10:29:11 -0400
> > From: Doug McIlroy <doug at cs.dartmouth.edu>
> > To: sourabh.s.joshi at gmail.com
> > Cc: beginners at haskell.org
> > Subject: Re: [Haskell-beginners] GCJ 2015 - Round 1A Problem - Haircut
> > Message-ID: <201504181429.t3IETBfo025201 at coolidge.cs.dartmouth.edu>
> > Content-Type: text/plain; charset=us-ascii
> >
> > > Can someone tell me how I could have avoided or fixed this?
> >
> > The trouble manifested as stack overflow on solving
> >
> > > https://code.google.com/codejam/contest/4224486/dashboard#s=p1
> >
> > For efficiency, you'll probably need more cleverness in math than in
> Haskell. You can predict
> > an approximate start time for the Nth customer's service from the
> average per-customer
> > service time M, where 1/M = sum 1/M_k.
> > Starting from that estimate, one can skip over almost the entire service
> simulation.
> >
> > Doug McIlroy
> >
> >
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150503/862e6fde/attachment.html>