Please someone solve this, most probably it can be solved by Disjoint Set Union, I tried but can't think of some clear way.
I even posted this on Leetcode(because it is for posting this type of things) but no one solved yet
Problem Statement:
You are given a 2D vector bookshelf, where each element represents a book type numbered from 1 to k. The task is to empty the bookshelf by selecting a book and removing all books of the same type that lie in the same row or column as the selected book. The goal is to determine the minimum number of turns needed to completely clear the bookshelf.
For instance, if you select a book of type 2 located at row 0 and column 3, you would remove all books of type 2 present in row 0 and column 3, including the selected book.
Function Signature:
int emptyshelf(vector<vector<int>>& bookshelf, int k) {
// Your implementation here
}
Constraints:
- 1 <= bookshelf.size() <= 100
- 1 <= bookshelf[0].size() <= 100
- 1 <= k <= 100
Example 1:
Input:
1 1 1
1 2 2
1 2 1
Output:
3 turns
Example 2:
Input:
1 2 2
1 2 2
2 1 2
Output:
4 turns
Explanation:
For each turn, you select a book and remove all books of the same type either in the same row or column. The objective is to minimize the number of turns it takes to completely empty the bookshelf.
nvm my bad, I could only come up with a k*n^6 DP which I can prove. There maybe some greedy technique as well
It would be nice if you will explain this.
We solve for each k separately, since they are independent. Then notice that once a cell is picked, we should never pick another cell which shares a row or a column with the previously picked cell. So let dp[p][q][r][s] mean the minimum operations required to remove books in the sub grid with top corner p, q and bottom corner r, s. Then inside this sub grid we can iterate overall all the cells and if we remove pick it, then our sub grid will be in general broken into 4 parts, our dp transition will be 1 + the sum of the dp of the four sub grids, minimised over all such cells we pick inside our sub grid.
state require n^4 and transitions are n^2, and we do this for k different colours thus kn^6.
However I suspect we can do a greedy by removing a cell which removes the most coloured cells, then removing all those coloured cells, and iterate till no coloured cells remain, for each colour.
But this maybe wrong due to it being awfully similar to the "set cover" problem, which is NP hard.
First of all it is easy to see that different book types are independent, so we will solve for them separately.
Let the dimensions of the grid be $$$n$$$ and $$$m$$$, and the current book type be $$$x$$$. Construct a bipartite graph with $$$n + m$$$ vertices, where there is an edge between $$$i$$$ and $$$j$$$ iff there is a book of type $$$x$$$ in the cell $$$(i, j)$$$. Note that an operation on a cell corresponds to deleting an edge and all adjacent edges. Let's remove all isolated vertices. We can see that the subset of edges on which we perform operations will be adjacent to all the remaining vertices. This condition is also a sufficient. Thus, we need to find a minimum edge cover of the vertices, which can be done with bipartite matching.
This leads to a complexity of $$$\mathcal{O}(nm \sqrt{n + m})$$$ if we use a $$$\mathcal{O}(E \sqrt{V})$$$ matching algorithm.
I thought the same, but it's wrong as far as I understand. Consider a 3x3 grid and 1-based cells (1, 1) (2, 2) and (2, 1) are black. minimum edge cover gives an answer of two, while we could obviously pick cell (2, 1) which would cover all the three black cells at once.
Notice that different book types are independent, so we can solve for each book type separately. Build a graph where the nodes are rows and columns, and each book of that type is an edge between its row and its column. This is a bipartite graph, and in addition, every bipartite graph corresponds to a book configuration.
When removing a book, you also remove all the books in the same row and in the same column, which correspond its adjacent edges in the graph. Therefore, solving this problem solves the minimum edge dominating set on bipartite graphs, which is NP-complete.
In conclusion, either this problem requires some state-of-the-art randomized/approximation algorithm, or the author made a wrong problem (very likely).