WEED - Editorial

Contest

Summer of innovation

Problem

Blow weed everyday

Prerequisite

Brute Force Search, Hashing

Statement

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.

Explanation

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?
No.
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

Link