Minimize the number of Dogs!

Revision en3, by pks18, 2020-08-05 14:30:33

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!

Tags #dfs and similar, #graph theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English pks18 2020-08-05 14:30:33 4 Tiny change: 'ty spots. But if we ' -> 'ty spots. \n\nBut if we '
en2 English pks18 2020-08-05 06:40:56 0 (published)
en1 English pks18 2020-08-05 06:39:36 442 Initial revision (saved to drafts)