Coding Solution

Teads Sponsored Contest – solution CodinGame en Java

MoyentreesBFSgraph diametergraph radiusMis à jour le
Réponse courte

Le réseau de Teads est un arbre, et le nombre minimal d'étapes pour atteindre tout le monde depuis la meilleure personne de départ est le rayon de l'arbre. Dans un arbre, le rayon vaut ceil(diamètre / 2), et le diamètre s'obtient en deux parcours : depuis un nœud quelconque, on trouve le nœud le plus éloigné u ; depuis u, la plus grande distance est le diamètre D. On affiche (D + 1) / 2, le tout en O(n).

L'énoncé

On reçoit les liens d'amitié d'un groupe de personnes sous forme de n arêtes non orientées entre identifiants. Un message se propage d'une personne à tous ses amis directs en une étape, puis aux amis des amis, et ainsi de suite. Il faut trouver le plus petit nombre d'étapes nécessaire pour toucher tout le monde en choisissant la personne de départ de façon optimale.

Les relations forment un arbre : connexe, sans cycle, n arêtes pour n+1 personnes, avec jusqu'à environ 150 000 relations. Lancer un BFS depuis chaque personne est quadratique et dépasse le temps sur les plus gros tests.

La démarche, étape par étape

  1. Construire une liste d'adjacenceOn lit les arêtes et on stocke, pour chaque identifiant, la liste de ses voisins dans les deux sens. On dimensionne la structure selon le plus grand identifiant rencontré, car rien n'impose que les identifiants soient denses.
  2. Premier parcours depuis un nœud quelconqueOn part de n'importe quelle personne présente dans une arête et on calcule les distances vers toutes les autres. Le nœud le plus éloigné u est garanti être une extrémité d'un plus long chemin de l'arbre.
  3. Second parcours depuis uOn calcule les distances depuis u. La plus grande distance trouvée est le diamètre D, le nombre d'arêtes du plus long chemin de l'arbre.
  4. Passer du diamètre au rayonLa meilleure personne de départ se trouve au milieu de ce plus long chemin. Depuis là, la personne la plus éloignée est à ceil(D / 2) étapes, soit (D + 1) / 2 en arithmétique entière.

Complexité

TempsO(n)
MémoireO(n)

Deux parcours linéaires d'un arbre à n+1 nœuds et n arêtes, plus les listes d'adjacence elles-mêmes.

Code de la solution

Teads Sponsored Contest – Java

Bien que la méthode s'appelle BFS, elle utilise une Stack : c'est donc un parcours en profondeur itératif. Cela reste correct ici car, dans un arbre, l'unique chemin entre deux nœuds est aussi le plus court, donc la profondeur égale la distance. La pile explicite évite aussi les problèmes de profondeur de récursion sur les longues chaînes.

import java.util.*;
import java.math.*;

/**
 * This class is used to return both the last vertex encoutered, 
 * and the excentricity of the starting vertex after a BFS
 */
class Result { 
    public int length; 
    public Node last; 
}

/**
 * This class is representing a node of the graph.
 * neighbs is a list of the node neighbours
 * n is a unique constant id
 */
class Node {
    private ArrayList<Node> neighbs;
    private int n;
    
    public Node(int n){
        this.n = n;
        neighbs = new ArrayList<Node>();
    }
    
    public void add(Node n){
        neighbs.add(n);
    }

    public ArrayList<Node> neighbs(){
        return neighbs;
    }
    
    public int n(){
        return n;
    }
}

class Solution {
    /**
     * Reads the standard input and constructs the graph to study
     * @return ArrayList of the vertices of the graph
     */
    public static ArrayList<Node> readInfos()
    {
        Scanner in = new Scanner(System.in);
        ArrayList<Node> graph = new ArrayList<Node>();
        int N, x, y;
        
        N = in.nextInt();
        for (int i = 0; i < N; i++) {
            x = in.nextInt();
            y = in.nextInt();
            /*As node ids are consecutive and start from 0, when discovering a
             new node i, adds nodes to the graph until there are i+1 nodes */
            while(graph.size() <= Math.max(x,y))
                graph.add(new Node(graph.size()));
            graph.get(x).add(graph.get(y));
            graph.get(y).add(graph.get(x));
        }
        
        return graph;
    }
    
    /**
     * Runs a Breadth First Search and returns the last node encountered, 
     * and the starting node excentricity
     * Complexity : O(|V|)
     * @param start starting vertex
     * @param graph graph to search
     * @return Result containing one of the most distant nodes from 'start', 
     * and the distance between them*/
    public static Result BFS (Node start, ArrayList<Node> graph)
    {
        Result res = new Result();
        
        int[] depth = new int[graph.size()];
        for (int i = 0 ; i < graph.size() ; i++)
            depth[i]=-1;
        depth[start.n()] = 0;
        
        Stack<Node> stack = new Stack<Node>();
        stack.push(start);
        
        Node father, son;
        while (!stack.empty()) {
            father = stack.pop();
            Iterator<Node> sons = father.neighbs().iterator();
            while (sons.hasNext()) {
                son = sons.next();
                if (depth[son.n()] == -1) {
                    depth[son.n()] = depth[father.n()]+1;
                    if (depth[son.n()] > res.length) {
                        res.length = depth[son.n()];
                        res.last = son;
                    }
                    stack.push(son);
                }
            }
        }
        return res;       
    }

    public static void main(String args[]) 
    {
        ArrayList<Node> graph = readInfos();
        Result r = BFS(graph.get(0), graph);
        r = BFS(r.last, graph);
        System.out.println((r.length+1)/2);
    }
}
            

Erreurs fréquentes

Pour aller plus loin

Pourquoi le double parcours trouve-t-il le diamètre ? Soit a–b un plus long chemin et s le départ. Prenons u, le nœud le plus éloigné de s ; si u n'était l'extrémité d'aucun plus long chemin, on pourrait rerouter : le chemin de u passant par le point où le chemin de s rejoint a–b, puis vers le plus éloigné de a ou b, serait plus long que a–b, contradiction. Une autre approche, tout aussi linéaire et que certains trouvent plus intuitive, est l'épluchage des feuilles : on retire à répétition toutes les feuilles courantes (nœuds de degré 1) par couches, comme on pèle un oignon. Le nombre de couches retirées avant qu'il ne reste un ou deux nœuds est la réponse, et les nœuds survivants sont exactement le centre de l'arbre, c'est-à-dire les personnes idéales pour lancer le message.

Questions fréquentes

Pourquoi Teads passe par le diamètre plutôt que directement par le rayon ?

Parce que dans un arbre ils sont liés : rayon = ceil(diamètre / 2). Le diamètre se calcule facilement en deux parcours, alors que le rayon directement exigerait l'excentricité de chaque nœud.

Est-ce important d'utiliser un BFS ou un DFS ?

Pas dans un arbre. Il n'y a qu'un chemin entre deux personnes, donc tout parcours complet qui note la profondeur donne la vraie distance. Sur un graphe général, il faudrait un BFS.

Quelle est la réponse pour une seule relation ?

Deux personnes reliées par une arête ont un diamètre de 1, donc la réponse est (1 + 1) / 2 = 1 étape.

Puzzles similaires

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