backo's blog

An interesting problem
By backo, history, 9 years ago, In English

Hello everyone!

I've recently come across a problem and I can't seem to find an efficient solution. I didn't know what to title this post because I don't know which group of problems does it belong to (dp,greedy,...). The problem is as follows:

You're given a set of distinct values {a1,a2,a3,...,ak} (1<=k<=3*10^5). Lets denote this A.

Also, you're given an array of "slots" of size 10^5. For each slot, you're given a subset of A.

You have to place a value from set A in each of the slots such that value in each slot has to be from its subset. (The subset is a constraint on which elements can go inside). Different slots can have same values stored in them (and it is encouraged to do so)

Now you have to fill all slots BUT minimizing the ammount of distinct values from A used.

I don't know if I've been clear on this, so let's consider this simple example:

A = { 1,2,3 }

constraints (3 slots): (1,2) (1,3) (1,2)

Answer: You're going to fill the slots (1,1,1), thus using minimum number of distinct values from A (only 1). An alternate solution could be (1,3,2) but this uses 3 elements from A and thus it is not optimal. Filling (3,3,2) is not a valid solution because 3 cannot go into the first slot (because of the constraint).

This is actually a subproblem of a larger problem I've been trying to solve, and it might mean I have to take a different approach to solving the original problem in order to avoid solving this one. However, I think this is an interesting problem as is so I think it will be useful for many of you on this site if a solution is given.

Thanks in advance!

Backo.

p.s. If you want, I can post a link to the original problem (it's graph-related)

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the set-cover problem: https://en.wikipedia.org/wiki/Set_cover_problem and is NP-Hard in general. It may be the case that in this problem there are some specific properties of the input that makes it solvable, but they're probably easier to notice in the original statement, so feel free to share it.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I see. Didn't hear of that problem before. Then it was probably a wrong approach. The problem I've been solving is: 449B - Jzzhu and Cities

    I've been going about it by finding single-source shortest paths from capital to each of the city. Also, I saved for each vertex V which trainroutes does the shortest path to V goes through. Obviously, it seemed that each shortest path would go through exactly 1 trainroute, but I think that there can be several shortest paths for V that go through different trainroutes and I have to choose which to take and which to reject

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

      As you said, each shortest path has at most one trainroute. So first build the graph with just the edges and trainroutes that are part of some shortest path from the capital. So imagine you are analizing a vertex V wich has a trainroute that ends in it and there isnt other trainroute that forms part of a shortest path to V . If there is at least one shortest path that doesnt use a trainroute you can erase all the trainroutes that end in V (if there are more that one) and notice that for an other vertex wich its shortest path pass trought V, lets calle it W, you alredy have a path that doesnt has a trainroute or is one but just because is strictly necessary to use it. So you just have to analize the trainroutes that end in W using the same idea as we did with V

      Hope you understand my explanation, sorry for my bad english

      → Reply