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.
