Teads Sponsored Contest – CodinGame solution in Java
The network in Teads is a tree, and the minimum number of steps to reach everyone from the best starting person is the tree's radius. For a tree, the radius equals ceil(diameter / 2), and the diameter is found with two traversals: from any node, find the farthest node u; from u, the farthest distance is the diameter D. Print (D + 1) / 2.
The problem
You receive the friendship links of a group of people as n undirected edges between person ids. A message spreads from one person to all their direct friends in one step, then to friends of friends, and so on. Find the smallest number of steps needed to reach everybody if you get to pick the starting person optimally.
The relations form a tree: connected, no cycles, n edges for n+1 people, with up to around 150,000 relations. Running a BFS from every person is quadratic and times out on the largest tests.
Approach, step by step
- Build an adjacency listRead the edges and store, for every id, the list of its neighbours in both directions. Size the structure by the largest id you see, since ids are not required to be dense.
- First traversal from any nodeStart from any person who appears in an edge and compute distances to all others. The farthest node u is guaranteed to be one end of a longest path of the tree.
- Second traversal from uCompute distances from u. The largest distance found is the diameter D, the number of edges on the longest path in the tree.
- Convert diameter to radiusThe best starting person sits in the middle of that longest path. From there, the farthest person is ceil(D / 2) steps away, which in integer arithmetic is (D + 1) / 2.
Complexity
O(n)O(n)Two linear traversals of a tree with n+1 nodes and n edges, plus the adjacency lists themselves.
Solution code
Teads Sponsored Contest – Java
Although the method is named BFS, it uses a Stack, so it is an iterative depth-first traversal. That is still correct here because in a tree the only path between two nodes is the shortest one, so depth equals distance. The explicit stack also avoids recursion depth problems on long chains.
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);
}
}
Common mistakes
- BFS from every nodeComputing every node's eccentricity is O(n²) and fails on the largest tests. Two traversals are enough for a tree.
- Recursive DFS on a long chainA test shaped like a line of 100,000+ people overflows the call stack in Java or Python with a recursive DFS. Use an explicit stack or queue.
- Printing D / 2 instead of (D + 1) / 2For an odd diameter, for example 3, the middle falls on an edge, and the best you can do is 2 steps. Plain integer division gives 1 and fails.
- Starting from an id that is not in the graphIf you allocate nodes up to the maximum id and start from node 0 without checking, an unused id leaves the traversal empty. Start from the first endpoint read from the input.
Going further
Why does the double traversal find the diameter? Let a–b be a longest path and s the start. Take the farthest node u from s; if u were not an endpoint of some longest path, you could reroute: the path from u through the point where s's path meets a–b, then to the farther of a or b, would be longer than a–b, a contradiction. A different, equally linear approach that some find more intuitive is leaf peeling: repeatedly remove all current leaves (nodes of degree 1) in layers, like peeling an onion. The number of layers removed until one or two nodes remain is the answer, and the surviving nodes are exactly the centre of the tree, i.e. the ideal people to start the message.
FAQ
Why does Teads use the diameter instead of the radius directly?
Because on trees they are linked: radius = ceil(diameter / 2). The diameter is easy to compute with two traversals, while the radius directly would require the eccentricity of every node.
Does it matter whether I use BFS or DFS?
Not on a tree. There is only one path between any two people, so any full traversal that records depth gives the true distance. On general graphs you would need BFS.
What is the answer for a single relation?
Two people connected by one edge have diameter 1, so the answer is (1 + 1) / 2 = 1 step.