## 11124 - Troubles for Modern Days Problemsetters

Moderator: Board moderators

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

### 11124 - Troubles for Modern Days Problemsetters

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
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
Contact:
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
You are absolutely right
Luckily it doesn't matter for the samples...
FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
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
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
Contact:
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??

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