Ah, that's probably why. I didn't even use a hash map (which would allow O(1) access). I used a set, and it's probably implemented using a tree (so O(logn) access).
A hash map would have additional risk of collision, though, that would be hard to detect. But if you give it 2GB of memory or something... luck will probably be on our side. On Sep 12, 9:44 am, Nate Bauernfeind <[email protected]> wrote: > FYI for a solution that runs in less than 20 seconds you need to > memoize using a simple int[11][MAX_V] kind of array. > > (Another FYI: hash maps have way too much overhead... Changing the > hash maps in my solution to a simple array drops the run time from 23m > to 18s. Doh!) > > Nate > > On Sep 12, 1:34 am, Bartholomew Furrow <[email protected]> wrote: > > > Sometimes solutions run near the limit, and it can help to have fast > > hardware; I'd like to think this is the exception rather than the rule. > > With that said, it's a shame when it does happen. I'm hoping you can think > > of an optimization or two that would have brought the runtime down by some > > constant factor, so that you could have done it even with 2x slower > > hardware. > > Incidentally, an alternative was to do precomputation. I didn't work on > > that problem myself, but I think it was a way around doing a lot of > > computation during the 8 minutes. > > > Also it was apparently solvable within 20 seconds in C++, though as I > > mentioned I don't know how. :-) Terence, would you mind linking your > > solution? > > > Bartholomew > > > On Fri, Sep 11, 2009 at 11:00 PM, cyberfish <[email protected]> wrote: > > > > Just thought I should point out that, for the large input of question > > > A (round 1A), my program solved it in a little under 7 minutes on my > > > computer (a Core 2 Duo overclocked to 3.3ghz). A slower computer may > > > not have made it, so I think this gives an unfair advantage to people > > > with fast computers (like myself) :). --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
