Page 1 of 1

11124 - Troubles for Modern Days Problemsetters

Posted: Sat Oct 14, 2006 7:38 pm
by Alec
I got TL for thousand times. Is there any one give me some help on it. Thank you very much!!

Posted: Sat Oct 14, 2006 7:45 pm
by fpavetic
there is a way to find kth element in unsorted sequence in O(n) average, where n is the length of the sequence.

Posted: Sun Oct 15, 2006 5:42 am
by Jan
The problem states
IList(5,0,1)+IList(3,6,0)+IList(5,5,-1) generates the list: 0 1 2 3 4 5 6 6 6 5 4 3 2 1 0.
shouldn't it be
IList(5,0,1)+IList(3,6,0)+IList(5,5,-1) generates the list: 0 1 2 3 4 6 6 6 5 4 3 2 1.

Posted: Sun Oct 15, 2006 9:14 am
by little joey
You are absolutely right :oops:
Luckily it doesn't matter for the samples...

Posted: Sun Oct 15, 2006 5:17 pm
by FAQ
Some I/O please :( I still got WA
is there any test like NList(0) ?

Posted: Sun Oct 15, 2006 7:29 pm
by kalinov
Watch out for overflow... Try this:

Code: Select all

input:
5
RList(10,-2147483648,2147483647,4294967295)
0

output:
Case 1: 2139940657

Posted: Sun Oct 15, 2006 7:57 pm
by Jan
kalinov wrote:Watch out for overflow... Try this:

Code: Select all

input:
5
RList(10,-2147483648,2147483647,4294967295)
0
output:
Case 1: 2139940657
I think there are no test cases like that. The problem is elsewhere. Because reading input, generating list, finding the kth number... so, errors can occur.
FAQ, you can easily make random cases and check your code. To check the output just sort the list and then match the result with the calculated result (calculated in O(n) time). By the way thanks Mr. Joey for this nice problem.

can someone give me a better algorithm??

Posted: Sat Sep 08, 2007 7:20 pm
by Mr.south
I always got TLE

Is there any more efficient way to generate the number list ?

My algorithm is:

generate the list and sort it by qsort and got TLE