Coding Solution

Death First Search - Episode 1 – solution CodinGame en Java

MoyenBFSgraphsshortest pathgreedyMis à jour le
Réponse courte

Chaque tour, on lance un parcours en largeur depuis l'agent Skynet pour trouver la passerelle la plus proche, puis on coupe le premier lien de ce plus court chemin. Si l'agent est voisin d'une passerelle, c'est exactement ce lien qu'on coupe ; sinon, on retire un lien sur sa meilleure route. Dans l'Episode 1, chaque nœud touche au plus une passerelle, donc cette règle gloutonne ne perd jamais.

L'énoncé

Un réseau de N nœuds est relié par L liens non orientés, et E de ces nœuds sont des passerelles. Un agent viral part d'un nœud et avance d'un lien par tour vers une passerelle. Avant chacun de ses déplacements, on supprime un lien, et on gagne si l'agent ne peut plus jamais atteindre une passerelle.

Les premières lignes décrivent le graphe et listent les passerelles ; puis chaque tour, on reçoit le nœud courant de l'agent et on affiche les deux indices de nœuds dont on coupe le lien. Ce puzzle s'appelait auparavant Skynet: the Virus, puis Skynet Revolution - Episode 1 sur CodinGame.

La démarche, étape par étape

  1. Construire une liste d'adjacenceOn stocke les voisins de chaque nœud pour pouvoir retirer un lien de ses deux extrémités quand on le coupe. On garde un ensemble ou un drapeau pour les nœuds passerelles.
  2. Trouver la passerelle la plus proche par BFSOn lance un BFS depuis le nœud de l'agent et on s'arrête à la première passerelle défilée : comme le BFS explore par distance croissante, c'est la plus proche. On mémorise le prédécesseur de chaque nœud pour reconstruire le chemin.
  3. Couper le premier lien du cheminOn remonte de la passerelle vers l'agent et on coupe le lien entre l'agent et le nœud suivant sur ce chemin. Quand l'agent est voisin d'une passerelle, c'est le lien qui ferait perdre la partie immédiatement.
  4. Mettre à jour le graphe et recommencerOn retire le lien des deux listes d'adjacence, on l'affiche et on attend la nouvelle position de l'agent. On recalcule le BFS à chaque tour, car la route de l'agent change après chaque coupe.

Complexité

TempsO(E·(N + L)) per turn
MémoireO(N + L)

Ce code lance un BFS par passerelle, chacun linéaire en la taille du graphe. Un seul BFS depuis l'agent qui s'arrête à la première passerelle donne la même réponse en O(N + L).

Code de la solution

Death First Search - Episode 1 – Java

Un objet Path est construit par BFS depuis l'agent vers chaque passerelle, et le plus court chemin non vide est coupé à son premier lien. Node conserve une liste chaînée de voisins, si bien que retirer un lien revient à une suppression dans la liste à chaque extrémité.

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)); 
        }
    }
}
            

Erreurs fréquentes

Pour aller plus loin

Pourquoi la règle gloutonne est-elle sûre dans l'Episode 1 ? Grâce à une garantie dans la conception des tests : aucun nœud n'est relié à deux passerelles. La seule situation dangereuse est un agent voisin d'une passerelle, et il y a alors exactement un lien dangereux, celui que la règle du BFS coupe. Quand l'agent n'est voisin d'aucune passerelle, il n'y a pas de menace immédiate et n'importe quelle coupe sur son plus court chemin convient. L'Episode 2 supprime cette garantie : des nœuds peuvent toucher deux passerelles, et l'agent peut créer une double menace impossible à parer en une seule coupe. Il faut alors couper à l'avance les liens des nœuds reliés à plusieurs passerelles, en priorisant ceux que l'agent peut atteindre sans passer par des déplacements « gratuits », ce qui explique qu'une simple coupe sur le plus court chemin ne se transpose pas.

Questions fréquentes

Faut-il un BFS par passerelle ?

Non. Un seul BFS depuis l'agent, arrêté à la première passerelle atteinte, trouve directement la plus proche et coûte E fois moins.

Dans quel ordre afficher les deux nœuds ?

Peu importe : le lien est non orienté et l'arbitre accepte « a b » comme « b a ».

Quelle différence avec l'Episode 2 ?

Dans l'Episode 2, un nœud peut être relié à deux passerelles : il faut anticiper les doubles menaces au lieu de réagir seulement à la passerelle la plus proche.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome