I was solving the problem set of Code forces when I stumbled upon this question Protect Sheep. The question was pretty simple if we simply place dogs on all the empty spots.

But if we were supposed to minimize the number of the dogs used to protect the sheep. How do we solve it then? There seems to be many cases to handle. Any kind of help would be appreciated!