PROBLEM LINK:Setter: Hasan Jaddouh DIFFICULTY:EasyMedium 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
EXPLANATIONFirst 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. 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 $(N1)$ choices, next leftmost unused player has $(N3)$ choice and so on. Final Number of ways become $(N1)*(N3)* \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 QuestionInstead of SnackDown, Given skill of $N$ players, Make teams for ACMICPC regionals. It is given that $N$ is divisible by 3. Leave answer in comments. Time ComplexityTime 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 Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 14 Oct '18, 12:43

I love your editorials!! Such clear explanation!! Thanks a lott <3333 answered 17 Oct '18, 22:00
@taran_1407
I didn't know taran tarini really exist XD....
(19 Oct '18, 19:43)
Even i do not know this profile. Seems like a prank on me by my dear friends. xD
(19 Oct '18, 20:16)
.....XDDDD
(21 Oct '18, 19:56)

Can anyone please help me with my code.Its giving wrong answer.I have tried it many times.Link to my solution is below. Link : https://pastebin.com/i4w12XFr answered 18 Oct '18, 15:24

What’s wrong with this code? It works on all the cases mentioned in the editorial above answered 18 Oct '18, 15:47

The answer for bonus question is : The final of ways to form the acmicpc team is (3*N)!/(3^M * (M!)) answered 18 Oct '18, 23:20

Can someone help with my code? It's giving a wrong answer, but my local testing gives the right answer and I use the method from the editorial. answered 19 Oct '18, 07:30

Can you explain the logic behind doing %mod after every change in 'ans', please? answered 19 Oct '18, 09:17

i have a query : suppose the s[] is [1,1,2,2] so, is [1,2][1,2] not the correct pairing?? answered 19 Oct '18, 11:28

@maistro017, no its not. arrange ur teams in this way [2,1], [1,2] now here D>B and A>C so it satisfies the condition given in the question so this formation is invalid. The correct formation will always be in a sorted order no matter how you try. So here it will be [1,1],[2,2] answered 19 Oct '18, 17:30
