11668 - How Many Teams

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

11668 - How Many Teams

Post by rushel » Tue Sep 15, 2009 10:43 pm

can anybody please give some test cases of the following problem:

http://uva.onlinejudge.org/index.php?op ... oblem=2715

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Re: 11668

Post by rushel » Wed Sep 16, 2009 8:44 am

Thanks got AC

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11668 - How Many Teams

Post by tryit1 » Thu Sep 17, 2009 2:37 am

Can you give some hints, I thought of maximum matching but it is too complicated

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm

Re: 11668

Post by ardiankp » Thu Sep 17, 2009 9:46 am

Hint please.. I've tried DP of configurations, but always get TLE.

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Re: 11668

Post by rushel » Fri Sep 18, 2009 8:56 pm

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.

Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

Re: 11668

Post by Khongor_SMCS » Sat Sep 19, 2009 9:22 am

Thanks your hint rushel.
I missed this part
Due to the limited number of seats, a department can send at most 3 members.

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11668

Post by tryit1 » Sat Sep 19, 2009 9:47 am

if we do as above, don't we need to track which department has allocated student to which partition.

f(a,b,c) = f(a-x,b,c)*Bin(a,x) *Bin(b,y)*Bin(c,z) *( k!). (x+y+z=k)

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm

Re: 11668

Post by ardiankp » Sat Sep 19, 2009 6:58 pm

I missed that part also. Thanks!

Post Reply

Return to “Volume 116 (11600-11699)”