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

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" пише:

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

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners