**## 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 i^{th} team is calculated as score of i^{th} team * multiplier of i^{th} team. You have been asked Q questions to tell the K^{th} ranked team which is sorted in non increasing order, if two teams have same net score then team with lesser i^{th} 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 **10 ^{4}** we can directly tell in

**O(1)**that which team is at

**K**position by just querying the sorted vector as:

^{th}```
-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 10^{6} so by multiplying both to calculate net score we get a value which is of order ~ 10^{12} which can not be taken in **int**

2- Not using a proper comparator function in sorting.