Hi everyone
I'm trying to solve problem http://acm.ro/2010/prob/probleme/D.pdf .
In short, the problem gives N contests and M problems ( N <= 15 , M <= 50 ). For each problem you have determined a set of contests you can give that problem to. Also you know the required number of problems for each contest. Find out the maximal number of different contests for which you can simultaneously compose complete problemsets from the given set of problems. All problems in the problemsets must be unique, i.e. no problem can be used twice in different problemsets.
Sample Input :
4 5
IOI 3
IPSC 2
TopCoder 2
SEERC 10
IOI
IPSC TopCoder
IOI IPSC
IOI IPSC
TopCoder SEERC
Answer : 2 ( IOI takes problem 1, 3, 4 and TopCoder takes problem 2, 5 )
I found a solution seems using Max-Flow algorithm. Since the input size is quite small and I have no idea about Max-Flow algorithm yet, I wonder if there is a dynamic programming solution for this problem ?
Thanks in advanced.