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

[Gregory Guthrie]

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
> 
>