PROBLEM LINK:
Author: Parth Mittal
Tester: Anmol Singh
Editorialist: Rounaq Jhunjhunu Wala
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Graphs, Breadth-first search, Bitmask
PROBLEM:
Given a undirected unweighted graph with N nodes and M edges, P nodes having gangsters on them such that they kill anybody on a node having a distance K from the gangster node, we need to find a safe path from node s to node t. In case we come in range of any gangster, we can either pay him C_i money units (i is the ID of the gangster), or die. We want a minimum cost safe path from s to t.
QUICK EXPLANATION:
Since P is quite small, we can try to consider paying all subsets of the gangsters.
Now, when we pay a mask m of gangsters, we take its compliment to get the gangsters who will try to kill us.
Then we mark off all nodes within distance k of these gangsters as unavailable, and determine if s and t are still connected in this scenario.
Finally, compute the minimum cost over all the masks which do not disconnect s and t.
Runtime: O(2 ^ P \times (N + M)) (BFS for each mask)
EXPLANATION:
We need to find a path from s to t. We can do that via a breadth-first search. Now, we need to assess that this path is indeed safe, that is , we are not being killed by any gangster on any node in the path. If we keep the range of each gangster (Nodes within distance k of the gangster node) in lists, then we would need to check each node n in the path for not belonging in a list of any of the active gangsters (active means the gangsters whose we have not paid the bribe, and thus they will still kill us).
So, we may end up searching |P|*|V| lists. Which is not good.
Notice that the size of the set P is small, so, we can actually choose an arbitrary subset of gangsters whom we will pay the bribe. Now, for each of the gangsters not in the chosen subset, we mark the nodes in range of those gangsters as inaccessible. We would then again do a BFS on the graph with source s, this time not taking the inaccessible nodes into consideration. If s and t are stil conneced, then, the chosen subset is a feasible solution.
Now, we do the above for all subsets of P, and find the minimum cost solution from the feasible ones.