### dpasztor's blog

By dpasztor, history, 10 months ago, There is a set of items. You are given some subsets of these items. (each has a given price)

You should calculate how much money you need to spend to have a full set and which subsets you need to buy.

(Number of subsets is <= 3000)

(It is not guaranteed that there is a solution)

Easier version: You know that the main set is {1,2,3,4,5,6,7,8,9,10,11,12,13}

Example for easier version:

1,2,3 price: 3

4,5,6 price: 3

7,8,9 price: 3

10,11,12 price: 3

13 price: 100

1,2,3,4,5,6,7,8,9,10,11,12,13 price: 110

The answer is obviously 110. (you only need to buy a last one, they dont have to be proper subsets)

Does anybody know the solution? Is something similar here on CF? Comments (4)
 » 10 months ago, # | ← Rev. 2 →   Maybe it's mincost max flow (mb there is easier solution, idk).I also don't know if this solution will pass the time limit.For example A is origin, B is sink, Si — subset no. i. Add edges like A->Si with capacity=inf, cost=Si_price Add edges Si->(items in Si) with capacity=1, cost=0 Add edges items->sink: capacity=1, cost=0 Max flow should be |items| if there is an answer, minimal cost will be the minimal price.
•  » » Why downvotes? It’s true solution.
 » This is a harder version of set cover problem and therefore is np hard. The easier version can be solved using bitmasks.
•  » » But how?? I cant find a place where the algorithm is explained.