I think there was no problem with speed on problem B, I made it with Visual Basic and runned in under 20 seconds with the large input. Still think C++ is much more appropriate for these than VB but this time it worked fine.
On Apr 28, 11:42 am, tutufan <[email protected]> wrote: > 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 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.
