You are given a 40x40 grid. Each point of the grid is either 0 or 1. You are also given an infinite amount of 1x40 rectangular slabs.

How to find out the minimum number of slabs required to cover all the points which have a value 1?

NOTE: The 1x40 slabs can overlap with each other.

  • 3
    $\begingroup$ Since I can't possibly need more than 40 slabs, the person responsible for buying infinitely many of them should be fired. :-) $\endgroup$ – David Richerby May 11 '14 at 17:23
  • 2
    $\begingroup$ What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – FrankW May 11 '14 at 18:33

I'm assuming you're only allowed to use the 1x40 slabs horizontally or vertically. They thus cover entire rows or columns. We can rephrase your problem as minimum vertex cover in a bipartite graph. The bipartite graph consists of 40 row vertices and 40 column vertices. Connect two vertices if the corresponding point in the grid is 1. The minimum number of slabs needed to cover all 1s is exactly the minimum vertex cover in this bipartite graph. In bipartite graphs, minimum vertex cover equals maximum matching, so the problem is algorithmically feasible. In order to find a concrete algorithm, just look for algorithms for solving minimum vertex cover on bipartite graphs.

  • $\begingroup$ Apparently not. But I don't believe I answered the question as stated. Anyone following my hint might end up actually learning something, which is the point of solving exercises in the first place. $\endgroup$ – Yuval Filmus May 12 '14 at 16:28
  • $\begingroup$ Got it. Thank you for the explanation. $\endgroup$ – D.W. May 12 '14 at 16:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.