Can Anyone explain the solution/approach for the last question of Snack Down Qualifier 2019.
Thanks.
Here’s a worked out example
Input: 3 3 3 3 3 2 2 2 2 1
Output: 180
Explanation:
It’s obvious from the example given with the problem that the higher ranked players form teams first and the teams of lower ranked players depends on them, so it makes sense to first sort the input in reverse order (in this case it’s already sorted).
Next, consider the highest rank players, five players with rank 3, now since they are 5 one of them will be left out and will be forced to form a team with one of the four rank 2 player. So there are 5x4=20 possibilities of making that pair, once this pair is made the reamining four rank 3 players can form teams amongst themselves in 3 ways - (ab cd), (ac bd), (ad bc). So 20x3=60 possibilities till now.
Now, the rank 3 players are done and one of the rank 2 player is also “consumed” in forming a team with the rank 3 player. So we have reduced our original problem a new subproblem - 2 2 2 1.
Repeating the same argument as above the number of teams possible for this subproblem is 3. Therefore 60x3=180 total possiblities.
1 Like