That explains it! Thanks for clearing up the confusion, Pablo. I forgot
that problem had shown up twice.
On Thu., Aug. 23, 2018, 10:30 'Pablo Heiber' via Google Code Jam, <
google-code@googlegroups.com> wrote:
> Part of the confusion is that the problem appeared in the 2017
> qualification round and in the 2018 practice round, and you can try to
> practice in both of them. I would expect your code to reasonably solve the
> 2017 qualification round version.
>
> For the 2018 practice round, it's possible that the combination of test
> data / time limit made it impossible or too hard to pass that version of
> the solution in a slow language like python. We usually check that problems
> are solvable in Python for the early rounds, and this was also the case,
> but we don't necessarily check that alternative not-full solutions also
> pass the TL when implemented with really high constants or in slow
> languages, and this is especially true for a non-competitive practice round
> since we mostly adapted the already prepared problem instead of preparing
> from scratch for the new platform.
>
> I would suggest you try your code in the 2017 version for this problem.
> Problems that debuted in 2018 should have their limits set up better for
> Python users.
>
> Best,
> Pablo
>
> On Thu, Aug 23, 2018 at 9:15 AM Cygin <mangin.cypr...@gmail.com> wrote:
>
>> I think you have misunderstood the analysis. To keep a reasonable
>> complexity, you need to make sure that your set cannot contain several
>> times the same element.
>> See the comment saying "This is a set, not a multiset!". Therefore, heapq
>> will not be the right datastructure for this, as it does not allow to check
>> if an element is in the heap easily.
>>
>> So basically, you need anything resembling a set, along with a way to
>> count the number of occurrences of a given element.
>>
>> On Thursday, August 23, 2018 at 1:37:05 AM UTC+2, Eugene Yarmash 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 google-code+unsubscr...@googlegroups.com.
>> To post to this group, send email to google-code@googlegroups.com.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/google-code/f5f98492-0002-432d-bd93-f9dd068d9fc8%40googlegroups.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 google-code+unsubscr...@googlegroups.com.
> To post to this group, send email to google-code@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/CANa5jcCP7CopjZM991oZUTHpZ_-Sbe7-s1Eg%3DU52RpxHP%2Bz%3DCw%40mail.gmail.com
> <https://groups.google.com/d/msgid/google-code/CANa5jcCP7CopjZM991oZUTHpZ_-Sbe7-s1Eg%3DU52RpxHP%2Bz%3DCw%40mail.gmail.com?utm_medium=email&utm_source=footer>
> .
> 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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CAHaiWHNP93_UaW_0BDoFHLA2qviKmD1_asmCoA2pzALeDhZb0w%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
