KSMALL - K-th smallest number


Given an array of (pseudo) random numbers generated by the C++ function below, your task is to find the K-th smallest number of all the numbers.

unsigned array[5000000];

void randomize(unsigned a,unsigned b,unsigned mod)
{
	for( int i=0 ; i<5000000 ; i++ )
	{
		a = 31014 * (a & 65535) + (a >> 16);
		b = 17508 * (b & 65535) + (b >> 16);
		array[i] = ((a << 16) + b) % mod;
	}
}

Note that the computation might overflow, but we only care about the last 32 bit of each result so it doesn't matter.

Input

One line with 4 numbers (a, b, mod, K) separated by space.

0 < a, b < 65535

< mod < 232-1

1 < K < 5x106

Output

K-th smallest number of all the generated numbers.

Example

Input:
2 3 100000007 23

Output:
434

 

 


hide comments
priyanshul: 2018-11-21 13:07:06

its showing segmentation fault, what should I do? (i am using quicksort to sort the array and then reading the (k-1)th element of the array.

jmr99: 2018-10-13 17:18:18

if(heard about ""nth_element"" stl in c++)
cout<<"go for it ";
1.partial_sort and priority_queue gives tle

Last edit: 2018-10-13 17:41:28
akki: 2017-04-14 13:36:15

Hint: Learn 3-way partitioning (quicksort).

aakash_s: 2016-09-23 08:29:41

I have tried O(n) approach with optimizations
still it shows time limit exceeded.
I don't understand what to do next

sivakumarar: 2016-09-22 19:07:43

How to find which of the 20 test case failed. Is there are way to get the test input files to test and debug it locally , before uploading the solution.

Sarot Busala: 2015-07-01 09:33:25

I have tried 3 different ways, one of this is O(N) approach and got only TLE. :(
Is the time limit too strict??

:D: 2015-03-10 22:10:15

Re Jason S: It's the sorted(array)[k-1] version. That way for every K in the specified input range there is always a valid solution.

Rahul Lingala: 2015-01-23 21:58:07

Time limit is too strict. I know the perfect algorithm, but still my solution is not getting accepted even after optimising it to the maximum extent.

Andy: most people who solve this don't even reach half the time limit, so I think it's reasonable.

Last edit: 2015-01-30 14:46:00
Jason S: 2014-08-24 04:42:56

Is it supposed to be sorted(array)[k-1] or the kth unique value? I have some thousands of testcases based on the former (which the example implies) that pass but am getting WA.

anurag garg: 2014-03-25 13:41:50

@author can you have a look at my submission:11324082
I am getting TLE after 20th case
is there any chance to get AC with this approach
thanks

Ans: The judge will run all 20 test cases even if you fail at some point. It is possible to get accepted with any O(n) approach, although some optimization might be required.

Last edit: 2014-03-25 21:04:16

Added by:Andy
Date:2014-03-10
Time limit:0.100s-0.246s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All