Cole, volunteers as a shelver at the school library, where the encyclopedias need to be re- organized. After re-organizing all the encyclopedias, Cole realizes that some of the encyclopedias are shelved in the wrong order. To fix the mistake, Cole decides to remove all the encyclopedias from the n by m shelf. While reshelving the encyclopedias, Cole realizes that the most efficient way to reshelve the encyclopedias is to select one encyclopedia, remove it, and remove all the other encyclopedias in the same row and column that the author wrote of the encyclopedia Cole chose. Cole wants to determine the minimum number of encyclopedias that need to be selected to remove all the encyclopedias from the shelf.
Note: The encyclopedias shelf section contains k authors. Each author is represented by an integer from 1 to k.
Example Let there be k = 3 authors. Let the following matrix represent the encyclopedias shelf:
221 111 233
Cole can choose the encyclopedia at position (2,3) in the first operation and remove it. Then, the matrix looks like this:
22X XXX 233
Cole can choose the encyclopedia at position (1,1) in the second operation and remove it. Then, the matrix looks like this:
XXX XXX x33
Cole can choose the encyclopedia at position (3,3) in the third operation and remove it. Then, the matrix looks like this:
XXX XXX XXX
So the answer for this sample is 3
1<=n,m<=1000, k<=50
Can anyone help me with its solution?
My approach: first make a bipartite graph for each author, and connect edges of a node with all other nodes, which are in the same column and same row with it, next look for the min vertex cover, such that those minimum vertex cover will cover all edges, and that will be my answer.
3 3 3 2 1 2 1 1 1 2 3 3
FOR THIS SAMPLE THE answer is like for the author 1
u can have bipartite graph like with undirected edges at vertices (0,0)-(1,1) (1,0)-(1,1) (1,0)-(1,2) (1,1)-(1,2)
here the min vertex cover is 1 that is (1,1)
similarly we can have graph at nodes
(0,0)-(0,2) (0,0)-(2,0) for author 2
and here also max matching or min vertex cover is 1
and for author 3
(2,2) — (2,3)
also its 1 and hence final anwer is 3
But I'm unable to code it. If anyone could help me, it would be much better....
"first make a bipartite graph for each author, and connect edges of a node with all other nodes, which are in the same column and same row with it"
This construction doesn't form a bi-partite graph always. For example take a single row matrix (1, 1, 1) for author 1 according to your construction it forms a 3 cycle.
Can you help me with the implementation for the problem?
A better construction would be to add edges from rows to columns as $$$row$$$ to $$$col$$$ if $$$matrix[row][col] = k$$$.
This is a bi-partite, now using find maximum matching using $$$Hopcroft-Karp$$$ Algorithm which would also be minimum Vertex Cover according to $$$Konig's$$$ $$$Theorem$$$.
But after that we will be left with a set of $$$row$$$ s, $$$col$$$ s from which we have to remove redundant elements $$$(row/col)$$$ if they have an edge optimally.