The second part can be done in total time O(n log n) as well. You simply create a heap of nodes, arranged by largest 2 star value. It takes time n log n to add and remove n nodes to a heap.
On Sat, Apr 28, 2012 at 6:17 AM, Tom Anderson <[email protected]> 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: >>> >>> C++, being an order of magnitude faster for execution, allows more slop >>> in sub-optimal algorithm selection. >>> C++ happens to be the language the best or most fluent coders are using >>> all day long (so are most familiar with). >>> 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. -- 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.
