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" <[email protected]> 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 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.
