Rex-myFriendForever's blog

By Rex-myFriendForever, 11 years ago, In English

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.

Full text and comments »