11124 - Troubles for Modern Days Problemsetters

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Alec
New poster
Posts: 8
Joined: Sun Mar 28, 2004 9:00 pm

11124 - Troubles for Modern Days Problemsetters

Post by Alec »

I got TL for thousand times. Is there any one give me some help on it. Thank you very much!!
fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post 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.
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post 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.
Last edited by Jan on Sun Nov 26, 2006 10:13 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

You are absolutely right :oops:
Luckily it doesn't matter for the samples...
FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ »

Some I/O please :( I still got WA
is there any test like NList(0) ?
kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

Post by kalinov »

Watch out for overflow... Try this:

Code: Select all

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

output:
Case 1: 2139940657
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post 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.
Ami ekhono shopno dekhi...
HomePage
Mr.south
New poster
Posts: 11
Joined: Thu Jan 25, 2007 1:45 pm

can someone give me a better algorithm??

Post 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
Post Reply

Return to “Volume 111 (11100-11199)”