In the qualification round, my Python solution to B (or C?) almost overran the time limit for the large input. This was partly because my original program didn't provide any progress feedback, and I wasn't sure it was working correctly, so I restarted it to be sure. Even after the restart, though, it probably ran for 5+ minutes, and I just squeaked it in.
So, this time, I was ready to run pypy, and also to split cases across CPUs. Unfortunately, though, A didn't need this, and I tripped on the algorithm for B (running out of time for C), so I didn't get to use any of this. But I'm ready for Round 1B! :-) On Tuesday, May 1, 2012 1:48:44 AM UTC-5, Luke wrote: > > Agreed. I think Problem B could have been coded in Brainf*ck or something > like that without having any difficulty of finishing on time. > > However, as the contest progresses this is less and less the case. Still, > I contend that one could write a solution to any code jam problem so far in > Python, that would run in under 8 minutes with pypy. > > I came quite late into the knowledge of pypy. I qualified for last years > World Finals by virtue of having solved the D-large in Round 3. However, I > was very lucky, as running it took about 7 minutes and 30 seconds. Had I > been using pypy, it would have been much more comfortable. > On 30 Apr 2012 23:46, "Makandriaco" <jimenez@ <[email protected]>xxx> > wrote: > >> 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. >> >> -- 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/-/p31vGPUsixUJ. 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.
