The problem is essentially, given $2\leq n\leq 10^5$ people, where the $i^{\text{th}}$ person has a skill level of $b_i$ in billiards and $p_i$ in pool, can you split the people into teams of two such that every team has the exact same skill in both pool and billiards?
Checking through all pairs is not an option since that would be $O(n^2)$. So first we notice the following conditions for impossibility:
- $n$ is odd
- $\frac{1}{n/2}\sum_{1\leq i\leq n}^{b_i}$ is not whole, and same for $p_i$'s.
But we can also have impossibility if we have these conditions but some person has no possible pairings. The intuition to make progress is that we need to pair a small skill with a large skill, otherwise they won't balance. This hints at the following observation.
Obs: The person with the minimum skill in billiards must be paired with the person of maximum skill.
proof. Suppose this is not the case. Consider the skill levels of billiards in non-decreasing order
$$b_1', b_2', ..., b_n'$$
then some $b_i'$ for $i>1$ is paired with $b_n'$. Suppose $b_1'$ is paired with $b_j'$ for $i\not = j$.
Since $b_1' < b_i'$ and $b_j' < b_n'$, we know that $b_1' + b_j' < b_i' + b_n'$, thus the sums are not equal. A contradiction.
This directly suggests the approach of sorting the skill levels of the people for billiards, checking if the min and max skilled people can be paired in both billiards and pool, if not then it is impossible, if yes, then move to the next min and max pair until all have been looked at. This only requires $O(n\log{n} + n) = O(n\log{n})$ time and we are done.
No comments:
Post a Comment