Discussion:
Q4 CPU exceeded
(too old to reply)
Jacob Malevich
2011-11-15 20:46:40 UTC
Permalink
All of my commands for Q4 have O(logn) runtime, and the first two test
cases say that they have equal output to the test. It is only the last
test that is giving CPU exceeded. Any ideas why this test case may be
saying that?
Dan Lizotte
2011-11-16 00:00:15 UTC
Permalink
Post by Jacob Malevich
All of my commands for Q4 have O(logn) runtime, and the first two test
cases say that they have equal output to the test. It is only the last
test that is giving CPU exceeded. Any ideas why this test case may be
saying that?
I see you got it fixed. Any words of wisdom for people still working on
it? (No pressure.)
Jacob Malevich
2011-11-16 00:43:23 UTC
Permalink
Post by Dan Lizotte
Post by Jacob Malevich
All of my commands for Q4 have O(logn) runtime, and the first two test
cases say that they have equal output to the test. It is only the last
test that is giving CPU exceeded. Any ideas why this test case may be
saying that?
I see you got it fixed. Any words of wisdom for people still working on
it? (No pressure.)
Sure! What I realized is that using difference with two sets wasn't
actually logn runtime unless the second set is of size one. I also found
out that using before and after was the fastest way to implement the
best and score function since they both take O(logn). My program was
just failing with very large test cases since my best and score were
running in O(nlogn),
Dan Lizotte
2011-11-16 01:07:01 UTC
Permalink
Post by Jacob Malevich
Post by Dan Lizotte
Post by Jacob Malevich
All of my commands for Q4 have O(logn) runtime, and the first two test
cases say that they have equal output to the test. It is only the last
test that is giving CPU exceeded. Any ideas why this test case may be
saying that?
I see you got it fixed. Any words of wisdom for people still working on
it? (No pressure.)
Sure! What I realized is that using difference with two sets wasn't
actually logn runtime unless the second set is of size one. I also found
out that using before and after was the fastest way to implement the
best and score function since they both take O(logn). My program was
just failing with very large test cases since my best and score were
running in O(nlogn),
Ok great; thanks for giving us your two cents.

Loading...