#11204 - Musical instruments
|Solution Description: ||I completely overthought this problem the first time, and the second time.|
It's simply a combinatorics solution. Create an instruments array, and increment the elements corresponding to the students' first choices. The other choices are irrelevant.
Now, just go through the array, and multiply all the elements > 1 together. There's your answer!
This is because for each instrument in competition, there are n students that could have it (where n is the number of students with it as a first priority).
From there it's simply the combinations of students for each instrument.
At first I thought this was a DP - although I'm sure you could probably think one up. Then I misread the question, and thought that in addition to the correct solution above, you had to multiply THAT by all the combinations of students who didn't get the instrument they wanted - getting instruments they don't want.
|Solution Description: ||The only thing that matters in the input is which instrument is priority 1 for each student. We want the number of ways to maximize how many priority 1 instruments get assigned.|
If there are no conflicts for priority 1 instruments, then there is only 1 way to assign them: give everybody what they want. When more than one student wants the same instrument though, then we can choose any of them.
So, if 2 students want instrument A, 4 students want instrument B, and 3 want instrument C, then we must pick one student from each group. There are 2*4*3 ways of doing this, so the answer is 24.
Keep an array, a, where a[i] is the number of students that have priority 1 for instrument i. Output the product of all non-zero cells in a.
Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By