I'm using Python, too. In the qualification round, I almost got burned, as I was running it on a very slow machine, and only finished the large input on one problem with seconds to spare. This time, I coded up some boilerplate that (together with xargs) will allow me to run separate cases individually, on separate CPUs. Pypy would also be a possibility for speeding things up some. Unfortunately, since I was mostly tripping over the algorithms, I didn't really get a chance to benefit from this.
As Luke says below, I think there's a way to use multiple heap queues and maybe sets to get to O(n log n). For the one star levels, you can just keep track of the two sets (sufficient and not), and move levels from one to the other as they become achievable. In any case, this time, quadratic was good enough, and certainly leads to a simpler algorithm. Mike On Saturday, April 28, 2012 12:17:31 AM UTC-5, IdahoJacket wrote: > > My n^2 solution in Python ran the large input in ~20 seconds. Considering > that Python is not known for its speed, and I made no particular effort to > make my code efficient, doing it in C++ would be unlikely to make any > difference. > > I'm not sure how you would create an n log(n) algorithm. You could use a > heap for finding any available 2 star levels to play in n log(n) time, but > choosing which 1 star level is harder. The search for 1 star levels first > needs to bisect the list of nodes into those you have enough stars to > complete and those you don't. Then you need to find which of those has the > largest 2 star value. The first part can be done in log(n) time, but I > don't see how you can do the second part in under n. > > On Friday, April 27, 2012 9:03:04 PM UTC-7, tutufan wrote: >> >> I (deservedly) got crushed in Round 1A (20pts). In the process, though, >> noted that the winning solutions to problem B are all quadratic, even >> though (I think) the problem is actually O(n log n). My incorrect >> algorithm was, being based on heap queues, and I'm thinking the correct >> algorithm also could be done that way. >> >> If so, this is maybe a case where C++ helps you out (i.e., you can be >> quadratic and just blow through it). >> >> >> >> On Friday, April 27, 2012 3:35:23 PM UTC-5, tutufan wrote: >>> >>> Apparently C++ is the most common language used by GCJ winners, at least >>> in later rounds (if not all of them). It seems like the pressure for a >>> rapid solution would suggest a higher-level language like Python, Ruby, >>> Lisp, etc., but that's not what contestants are actually doing. >>> >>> Any theories for this? Possibilities: >>> >>> 1. C++, being an order of magnitude faster for execution, allows >>> more slop in sub-optimal algorithm selection. >>> 2. C++ happens to be the language the best or most fluent coders are >>> using all day long (so are most familiar with). >>> 3. C++ is actually the best language (a priori) for this contest, >>> for some non-obvious reason. >>> >>> What do you think? >>> >> -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/ylzEFp0ZZ6YJ. 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.
