PROBLEM LINK:
Author: Snigdha Chandan
Tester: Sergey Kulik
Editorialist: Xellos
DIFFICULTY:
CHALLENGE
PREREQUISITES:
researching
PROBLEM:
There’s a graph and an infection spreading from a given vertex; in each step, the vertices adjacent to an infected vertex become infected and an infected vertex remains infected. Before each step, you may vaccinate one uninfected vertex, which will never become infected afterwards.
EXPLANATION:
[based on problemsetter’s notes]
The problem is known as Firefighter Problem. It’s very hard, but also well studied; there are a lot of resources to read up on (including the special cases among the tests: bipartite and 4-regular graph).
Typically, we could try some kind of greedy approach; the bounds allow us to spend O(M+N) time on each of the K decisions. The most basic greedy would look just at neighbours of infected nodes, a more advanced greedy would consider also their neighbours etc.; it’s somewhat better to block articulations or prefer vertices whose blocking makes subgraphs with a large sum of weights safe from infection.
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.