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

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 To: sourabh.s.joshi@gmail.com Cc: beginners@haskell.org Subject: Re: [Haskell-beginners] GCJ 2015 - Round 1A Problem - Haircut Message-ID: <201504181429.t3IETBfo025201@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