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 view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/s-xgkysj9yYJ. 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.
