pks18's blog

By pks18, history, 7 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +18 Vote: I do not like it

max flow, min cut

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    Thats a 900 rated problem -_-

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +26 Vote: I do not like it

      Yeah and OP asked for a different version of it.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think I didn't understand how to use max flow-min cut to solve the optimization problem. Could you elaborate it more?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?