I agree. On 1 May 2012 18:01, "Registered user" <[email protected]> wrote:
> lets plz close this thread... > the person who asked has got the ans. and now plz do not reply anymore to > this. lets have some mercy on the traffic. > > this thread is closed... > On 1 May 2012 12:18, "Luke Pebody" <[email protected]> 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" <[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. >> > -- > 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.
