Coding Solution

Death First Search - Episode 1 – CodinGame solution in Java

MediumBFSgraphsshortest pathgreedyUpdated
Short answer

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

  1. 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.
  2. 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.
  3. 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.
  4. 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

TimeO(E·(N + L)) per turn
SpaceO(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)); 
        }
    }
}
            

Common mistakes

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.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome