INSQ15_E - Editorial

## Who is at kth position


PROBLEM LINK:

Contest

Practice

Author: Aman Mittal
Tester: Md Shakim
Editorialist: Aman Mittal

DIFFICULTY:

Cakewalk

PREREQUISITES:

Sorting, Basic programming

PROBLEM:

You are given score and multiplier of each team. Net score of ith team is calculated as score of ith team * multiplier of ith team. You have been asked Q questions to tell the Kth ranked team which is sorted in non increasing order, if two teams have same net score then team with lesser ith value comes first.

EXPLANATION:

Take the details of each team in a vector/array of pair < long long int, int> / struct{ long long int, int} and do either of two ways,

1- Do any sorting of O(NlogN) complexity and apply a suitable comparator function.

bool comp(const pair< long long int , int > &A , const pair < long long int , int > &B ) {
	if(A.first > B.first) {
		return 1;
	}
	if((A.first == B.first) && (A.second < B.second )) {
		return 1;
	}
	return 0;
}

</pre>

2- You can tweak in the way of inserting values in the pair. You can take the second key and store it as -1 * second key value. And then apply a inbuild sort() as

sort(vectorOfPair.rbegin(), vectorOfPair.rend());  //sorting in a reverse order

It will do a sorting of descending order on first key and on same first key second key will be sorted in descending order. But as we have done -1 * second key so for same first key values, second key having less negative value will be placed above than a more negative value.

See in this example:

Suppose there are 5 teams and netscore of each team is given like:

Net Score   Team Number

24           1

2            2

12           3

80           4

12           5

If you push these values in a vector of pairs such as

 make_pair(NetScore, -1 * TeamNumber); </pre>

and sort the vector in descending order as it was mentioned above, then the vector will become

Net Score   Team Number

80           -4

24           -1

12           -3

12           -5

2            -2

NOTE that on same net score value 12, -3 is put above than -5 as -3 > -5

Now comes the query part, as query is of size 104 we can directly tell in O(1) that which team is at Kth position by just querying the sorted vector as:

-1 * vector[K - 1].second </pre>

Common mistakes:

As we have analysed few solutions we have found some common mistakes done by the teams:

1- Not taking long long int as the first key of the pair<>. As score S and multiplier M are both of order 106 so by multiplying both to calculate net score we get a value which is of order ~ 1012 which can not be taken in int

2- Not using a proper comparator function in sorting.

TIME COMPLEXITY

O(NlogN)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author Solution

Tester Solution

https://www.codechef.com/viewsolution/8051410 whats wrong with this solution

We can avoid writing a compare function by passing n-i as the second parameter instead of i.

Like this : http://ideone.com/MB2Tik

1 Like

Hi,

1 Like

Yes, this is also a correct alternative way to make the pair avoiding comparator function.