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]
<mailto:[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]
<mailto:google-code%[email protected]>.
To post to this group, send email to [email protected]
<mailto:[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]
<mailto:[email protected]>.
To post to this group, send email to [email protected]
<mailto:[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/fdaeb3ff-52ef-f62c-8fb7-6f5e91c1e342%40gmail.com.
For more options, visit https://groups.google.com/d/optout.
