WEED - Editorial


Summer of innovation


Blow weed everyday


Brute Force Search, Hashing


Snoop and Dogg are two very lazy brothers. To teach them a lesson of responsibility, their mother has asked them to remove weed from their garden. Assume that the garden is a grid of MxN dimensions. The garden has weed grown in K of these grid cells. Because, the brothers are so lazy, Snoop will only clear one row of garden whereas Dogg will only clear one column of the garden. What is the maximum number of weed that they can remove from the garden.


Whenever Snoop Dogg tries to clear weeds, he clears a complete row and a column. So the maximum cells with weed that he can remove is Maximum(row) + Maximum(column). So, they should start from (MAXr, MAXc). But will this be the solution always?
When cell (MAXr, MAXc) has a weed in it, they are essentially only removing Maximum(row) + Maximum(col) -1 weeds in total. So, we need to perform a brute force search over all K cells to see if any of them have weed in it or not. This can be done fairly easily as K is not that large. The max of row and column can also be calculated at runtime using dictionaries (hashmaps).

Setter’s Solution