Yes, it does matter. I tired to implement the isHappy() in Java with HashMap<Integer,Boolean>. It just fail because of OutOfMemoryError(with -Xmx1024MB).
Then after, I checked the source from the top guys. The algorithm is exactly the same, but he use C++. I don't think language is a matter, so I rewrite my program and replace HashMap with byte[]. Finally, it run smoothly with a bit faster. The rule of abstraction does not apply to code competition? On Sep 13, 4:25 am, cyberfish <[email protected]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
