I would place this problem in a class of maximum bipartite matching with additional constraints problems. It's likely impossible to give "the fastest way to construct a valid solution" without knowing limits on set sizes, blocking set amount, number of distinct elements and their multiplicity. But I'll give an efficient polynomial-time solution: reduction to the maximum flow problem, similar to other problems in that class. This should allow solving your problem even for total size of multisets on the order of 100'000.
Definitions
Let's define a graph describing our problem.
The picking multiset will be represented by one vertex, a_i, per each distinct element v_i having a multiplicity pickcnt_i. The j-th blocked multiset will be represented by one vertex, b_jk, per each distinct element u_jk having a multiplicity of blockcnt_jk, and an auxiliary "bottleneck" vertex c_j. price_j will designate the necessary amount of elements to unblock the j-th blocked multiset. Additionally vertices S, source, and T, sink, are defined.
v_i is usable pickcnt_i times, so S is connected to a_i by an edge with capacity pickcnt_i. Similarly b_jk is connected to c_j with capacity blockcnt_jk. c_j is connected to T with capacity price_j to limit the progress of "partial unblocking". a_i and b_jk are connected by an edge iff v_jv_i == u_jk, with unlimited capacity.
Interpreting a flow
This graph represents a flow network. Let's look at an arbitrary feasible flow. Each unit of flow consumes: a unit capacity on S->a_i, modeling removal of a single v_i from the picking multiset; a unit capacity on b_jk->c_j, modeling removal of a single u_jk from the j-th blocked multiset; a unit capacity on c_j->T, modeling a single partial unblocking. Hence it is trivial to convert between a feasible flow and a matching of picking and blocking sets elements.
Let's look at a maximum flow. It doesn't violate any constraints from our original problem, and its value corresponds to the number of matched elements. So its value can't be higher than Σprice_j, can reach Σprice_j only by unblocking all sets, and must reach it if all sets can be unblocked. Therefore maximum flow gives a solution to the original problem if it satiates all c_j->T, and otherwise there is no solution.
Complexity
There are many algorithms for finding a maximum flow with complexities favoring dense or sparse graphs with small or unlimited capacities. Many perform in practice better than their complexity would suggest, particularly on special graphs like those produced by a bipartite matching problem. For some such graphs there are additional theorems proving a better complexity. Not knowing the limits I can't suggest a specific algorithm, only describe the size of the reduced problem.
The number of vertices is dominated by the sum of unique element counts for each set. The number of edges — by the number of valid "initial moves": what element can be used to partially unblock what multiset. The maximum flow is the maximum number of "moves" than can be performed.
To give an example of prewritten, ready to be used maxflow implementations, you can take a look at Dinic and PushRelabel here.
I would place this problem in a class of maximum bipartite matching with additional constraints problems. It's likely impossible to give "the fastest way to construct a valid solution" without knowing limits on set sizes, blocking set amount, number of distinct elements and their multiplicity. But I'll give an efficient polynomial-time solution: reduction to the maximum flow problem, similar to other problems in that class. This should allow solving your problem even for total size of multisets on the order of 100'000.
Definitions
Let's define a graph describing our problem.
The picking multiset will be represented by one vertex, a_i, per each distinct element v_i having a multiplicity pickcnt_i. The j-th blocked multiset will be represented by one vertex, b_jk, per each distinct element u_jk having a multiplicity of blockcnt_jk, and an auxiliary "bottleneck" vertex c_j. price_j will designate the necessary amount of elements to unblock the j-th blocked multiset. Additionally vertices S, source, and T, sink, are defined.
v_i is usable pickcnt_i times, so S is connected to a_i by an edge with capacity pickcnt_i. Similarly b_jk is connected to c_j with capacity blockcnt_jk. c_j is connected to T with capacity price_j to limit the progress of "partial unblocking". a_i and b_jk are connected by an edge iff v_j == u_jk, with unlimited capacity.
Interpreting a flow
This graph represents a flow network. Let's look at an arbitrary feasible flow. Each unit of flow consumes: a unit capacity on S->a_i, modeling removal of a single v_i from the picking multiset; a unit capacity on b_jk->c_j, modeling removal of a single u_jk from the j-th blocked multiset; a unit capacity on c_j->T, modeling a single partial unblocking. Hence it is trivial to convert between a feasible flow and a matching of picking and blocking sets elements.
Let's look at a maximum flow. It doesn't violate any constraints from our original problem, and its value corresponds to the number of matched elements. So its value can't be higher than Σprice_j, can reach Σprice_j only by unblocking all sets, and must reach it if all sets can be unblocked. Therefore maximum flow gives a solution to the original problem if it satiates all c_j->T, and otherwise there is no solution.
Complexity
There are many algorithms for finding a maximum flow with complexities favoring dense or sparse graphs with small or unlimited capacities. Many perform in practice better than their complexity would suggest, particularly on special graphs like those produced by a bipartite matching problem. For some such graphs there are additional theorems proving a better complexity. Not knowing the limits I can't suggest a specific algorithm, only describe the size of the reduced problem.
The number of vertices is dominated by the sum of unique element counts for each set. The number of edges — by the number of valid "initial moves": what element can be used to partially unblock what multiset. The maximum flow is the maximum number of "moves" than can be performed.
To give an example of prewritten, ready to be used maxflow implementations, you can take a look at Dinic and PushRelabel here.
I would place this problem in a class of maximum bipartite matching with additional constraints problems. It's likely impossible to give "the fastest way to construct a valid solution" without knowing limits on set sizes, blocking set amount, number of distinct elements and their multiplicity. But I'll give an efficient polynomial-time solution: reduction to the maximum flow problem, similar to other problems in that class. This should allow solving your problem even for total size of multisets on the order of 100'000.
Definitions
Let's define a graph describing our problem.
The picking multiset will be represented by one vertex, a_i, per each distinct element v_i having a multiplicity pickcnt_i. The j-th blocked multiset will be represented by one vertex, b_jk, per each distinct element u_jk having a multiplicity of blockcnt_jk, and an auxiliary "bottleneck" vertex c_j. price_j will designate the necessary amount of elements to unblock the j-th blocked multiset. Additionally vertices S, source, and T, sink, are defined.
v_i is usable pickcnt_i times, so S is connected to a_i by an edge with capacity pickcnt_i. Similarly b_jk is connected to c_j with capacity blockcnt_jk. c_j is connected to T with capacity price_j to limit the progress of "partial unblocking". a_i and b_jk are connected by an edge iff v_i == u_jk, with unlimited capacity.
Interpreting a flow
This graph represents a flow network. Let's look at an arbitrary feasible flow. Each unit of flow consumes: a unit capacity on S->a_i, modeling removal of a single v_i from the picking multiset; a unit capacity on b_jk->c_j, modeling removal of a single u_jk from the j-th blocked multiset; a unit capacity on c_j->T, modeling a single partial unblocking. Hence it is trivial to convert between a feasible flow and a matching of picking and blocking sets elements.
Let's look at a maximum flow. It doesn't violate any constraints from our original problem, and its value corresponds to the number of matched elements. So its value can't be higher than Σprice_j, can reach Σprice_j only by unblocking all sets, and must reach it if all sets can be unblocked. Therefore maximum flow gives a solution to the original problem if it satiates all c_j->T, and otherwise there is no solution.
Complexity
There are many algorithms for finding a maximum flow with complexities favoring dense or sparse graphs with small or unlimited capacities. Many perform in practice better than their complexity would suggest, particularly on special graphs like those produced by a bipartite matching problem. For some such graphs there are additional theorems proving a better complexity. Not knowing the limits I can't suggest a specific algorithm, only describe the size of the reduced problem.
The number of vertices is dominated by the sum of unique element counts for each set. The number of edges — by the number of valid "initial moves": what element can be used to partially unblock what multiset. The maximum flow is the maximum number of "moves" than can be performed.
To give an example of prewritten, ready to be used maxflow implementations, you can take a look at Dinic and PushRelabel here.
I would place this problem in a class of maximum bipartite matching with additional constraints problems. It's likely impossible to give "the fastest way to construct a valid solution" without knowing limits on set sizes, blocking set amount, number of distinct elements and their multiplicity. But I'll give an efficient polynomial-time solution: reduction to the maximum flow problem, similar to other problems in that class. This should allow solving your problem even for total size of multisets on the order of 100'000.
Definitions
Let's define a graph describing our problem.
The picking multiset will be represented by one vertex, a_i, per each distinct element v_i having a multiplicity pickcnt_i. The j-th blocked multiset will be represented by one vertex, b_jk, per each distinct element u_jk having a multiplicity of blockcnt_jk, and an auxiliary "bottleneck" vertex c_j. price_j will designate the necessary amount of elements to unblock the j-th blocked multiset. Additionally vertices S, source, and T, sink, are defined.
v_i is usable pickcnt_i times, so S is connected to a_i by an edge with capacity pickcnt_i. Similarly b_jk is connected to c_j with capacity blockcnt_jk. c_j is connected to T with capacity price_j to limit the progress of "partial unblocking". a_i and b_jk are connected by an edge iff v_j == u_jk, with unlimited capacity.
Interpreting a flow
This graph represents a flow network. Let's look at an arbitrary feasible flow. Each unit of flow consumes: a unit capacity on S->a_i, modeling removal of a single v_i from the picking multiset; a unit capacity on b_jk->c_j, modeling removal of a single u_jk from the j-th blocked multiset; a unit capacity on c_j->T, modeling a single partial unblocking. Hence it is trivial to convert between a feasible flow and a matching of picking and blocking sets elements.
Let's look at a maximum flow. It doesn't violate any constraints from our original problem, and its value corresponds to the number of matched elements. So its value can't be higher than Σprice_j, can reach Σprice_j only by unblocking all sets, and must reach it if all sets can be unblocked. Therefore maximum flow gives a solution to the original problem if it satiates all c_j->T, and otherwise there is no solution.
Complexity
There are many algorithms for finding a maximum flow with complexities favoring dense or sparse graphs with small or unlimited capacities. Many perform in practice better than their complexity would suggest, especiallyparticularly on special graphs havinglike those produced by a rigid structure, forbipartite matching problem. For some such graphs there are additional theorems proving a better complexity. Not knowing the limits I can't suggest a specific algorithm, only describe the size of the reduced problem.
The number of vertices is dominated by the sum of unique element counts for each set. The number of edges — by the number of valid "initial moves": what element can be used to partially unblock what multiset. The maximum flow is the maximum number of "moves" than can be performed.
To give an example of prewritten, ready to be used maxflow implementations, you can take a look at Dinic and PushRelabel here.
I would place this problem in a class of maximum bipartite matching with additional constraints problems. It's likely impossible to give "the fastest way to construct a valid solution" without knowing limits on set sizes, blocking set amount, number of distinct elements and their multiplicity. But I'll give an efficient polynomial-time solution: reduction to the maximum flow problem, similar to other problems in that class. This should allow solving your problem even for total size of multisets on the order of 100'000.
Definitions
Let's define a graph describing our problem.
The picking multiset will be represented by one vertex, a_i, per each distinct element v_i having a multiplicity pickcnt_i. The j-th blocked multiset will be represented by one vertex, b_jk, per each distinct element u_jk having a multiplicity of blockcnt_jk, and an auxiliary "bottleneck" vertex c_j. price_j will designate the necessary amount of elements to unblock the j-th blocked multiset. Additionally vertices S, source, and T, sink, are defined.
v_i is usable pickcnt_i times, so S is connected to a_i by an edge with capacity pickcnt_i. Similarly b_jk is connected to c_j with capacity blockcnt_jk. c_j is connected to T with capacity price_j to limit the progress of "partial unblocking". a_i and b_jk are connected by an edge iff v_j == u_jk, with unlimited capacity.
Interpreting a flow
This graph represents a flow network. Let's look at an arbitrary feasible flow. Each unit of flow consumes: a unit capacity on S->a_i, modeling removal of a single v_i from the picking multiset; a unit capacity on b_jk->c_j, modeling removal of a single u_jk from the j-th blocked multiset; a unit capacity on c_j->T, modeling a single partial unblocking. Hence it is trivial to convert between a feasible flow and a matching of picking and blocking sets elements.
Let's look at a maximum flow. It doesn't violate any constraints from our original problem, and its value corresponds to the number of matched elements. So its value can't be higher than Σprice_j, can reach Σprice_j only by unblocking all sets, and must reach it if all sets can be unblocked. Therefore maximum flow gives a solution to the original problem if it satiates all c_j->T, and otherwise there is no solution.
Complexity
There are many algorithms for finding a maximum flow with complexities favoring dense or sparse graphs with small or unlimited capacities. Many perform in practice better than their complexity would suggest, especially on graphs having a rigid structure, for some such graphs there are additional theorems proving a better complexity. Not knowing the limits I can't suggest a specific algorithm, only describe the size of the reduced problem.
The number of vertices is dominated by the sum of unique element counts for each set. The number of edges — by the number of valid "initial moves": what element can be used to partially unblock what multiset. The maximum flow is the maximum number of "moves" than can be performed.
To give an example of prewritten, ready to be used maxflow implementations, you can take a look at Dinic and PushRelabel here.
I would place this problem in a class of maximum bipartite matching with additional constraints problems. It's likely impossible to give "the fastest way to construct a valid solution" without knowing limits on set sizes, blocking set amount, number of distinct elements and their multiplicity. But I'll give an efficient polynomial-time solution: reduction to the maximum flow problem, similar to other problems in that class. This should allow solving your problem even for total size of multisets on the order of 100'000.
Definitions
Let's define a graph describing our problem.
The picking multiset will be represented by one vertex, a_i, per each distinct element v_i having a multiplicity pickcnt_i. The j-th blocked multiset will be represented by one vertex, b_jk, per each distinct element u_jk having a multiplicity of blockcnt_jk, and an auxiliary "bottleneck" vertex c_j. price_j will designate the necessary amount of elements to unblock the j-th blocked multiset. Additionally vertices S, source, and T, sink, are defined.
v_i is usable pickcnt_i times, so S is connected to a_i by an edge with capacity pickcnt_i. Similarly b_jk is connected to c_j with capacity blockcnt_jk. c_j is connected to T with capacity price_j to limit the progress of "partial unblocking". a_i and b_jk are connected by an edge iff v_j == u_jk, with unlimited capacity.
Interpreting a flow
This graph represents a flow network. Let's look at an arbitrary feasible flow. Each unit of flow consumes: a unit capacity on S->a_i, modeling removal of a single v_i from the picking multiset; a unit capacity on b_jk->c_j, modeling removal of a single u_jk from the j-th blocked multiset; a unit capacity on c_j->T, modeling a single partial unblocking. Hence it is trivial to convert between a feasible flow and a matching of picking and blocking sets elements.
Let's look at a maximum flow. It doesn't violate any constraints from our original problem, and its value corresponds to the number of matched elements. So its value can't be higher than Σprice_j, can reach Σprice_j only by unblocking all sets, and must reach it if all sets can be unblocked. Therefore maximum flow gives a solution to the original problem if it satiates all c_j->T, and otherwise there is no solution.
Complexity
There are many algorithms for finding a maximum flow with complexities favoring dense or sparse graphs with small or unlimited capacities. Many perform in practice better than their complexity would suggest, particularly on special graphs like those produced by a bipartite matching problem. For some such graphs there are additional theorems proving a better complexity. Not knowing the limits I can't suggest a specific algorithm, only describe the size of the reduced problem.
The number of vertices is dominated by the sum of unique element counts for each set. The number of edges — by the number of valid "initial moves": what element can be used to partially unblock what multiset. The maximum flow is the maximum number of "moves" than can be performed.
To give an example of prewritten, ready to be used maxflow implementations, you can take a look at Dinic and PushRelabel here.
I would place this problem in a class of maximum bipartite matching with additional constraints problems. It's likely impossible to give "the fastest way to construct a valid solution" without constraintsknowing limits on set sizes, butblocking set amount, number of distinct elements and their multiplicity. But I'll give anan efficientpolynomial-time solution that is not bruteforce: reduction to a maximum flow problemthe maximum flow problem, similar to other problems fromin that class. This should allow solving your problem even for total size of multisets on the order of 100'000.
Definitions
Let's define a graph describing our problem.
The picking multiset will be represented by one vertex, a_i, per each distinct element v_i having a multiplicity pickcnt_i. The j-th blocked multiset will be represented by one vertex, b_jk, per each distinct element u_jk having a multiplicity of blockcnt_jk, and an auxiliary "bottleneck" vertex c_j. price_j will designate the necessary amount of elements to unblock the j-th blocked multiset. Additionally vertices S, source, and T, sink, are defined.
v_i is usable pickcnt_i times, so S is connected to a_i by an edge with capacity pickcnt_i. Similarly b_jk is connected to c_j with capacity blockcnt_jk. c_j is connected to T with capacity price_j to limit the progress of "partial unblocking". a_i and b_jk are connected by an edge iff v_j == u_jk, with unlimited capacity.
Interpreting a flow
This graph represents a flow network. Let's look at an arbitrary feasible flow. Each unit of flow consumes: a unit capacity on S->a_i, modeling removal of a single v_i from the picking multiset; a unit capacity on b_jk->c_j, modeling removal of a single u_jk from the j-th blocked multiset; a unit capacity on c_j->T, modeling a single partial unblocking. Hence it is trivial to convert between a feasible flow and a matching of picking and blocking sets elements.
Let's look at a maximum flow. It doesn't violate any constraints from our original problem, and its value corresponds to the number of matched elements. So its value can't be higher than Σprice_j, can reach Σprice_j only by unblocking all sets, and must reach it if all sets can be unblocked. Therefore maximum flow gives a solution to the original problem if it satiates all c_j->T, and otherwise there is no solution.
Complexity
There are many algorithms for finding a maximum flow with complexities favoring dense or sparse graphs with small or unlimited capacities. Many perform in practice better than their complexity would suggest, especially on graphs having a rigid structure, for some such graphs there are additional theorems proving a better complexity. Not knowing the constraintslimits I can't suggest a specific algorithm, only describe the size of the reduced problem.
The number of vertices is dominated by the sum of unique element counts for each set. The number of edges — by the number of valid "initial moves": what element can be used to partially unblock what multiset. The maximum flow is the maximum number of "moves" than can be performed.
To give an example of prewritten, ready to be used maxflow implementations, you can take a look at Dinic and PushRelabel here.
I would place this problem in a class of maximum bipartite matching with additional constraints problems. It's likely impossible to give "the fastest way to construct a valid solution" without constraints, but I'll give an efficient solution that is not bruteforce: reduction to a maximum flow problem, similar to other problems from that class.
Definitions
Let's define a graph describing our problem.
The picking multiset will be represented by one vertex, a_i, per each distinct element v_i having a multiplicity pickcnt_i. The j-th blocked multiset will be represented by one vertex, b_jk, per each distinct element u_jk having a multiplicity of blockcnt_jk, and an auxiliary "bottleneck" vertex c_j. price_j will designate the necessary amount of elements to unblock the j-th blocked multiset. Additionally vertices S, source, and T, sink, are defined.
v_i is usable pickcnt_i times, so S is connected to a_i by an edge with capacity pickcnt_i. Similarly b_jk is connected to c_j with capacity blockcnt_jk. c_j is connected to T with capacity price_j to limit the progress of "partial unblocking". a_i and b_jk are connected by an edge iff v_j == u_jk, with unlimited capacity.
Interpreting a flow
This graph represents a flow network. Let's look at an arbitrary feasible flow. Each unit of flow consumes: a unit capacity on S->a_i, modeling removal of a single v_i from the picking multiset; a unit capacity on b_jk->c_j, modeling removal of a single u_jk from the j-th blocked multiset; a unit capacity on c_j->T, modeling a single partial unblocking. Hence it is trivial to convert between a feasible flow and a matching of picking and blocking sets elements.
Let's look at a maximum flow. It doesn't violate any constraints from our original problem, and its value corresponds to the number of matched elements. So its value can't be higher than Σprice_j, can reach Σprice_j only by unblocking all sets, and must reach it if all sets can be unblocked. Therefore maximum flow gives a solution to the original problem if it satiates all c_j->T, and otherwise there is no solution.
Complexity
There are many algorithms for finding a maximum flow with complexities favoring dense or sparse graphs with small or unlimited capacities. Many perform in practice better than their complexity would suggest, especially on graphs having a rigid structure, for some such graphs there are additional theorems proving a better complexity. Not knowing the constraints I can't suggest a specific algorithm, only describe the size of the reduced problem.
The number of vertices is dominated by the sum of unique element counts for each set. The number of edges — by the number of valid "initial moves": what element can be used to partially unblock what multiset. The maximum flow is the maximum number of "moves" than can be performed.
I would place this problem in a class of maximum bipartite matching with additional constraints problems. It's likely impossible to give "the fastest way to construct a valid solution" without knowing limits on set sizes, blocking set amount, number of distinct elements and their multiplicity. But I'll give an efficientpolynomial-time solution: reduction to the maximum flow problem, similar to other problems in that class. This should allow solving your problem even for total size of multisets on the order of 100'000.
Definitions
Let's define a graph describing our problem.
The picking multiset will be represented by one vertex, a_i, per each distinct element v_i having a multiplicity pickcnt_i. The j-th blocked multiset will be represented by one vertex, b_jk, per each distinct element u_jk having a multiplicity of blockcnt_jk, and an auxiliary "bottleneck" vertex c_j. price_j will designate the necessary amount of elements to unblock the j-th blocked multiset. Additionally vertices S, source, and T, sink, are defined.
v_i is usable pickcnt_i times, so S is connected to a_i by an edge with capacity pickcnt_i. Similarly b_jk is connected to c_j with capacity blockcnt_jk. c_j is connected to T with capacity price_j to limit the progress of "partial unblocking". a_i and b_jk are connected by an edge iff v_j == u_jk, with unlimited capacity.
Interpreting a flow
This graph represents a flow network. Let's look at an arbitrary feasible flow. Each unit of flow consumes: a unit capacity on S->a_i, modeling removal of a single v_i from the picking multiset; a unit capacity on b_jk->c_j, modeling removal of a single u_jk from the j-th blocked multiset; a unit capacity on c_j->T, modeling a single partial unblocking. Hence it is trivial to convert between a feasible flow and a matching of picking and blocking sets elements.
Let's look at a maximum flow. It doesn't violate any constraints from our original problem, and its value corresponds to the number of matched elements. So its value can't be higher than Σprice_j, can reach Σprice_j only by unblocking all sets, and must reach it if all sets can be unblocked. Therefore maximum flow gives a solution to the original problem if it satiates all c_j->T, and otherwise there is no solution.
Complexity
There are many algorithms for finding a maximum flow with complexities favoring dense or sparse graphs with small or unlimited capacities. Many perform in practice better than their complexity would suggest, especially on graphs having a rigid structure, for some such graphs there are additional theorems proving a better complexity. Not knowing the limits I can't suggest a specific algorithm, only describe the size of the reduced problem.
The number of vertices is dominated by the sum of unique element counts for each set. The number of edges — by the number of valid "initial moves": what element can be used to partially unblock what multiset. The maximum flow is the maximum number of "moves" than can be performed.
To give an example of prewritten, ready to be used maxflow implementations, you can take a look at Dinic and PushRelabel here.