Are we talking about the qualification round problem from 2017? How are you trying to solve it if not by downloading the data? All problems prior to 2018 are solved by downloading data and uploading output.
I do think the analysis is right. On Thu., Aug. 23, 2018, 04:24 Eugene Yarmash, <[email protected]> wrote: > > On 08/23/2018 04:42 AM, Bartholomew Furrow wrote: > > We're looking at roughly 10^6 heap operations in 100 test cases, which is > around 10^8 heap operations total. I'd expect that to run in 4 minutes or > less in C++ no problem, but in Python I wouldn't be so confident. How long > does it run for? > > > I don't know as the test cases aren't downloadable (and I've switched to > another approach). > > I was just wondering if it was an inaccuracy in the text or a bug. The > relevant part is: > > If the operations over S are efficient, this will run in quasilinear > time. There are many data structures that support insertion, finding the > maximum, and removal of the maximum in logarithmic time, including AVL > trees, red-black trees, and heaps. Many languages have one such structure > in their standard libraries (e.g., the multiset or priority_queue in C++, > TreeSet in Java, and heapq module in Python). Since we take O(log *K*) > time for each of K steps, the algorithm takes only O(*K* log *K*) time, > which is fast enough to solve test set 2. > > > On Wed, Aug 22, 2018 at 5:36 PM Eugene Yarmash <[email protected]> > wrote: > >> Hello. I've tried to solve the problem using Python's heapq module, but >> that gave me 'Time limit exceeded' for the 2nd test case. I've checked >> the analysis and it claims that this approach should work for the 2nd >> test case. Am I missing something here? My code: >> >> from heapq import heappop, heappush >> >> >> def main(): >> T = int(input()) # the number of test cases >> >> for case in range(1, T+1): >> N, K = map(int, input().split()) >> >> h = [-N] >> >> for _ in range(K): >> chunk = -heappop(h) >> if chunk & 1: >> if chunk == 1: >> min_s = max_s = 0 >> else: >> min_s = max_s = chunk >> 1 >> heappush(h, -min_s) >> heappush(h, -max_s) >> else: >> max_s = chunk >> 1 >> min_s = max_s - 1 >> heappush(h, -min_s) >> heappush(h, -max_s) >> >> print('Case #{}: {} {}'.format(case, max_s, min_s)) >> >> >> main() >> >> >> >> >> >> -- >> Regards, >> Eugene >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To post to this group, send email to [email protected]. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/google-code/f6b8ece9-0d14-5a39-d01f-d75d1acf9187%40gmail.com >> . >> For more options, visit https://groups.google.com/d/optout. >> > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CAHaiWHNQ65sUwHzCPoxyseLq_DRRdiYjothB4W%3DZk9Dr25iwWg%40mail.gmail.com > <https://groups.google.com/d/msgid/google-code/CAHaiWHNQ65sUwHzCPoxyseLq_DRRdiYjothB4W%3DZk9Dr25iwWg%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > > > For more options, visit https://groups.google.com/d/optout. > > > -- > Regards, > Eugene > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAHaiWHOPtY_xEgVkOyUSoF62KoXsC4y3_678%2Bt69SSMVWToUmA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
