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)