11668  How Many Teams
Moderator: Board moderators
11668  How Many Teams
can anybody please give some test cases of the following problem:
http://uva.onlinejudge.org/index.php?op ... oblem=2715
http://uva.onlinejudge.org/index.php?op ... oblem=2715
Re: 11668  How Many Teams
Can you give some hints, I thought of maximum matching but it is too complicated
Re: 11668
let, a = number of departments which has 1 student, b = number of departments which has 2 students and c=number of departments which has 3 students.
Now let dp[a][c]=number of permutations
we know 1*a+2*b+3*c=N and N%K==0 so we have to make N/K groups
Suppose now we want to form a group, we can choose c1 students from departments which have 1 students, c2 students from departments which have 2 students and c3 students from departments which have 3 students such that c1+c2+c3=K.
Now let dp[a][c]=number of permutations
we know 1*a+2*b+3*c=N and N%K==0 so we have to make N/K groups
Suppose now we want to form a group, we can choose c1 students from departments which have 1 students, c2 students from departments which have 2 students and c3 students from departments which have 3 students such that c1+c2+c3=K.

 New poster
 Posts: 15
 Joined: Thu Jun 18, 2009 12:01 pm
 Contact:
Re: 11668
Thanks your hint rushel.
I missed this part
I missed this part
Due to the limited number of seats, a department can send at most 3 members.
Re: 11668
if we do as above, don't we need to track which department has allocated student to which partition.
f(a,b,c) = f(ax,b,c)*Bin(a,x) *Bin(b,y)*Bin(c,z) *( k!). (x+y+z=k)
f(a,b,c) = f(ax,b,c)*Bin(a,x) *Bin(b,y)*Bin(c,z) *( k!). (x+y+z=k)