PROBLEM LINK:
Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Combinatorics, Fundamental principle of Counting.
PROBLEM:
Given skill S of N programmers (N is even), we want to find number of ways to form teams such that There doesn’t exist two teams (A, B),(C,D) such that S_D > S_B and S_A > S_C.
SUPER QUICK EXPLANATION
- Sort the scores in descending (or ascending) order. Try to make pair from left to right while handling programmers having same skill level combined.
- If there are X programmers with same skill, and X is odd, We select the player which will be left out first, and then count the number of ways to make pairs out of remaining players.
- In case we have a left over from higher (or lower) skill yet to be paired, We count first, the number of ways to select one player out of all players of immediately lower (or higher) skill. After that, we do what i mentioned in second point.
EXPLANATION
First of all, As i usually do, consider constraint that no two players have same skill level. We can see that there will always exist exactly one valid team formation, which pairs players like, best with second best, third with fourth and so on till all players are paired.
So, we know, that the multiple valid team formulation arises only when there are multiple players with same skill level.
Now, since this problem involves combinatorics, which i like to explain by examples, so, here we begin examples.
Consider example scores 2,2,2,2.
We can see that player at position 1 can pair with any of three, and remaining two players pair with each other, giving 3*1 = 3 ways.
Consider example scores 2,2,2,2,2,2.
Same idea, just that first player has 5 choices. Now, we have four players left. Let us assume, we pair the leftmost unpaired player, and count number of ways for him to form team. He has 3 choices. After removing him and his partner too, only two players left, which pair with each other, giving 5*3*1 = 15 ways.
Consider example scores 2,2,2,2,2,2,2,2.
Once again, Same idea, So i ask you to apply this idea to calculate it before seeing its explanation in secret box.
Click to view
Number of choices for leftmost unused player is 7. Six players left.
Number of choice for leftmost unused player is 5 now. Four players left.
Number of choice for leftmost unused player is 3 now. Two players left.
Number of choice for leftmost unused player is 1 now. No players left.
Final number of ways is 7*5*3*1 = 105 ways.
You all must be wondering why he’s boring us with same test case. My point is to ask you all to notice the pattern.
Last example of this type. 2,2,2,2\dots 2 N times.
Now, what did we learn from previous examples. First player has (N-1) choices, next leftmost unused player has (N-3) choice and so on.
Final Number of ways become (N-1)*(N-3)* \dots *5*3*1. This can also be calculated as \frac{(2*m)!}{2^m*m!} where m = n/2.
Looking for a proof? Here you go.
When all skill levels are same, the problem is to count number of ways to divide 2*M elements into M pairs. We can see, that every permutation of elements correspond to a team formation, where First player is paired with second, third player is paired with fourth and so on. Number of permutations is (2*M)!
For example, Take any permutation, say for M = as 1234, this correspond to teams (1,2),(3,4). But, we see, that permutation 1243 also correspond to same teams, as order of players in a team doesn’t matter. Team (1,2) is same as (2,1). Since there are M pairs, there are 2^M different permutations representing same teams, just having their players swapped. So, Number of ways of forming team without double counting these swaps is \frac{(2*M)!}{2^M}.
But, the ordering of teams is also double counted. Permutation 1234 represent teams (1,2),(3,4) which is same as (3,4),(1,2) represented by permutation 3412.
To avoid double counting, we need to see how many times each team formulation is being counted. It is easy to see that, we have M unordered pairs. Each permutation of these M pairs will be counted. This means that there are M! permutations corresponding to each team, so, we just divide the Number of ways by M!.
Final Number of ways become \frac{(2*M)!}{2^M*M!} which gives us correct number of ways to divide 2*M players into unordered pairs where permutation of teams doesn’t matter. This is what we require.
Till now, we only considered all examples which had same skill level for all players.
Consider another example 1 1 2 2 2 2.
We can see, that players of skill level 1 will be paired among each other, while players of skill level 2 will be paired among each other. By Fundamental principle of counting, we see these are just product of above two. Number of ways for team with skill 1 is 1, while Number of ways to form teams with skill 2 are 3*1. Total Number of ways is just 1*3 = 3 ways.
Now, we know how to count number of teams When there are even number of players with same skill.
But when number of players of a skill level is odd, One player of that skill level has to be paired with a player of different skill. Now, A player cannot be paired with anyone having not immediately lower (or higher) skill. Player with skill 1 can never be paired with player having skill 3 as long as there exist even a single player having skill 2.
Suppose 1 2 2 3 is the skill levels. Player 1 can be paired with either player 2 or player 3. Other person can be paired with player 4, resulting in 2 total ways.
Our second last example for today is 1 1 1 1 1 2 2 2 2 2 2 3 3 3.
We handle players of same skill together, in increasing (or decreasing, which you like) order of skill.
First we have 5 players of skill 1. We know, One of the player of skill 1 will be paired with player of skill 2. Number of ways to select that 1 player is 5. Remaining 4 players divided into unordered pairs in 3*1 ways.
Then we have 6 players of skill 2 and one player of skill 1 left. Firstly, we can pair player with player 1 with any of the six, In six ways. Now, 5 players of skill level left. One chosen player will be left out, we can choose in 5 ways. 4 players left, which are divided into pairs in 3*1 ways.
Lastly, we have 3 players of skill 3 and one player of skill 2 to be paired. Once again, we choose player to be paired with player of skill 2, which can be done in 3 ways. Two players of skill 3 left, which can be divided into teams in 1 way.
Since all these events have to be performed together, then by principle of counting, the final answer is just product of all these. that is. Required Number of ways is 5*3*6*5*3*3*1 = 4050 ways which is the required answer.
This was all for today, though you can read more about the proof here, as well as, you can find proof by searching about “Dividin N elements into pairs.”
Bonus Question
Instead of SnackDown, Given skill of N players, Make teams for ACM-ICPC regionals. It is given that N is divisible by 3. Leave answer in comments.
Time Complexity
Time complexity is O(N*LogN) due to sorting. Ordered Frequency map can also be used and is preferable.
PS: The solutions based on same idea, which tried to make a frequency array instead of frequency map, got TLE, because of the test file can have up to 1000 test cases of small size, in which case, your solution tried to complete O(T*10^6) iterations which will surely time out.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
According to the statement one (1,2) and (2,3) can not be a valid pair for the case described in editorial where (1,1),(1,1),(1,2),(2,2),(2,2),(2,3),(3,3) pairs are formed