### pks18's blog

By pks18, history, 7 weeks ago,

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!

• +2

 » 7 weeks ago, # | ← Rev. 2 →   0 Maybe I have an idea,don't know this would work or not.....if not please tell me what is wrong here.....first i would place dogs around all sheeps and count them =count_1....(so that all sheeps are safe) then again i traverse the whole grid and place dogs around all wolves =count_2.....(so thar wolfes can't go anywhere).... answer would be the min(count_1,count_2)...........
•  » » 7 weeks ago, # ^ |   0 Suppose all sheep are on one side and all wolves on the other side, we can put dogs in the between them. That can have less number of dogs in many cases of r and c. I think you get the idea.
•  » » » 7 weeks ago, # ^ |   0 yes i got it
 » 7 weeks ago, # |   +18 max flow, min cut
•  » » 7 weeks ago, # ^ |   -28 Thats a 900 rated problem -_-
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +26 Yeah and OP asked for a different version of it.
•  » » 7 weeks ago, # ^ |   0 I think I didn't understand how to use max flow-min cut to solve the optimization problem. Could you elaborate it more?
•  » » 6 weeks ago, # ^ |   0 Are you suggesting to connect all the sheep with all the wolves with an edge capacity of one and then find the Min-Cut. If yes, how would you model the case where you four sheep are placed at the corners of the field and yo have sheep at the center?