Interesting problem: Finding minimum number of lasers to cover certain cells in a matrix

Revision en1, by wrick, 2016-06-07 20:15:23

Reposted from here:

I was asked this in an interview. I am modifying the question a bit to preserve it from being explicitly Googleable but the gist is:

You are given an N x M grid. Some cells in the grid are "evil" (denoted by number 1) and rest are "good" (denoted by 0). You have lasers positioned across each N rows and across each M columns which when turned on kills all cells in their respective row or column e.g. if you have:

LL L1 L2 L3 L4
L5  0  1  0  0
L6  0  1  0  1
L7  0  1  1  0
L8  0  0  0  0

You can turn on either (L2, L3, L4):

LL L1 L2 L3 L4
L5  0  x  x  x
L6  0  x  x  x
L7  0  x  x  x
L8  0  x  x  x

Or you can turn on (L2, L6, L7):

L1 L2 L3 L4
L5  0  x  0  0
L6  x  x  x  x
L7  x  x  x  x
L8  0  x  0  0

A set of lasers turned-on is called "GoodConfig" iff it kills all evil cells. Note you can always turn on all lasers along a row or column and kill everything and it would be "GoodConfig" but turning on lasers is expensive and killing good cells is bad.

  1. What is the smallest size of "GoodConfig" i.e. least number of lasers we can turn on till kill all evil cells?

  2. What is a "GoodConfig" that minimizes the number of good cells killed?

I realized that part 1 is similar to a step in the Hungarian algorithm but I don't have a good intuition or implementation of it. Part 2 — I have no idea.

Tags algorithm, puzzles, hungarian algorithm

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English wrick 2016-07-07 16:25:34 0 (published)
en2 English wrick 2016-06-07 20:15:49 4 Tiny change: '):\n\n L1 L2 L3 ' -> '):\n\n LL L1 L2 L3 ' (saved to drafts)
en1 English wrick 2016-06-07 20:15:23 1750 Initial revision (published)