dpasztor's blog

Buying subsets
By dpasztor, history, 5 years ago, In English

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?

  • Vote: I like it
  • -9
  • Vote: I do not like it

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

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.

→ Reply
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

This is a harder version of set cover problem and therefore is np hard. The easier version can be solved using bitmasks.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    But how?? I cant find a place where the algorithm is explained.

    → Reply