← All solutions

This problem has a very distinct max flow smell, and indeed, flows are involved in the solution. First, suppose we think of the solution board as the adjacency matrix of a directed graph, with a component in row i column j being a unit of flow from i to j. Then, the constraint that there are equally many components in row i and column i just corresponds to each vertex having the same in-flow as out-flow. In other words, the solution is a circulation in a flow graph. To be specific, this flow graph is the graph on N vertices where there is capacity 1 from i to j if row i column j of the input board is not blocked. Furthermore, if we put cost 1 on those capacity 1 edges, the cost of the circulation precisely corresponds to the number of widgets used, so it seems hopeful that maximum cost circulations (which are perhaps less known than their cousins the min cost max flows, but can also be found efficiently) should be involved in the solution somehow.

However, there are two obstacles. First, there are some widgets that need to be used in the solution. This can be handled by either applying a lower bound on the flow of the corresponding edges (which makes finding an initial feasible solution a bit more complicated), or, more simply, by putting a large negative cost on these edges, heavily penalizing any solution that does not use them.

Second, there is the requirement that no row or column can contain more than an A/B fraction of all widgets. If this constraint was an absolute constraint, saying that at most m widgets can be placed on any row or column, it could easily be handled by introducing vertex capacities m in the graph (using the standard trick of splitting each vertex into an invertex and an out-vertex). Now, to handle the relative constraint, we can guess the value of m, solve the problem with that absolute bound, and check that the total number of widgets becomes at least m · B/A. There are at most N + 1 possible values of m so this only incurs an extra factor N in the running time (which in fact can be avoided by reusing the result for m − 1 when computing the maximum number of widgets for vertex capacities m).