Rex-myFriendForever's blog

DP approach for Problem D in Southeastern European Regional 2010 ?
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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Such constraints imply a bruteforce solution... so first you could choose a set of contests and test if it's possible to create complete problemsets.

That can be done by a simple maxflow: from supersource to problems, there are max. edge capacities 1, from every problem to any contest that it can be assigned to, it's max. cap. 1, and from every contest to the supersink, max. cap. is the number of problems in complete problemset. A Ford-Fulkerson algorithm for that; iff maxflow = sum of sizes of complete problemsets, it's possible.

The total complexity would be O(M^3 2^N) worst case, which could pass the tests if optimized carefully. Not the brightest solution out there, but easy to do.

I don't see a DP solution here. The problem is that while multiple combinations of problems may be suitable for one set of conditions, it could radically change after tweaking those conditions just a bit.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks a lot ! I totally don't know that max-flow algorithm is straightforward for this problem, I thought it is some kind of DP-trick...I have to read carefully about max-flow =.=

    → Reply