Difficulty : Hard
Piscine Tycoon is a new popular game.
In this game, there are two teams :
A game consists of two players, one playing the students team and one playing the assistants team. At the end of the game, both players obtain some points (integer values). The total score is the average of both points.
It turns out that the students team points and the assistants team points are not correlated. That is, a player playing the students team will always have the same amount of points at the end of the game no matter which assistant player was playing against him.
In the tournament, every player will play against each other player of the opposite team (i.e. a students team player will play against every assistants team player and vice versa). At the end of the tournament, all scores are calculated (recall that the score is the average points between the students team and the assistants team) and ordered in non descending order.
In other words, if $C$ contains every scores : $C_k = \frac {A_i + B_j} 2$ such that $C_1 \le C_2 \le … \le C_{M \times N}$.
We provide you two arrays of integers containing the points for each player :
Because it is too long to display every score, your goal is to print only the $K$-th score in the ordered score list.
3
All possible scores are [1.5, 2.5, 2.5, 3, 3, 3.5, 4, 4, 4.5] in order. The 5th one is 3.
Can you do this in $O(max(N, M) \times log(min(N, M)))$ ?
Let’s reformulate a bit the problem : Given $A$ and $B$ and the sorted list of average values $C_k = \frac {A_i + B_j} 2$, what is the $K$-th average value ?
First of all, let’s see the problem using a grid on the example ($A$ = [1, 4, 3], $B$ = [5, 2, 4], $K$ = 5). $A$ is the vertical and $B$ the horizontal. Since the initial order of $B$ and $A$ doesn’t modify the problem, we can sort them (only $B$ has to be sorted in this solution though).
| $A$ / $B$ | 2 | 4 | 5 |
|---|---|---|---|
| 1 | 1.5 | 2.5 | 3 |
| 3 | 2.5 | 3.5 | 4 |
| 4 | 3 | 4 | 4.5 |
In order, the average values are [1.5, 2.5, 2.5, 3, 3, 3.5, 4, 4, 4.5] (3 is the $K = 5$-th value).
Let $x$ be the $K$-th value (the result we want).
The $K$-th value means that it exists strictly less than $K$ values strictly less than $x$. It also means that there are $K$ or more than $K$ values less or equal to $x$ (if all average values are distinct, then it exists exactly $K$ values less or equal to $x$).
If we count the number of values less or equal to any $x$, we can deduce our result. This can be done using binary search.
The minimum and maximum average values are $0$ ($A$ and $B$ contains only positive integers) and $\frac {max_i(A_i) + max_j(B_j)} 2$ respectively, this is the initial interval.
At every iteration, we have to query whether the $K$-th value is lower or higher than the $mid$ value.
To do so, we can count the number of average values strictly less than $mid$. If this number is strictly less than $K$, then it is guaranteed that $x$ is after $mid$ (so the new interval is [mid + 1, r]).
We call the query function $count\_lower$.
Time complexity $O(log(max(A) + max(B)) \times O(count\_lower))$
This function takes as parameter $x$ and returns how many average values are strictly less than $x$.
We can compute this in quadratic time complexity but it is necessary to have an efficient query function, let’s use again binary search !
For each row $i$ of the grid, we combine $A_i$ with every $B_j$, $A_i$ doesn’t change so we can binary search the last value of $B_j$ such that $\frac {A_i + B_j} 2 < x$.
The query function is then $\frac {A_i + B_{mid}} 2 < x$ (note that $mid$ is the pivot in this binary search, not the previous one).
Time complexity $O(N \times log(M))$
Total time complexity $O(log(max(A) + max(B)) \times N \times log(M))$
It is good to avoid floating points when possible. In this exercise, we can notice that $\frac {a + b} 2 = \frac 1 2 \times (a + b)$, we can compute the sum $a + b$ instead of the average and then divide the result by $2$.
// Count how many values are strictly lower than x
int count_lower(const vector<int> &a, const vector<int> &b, int x) {
int n_lower = 0;
for (int i = 0; i < a.size(); ++i) {
// Find how many values < x by binary search
int l = 0;
int r = b.size();
while (l < r) {
int mid = l + (r - l) / 2;
int current_avg = (a[i] + b[mid]) / 2;
if (current_avg < x) {
l = mid + 1;
} else {
r = mid;
}
}
n_lower += l;
}
return n_lower;
}
float tournament(vector<int> a, vector<int> b, int k) {
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// Use integers, not floating points
for (auto &e : a)
e *= 2;
for (auto &e : b)
e *= 2;
// We have to find the last mid where count_lower(a, b, mid) < k is true
int l = 0;
int r = (a.back() + b.back()) / 2 + 1;
while (l < r) {
int mid = l + (r - l) / 2;
// Query whether the K-th value is lower or higher than the mid value
if (count_lower(a, b, mid) < k) {
l = mid + 1;
} else {
r = mid;
}
}
// r points to the first count_lower(a, b, r) >= k
return (r - 1) * .5f;
}
Full code