## Who is at kth position
PROBLEM LINK:
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.