Death First Search - Episode 1 – CodinGame solution in Java
Each turn, run a breadth-first search from the Skynet agent to find the closest gateway, then cut the first link of that shortest path. If the agent is next to a gateway, this cuts exactly that link; otherwise it removes a link on the agent's best route. In Episode 1 each node touches at most one gateway, so this greedy rule never loses.
The problem
A network of N nodes is joined by L undirected links, and E of those nodes are gateways. A virus agent starts on one node and moves one link per turn towards a gateway. Before each of its moves you remove one link, and you win if the agent can never reach a gateway.
The first lines describe the graph and list the gateways; then every turn you receive the agent's current node and must print two node indexes whose link you sever. This puzzle was previously called Skynet: the Virus and then Skynet Revolution - Episode 1 on CodinGame.
Approach, step by step
- Build an adjacency listStore the neighbours of each node so a link can be removed from both endpoints when you cut it. Keep a set or flag for gateway nodes.
- Find the closest gateway with BFSStart a BFS at the agent's node and stop at the first gateway you dequeue: because BFS explores in distance order, that gateway is the nearest one. Remember each node's predecessor to rebuild the path.
- Cut the first link of the pathWalk back from the gateway to the agent and cut the link between the agent and the next node on that path. When the agent is adjacent to a gateway, this is the link that would otherwise lose the game immediately.
- Update the graph and repeatRemove the link from both adjacency lists, print it, and wait for the agent's new position. Recompute the BFS every turn, since the agent's route changes after each cut.
Complexity
O(E·(N + L)) per turnO(N + L)This code runs one BFS per gateway, each linear in the size of the graph. A single BFS from the agent that stops at the first gateway gives the same answer in O(N + L).
Solution code
Death First Search - Episode 1 – Java
A Path object is built by BFS from the agent to each gateway, and the shortest non-empty one is cut at its first link. Node keeps a linked list of neighbours so removing a link is a list removal on both ends.
import java.util.*;
/**
* <b> Node is the class representing a node of the network. </b> Each node as :
* <ul>
* <li> a unique id, constant
* <li> a list of neighbour nodes
* </ul>
*/
class Node {
private final int n;
private LinkedList<Node> neighb;
public Node(int n) {
this.n = n;
neighb = new LinkedList<Node>();
}
public void addNeighb(Node m) {
neighb.add(m);
}
public void removeNeighb(Node m) {
neighb.remove(m);
}
public Node[] neighb() {
return neighb.toArray(new Node[neighb.size()]);
}
public int n() {
return n;
}
}
/**
* <b> Path is the class representing a path in the network, by a list of nodes </b>
*/
class Path {
private LinkedList<Node> p;
public Node getNode(int i) {
return p.get(i);
}
public int length() {
return p.size();
}
public void addFirst(Node n) {
p.addFirst(n);
}
public Path() {
p = new LinkedList<Node>();
}
/** This constructor builds a shortest path in the network described by
* nodes, between begin and end
*/
public Path (Node begin, Node end, Node[] nodes) {
p = new LinkedList<Node>();
int N = nodes.length;
/* For each node is kept a boolean equal to true if it has been visited
and an int equal to the node it has been visited from (initially = -1) */
boolean[] explored = new boolean[N];
for (int i=0; i < N ;i++)
explored[i] = false;
explored[begin.n()] = true;
int[] prec = new int[N];
for (int i=0; i < N; i++)
prec[i] = -1;
/* A BFS is performed, starting from node begin
and until finding the node end.*/
LinkedList<Node> q = new LinkedList<Node>();
q.add(begin);
Node n = null;
while((q.size() != 0) && (n = q.remove()) != end) {
for (Node m : n.neighb()) {
if(!explored[m.n()]) {
explored[m.n()] = true;
prec[m.n()] = n.n();
q.add(m);
}
}
}
/* if the queue is empty before finding the node end then
there is no path, the new path stays empty.
Else, a shortest path is identified by backtracing.*/
if (n == end) {
while(n != begin) {
this.addFirst(n);
n = nodes[prec[n.n()]];
}
this.addFirst(n);
}
}
}
class Player {
public static void cut(Node n1, Node n2){
n1.removeNeighb(n2);
n2.removeNeighb(n1);
System.out.println(n1.n() + " " + n2.n());
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
// Scanning number of nodes, links, and exits
int N = in.nextInt();
int L = in.nextInt();
int E = in.nextInt();
// Initializing an array of non-linked nodes
Node[] nodes = new Node[N];
for (int i = 0 ; i < N ; i++)
nodes[i] = new Node(i);
// Linking nodes
for (int i = 0; i < L; i++) {
int N1 = in.nextInt();
int N2 = in.nextInt();
nodes[N1].addNeighb(nodes[N2]);
nodes[N2].addNeighb(nodes[N1]);
}
// Initializing an array of exit nodes
Node[] exits = new Node[E];
for (int i = 0; i < E; i++)
exits[i] = nodes[in.nextInt()];
while (true) {
// Skynet agent position
int SI = in.nextInt();
/* Simple strategy : identify one shortest paths from Skynet
agent to each exit node, thanks to a Breadth First Searches
Then cutting the shortest, as close as possible to Skynet agent */
Path[] shortestPaths = new Path[E];
int minLength = Integer.MAX_VALUE;
Path pathToCut = null;
for (int i = 0 ; i < E ; i++) {
shortestPaths[i] = new Path(nodes[SI], exits[i], nodes);
int length = shortestPaths[i].length();
if ((length != 0) && (length < minLength)) {
minLength = length;
pathToCut = shortestPaths[i];
}
}
cut(pathToCut.getNode(0), pathToCut.getNode(1));
}
}
}
Death First Search - Episode 1 – Python
Same algorithm as the Java version. The queue is a list where new nodes are inserted at the front and popped from the back, which is FIFO but costs O(n) per insertion; collections.deque would make it O(1).
import sys, math
class Node(object):
'''Class representing a node of the network, each node as :
a unique id, constant
a list of neighbour nodes'''
def __init__(self, n =0):
self.n = n
self.neighb = []
def addNeighb(self, m):
self.neighb.append(m)
def removeNeighb(self, m):
self.neighb.remove(m)
class Path(object):
'''class representing a path in the network, by a list of node'''
def __init__(self, begin, end, nodes):
'''This constructor builds a shortest path in the network described by
nodes, between begin and end'''
self.p = []
N = len(nodes)
# explored[i] is True <=> node i has been visited
# prec[i] = j <=> node i has been visited coming from node j
explored, prec = [], []
for i in range(N):
explored.append(False)
prec.append(-1)
explored[begin.n] = True
# A BFS is performed starting from node begin, until finding node end
q, n = [], None
q.append(begin)
while len(q) != 0:
n = q.pop()
if n == end:
break
else:
for m in n.neighb:
if not explored[m.n]:
explored[m.n] = True
prec[m.n] = n
q[0:0] = [m]
# if the queue is empty before finding end, there is no path
# else a shortest path is identified by backtracking
if n == end:
while n != begin:
self.p[0:0] = [n]
n = prec[n.n]
self.p[0:0] = [n]
def length(self):
return len(self.p)
def addFirst(self, n):
self.p[0:0] = [n]
def getNode(self, i):
return self.p[i]
def cut(n1, n2):
'''removes the edge between node n1 and n2'''
n1.removeNeighb(n2)
n2.removeNeighb(n1)
print("{} {}".format(n1.n, n2.n))
# number of nodes, links and exits
N, L, E = [int(i) for i in input().split()]
# initializing the array of nodes and linking them
nodes = []
for i in range(N):
nodes.append(Node(i))
for i in range(L):
N1, N2 = [int(j) for j in input().split()]
nodes[N1].addNeighb(nodes[N2])
nodes[N2].addNeighb(nodes[N1])
# initializing the array of exits
exits = []
for i in range(E):
exits.append(nodes[int(input())])
while 1:
# each turn, identifies one of the shortest paths from Skynet Agent
# to each exit node (by a Breadth First Search), then cuts the shortest
SI = int(input())
shortestPaths = []
minLength = 9999999
pathToCut = None
for i in range(E):
shortestPaths.append(Path(nodes[SI], exits[i], nodes))
length = shortestPaths[i].length()
if (length != 0) and (length < minLength):
minLength = length
pathToCut = shortestPaths[i]
cut(pathToCut.getNode(0), pathToCut.getNode(1))
Common mistakes
- Cutting a random gateway linkRemoving any link attached to a gateway works on tiny graphs but fails when the agent is about to step onto a different gateway. Always react to the agent's actual position.
- Printing a link that no longer existsIf you forget to remove a cut link from your graph, the next BFS can choose it again and you waste a turn printing an already-severed link.
- Removing the link from one side onlyLinks are undirected, so delete the neighbour in both directions. Otherwise BFS still walks through it from the other endpoint.
- Using DFS to find the pathA depth-first path to a gateway is not necessarily the shortest, so you may cut a link far away while the agent walks into a gateway next to it.
Going further
Why is the greedy rule safe in Episode 1? Because of a guarantee in the test design: no node is linked to two gateways. The only dangerous situation is the agent standing next to a gateway, and then there is exactly one dangerous link, which the BFS rule cuts. When the agent is not adjacent to any gateway, there is no immediate threat and any cut on its shortest route is fine. Episode 2 removes that guarantee: nodes can touch two gateways, and the agent can create a double threat you cannot answer in one cut. There you must cut, ahead of time, links of nodes connected to several gateways, prioritising those the agent can reach without passing through 'free' moves, which is why a pure shortest-path cut does not carry over.
FAQ
Do I need one BFS per gateway?
No. One BFS from the agent that stops at the first gateway reached finds the closest gateway directly and is E times cheaper.
Which order should I print the two nodes in?
Either order works: the link is undirected and the referee accepts 'a b' or 'b a'.
What is the difference with Episode 2?
In Episode 2 a node can be linked to two gateways, so you must anticipate double threats instead of only reacting to the nearest gateway.