[Solved]: Efficiently selecting the median and elements to its left and right

Problem Detail: 

Suppose we have a set $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ of $N$ coders.

Each Coders has rating $R_i$ and the number of gold medals $E_i$, they had won so far.

A Software Company wants to hire exactly three coders to develop an application.

For hiring three coders, they developed the following strategy:

1. They first arrange the coders in ascending order of ratings and descending order of gold medals.
2. From this arranged list, they select the three of the middle coders. E.g., if the arranged list is $(a_5,a_2,a_3,a_1,a_4)$ they select $(a_2,a_3,a_1)$ coders.

Now we have to help company by writing a program for this task.

Input:

The first line contains $N$, i.e. the number of coders.

Then the second line contains the ratings $R_i$ of $i$th coder.

The third line contains the number of gold medals bagged by the $i$th coder.

Output:

Display only one line that contains the sum of gold medals earned by the three coders the company will select.

Asked By : Jack

Answered By : Opt

This is a problem of selecting the $k$th smallest element from the list solved by a class of algorithms called the Selection Algorithms. There exist deterministic linear time selection algorithms so your problem can be solved in linear time by selecting the $n/2,n/2-1,n/2+1$th smallest elements from the original unsorted list.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1231

3.2K people like this

 Download Related Notes/Documents