Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Teads Sponsored Contest

Original Problem

The Goal

Here at Teads we know that to maximize the impact of an advertisement, the message needs to spread far and quickly. You are given data to calculate viral potential, represented by a network of people ready to relay a message to more people.
We can assume this network contains no cyclic relation.
For example, if person #1 has a relation with person #2 and if person #2 has a relation with person #3, then it is impossible for #3 to have a direct relation with #1. When an individual broadcasts a message, it is counted as a single step, meaning that the time it takes to broadcast the message is independant from the amount of people in direct relation with the individual. We will consider that this event will always take 1 hour. Here is an example with persons #1, #2, #3, #4, #5, #6, #7 and #8 linked like so:
Here, by choosing to start propagation of the message with person #1, 4 hours will be needed to share the message to the entire network:
1. #1 relays the message to #2
2. #2 then relays it to #3
3. #3 relays it to #4 and #7.
4. #4 relays it to #5 and #6, while #7 relays it to #8 If we decide now to start the propagation with person #3, then only 2 hours are needed:
1. #3 relays the message to #2, #4 and #7
2. #2 relays it to #1 ; #4 relays it to #5 and #6 ; #7 relays it to #8 In this exercice, your mission consists in finding the minimal amount of hours it would take for a message to propagate across the entire network given to you as input.

Game Input

Input

Line 1: N the number of adjacency relations.

N next lines: an adjancency relation between two people, expressed as X (space) Y, meaning that X is adjacent to Y.

Output
The minimal amount of steps required to completely propagate the advertisement.
Contraints
0 < N< 150000
0 ≤ X,Y < 200000

Solution

To solve this problem we need a way of identifying the most central element of the tree. Okay, in fact there is either one central vertex or two adjacent vertices, but this doesn't change much at the end.

The first idea was using a depth first search from a random vertex to find the most distant vertex. We now take the found vertex and search for the most distant vertex again. The traveled distance is the diameter of the tree and halving it results in the radius of the tree. The radius is exactly the value we're looking for in this problem. However, running two times a DFS on all nodes is computationally quite comprehensive.

The second idea is a bit different. We start by removing all leafs of the tree. We now remove all the leafs again and again, until only the center is remaining. Doing this is pretty efficient. However, removing elements from the adjacent list requires expensive array operations or even object re-creations. That's why I added a counter of adjacent vertices per node to reduce the amount of work to simple integer decrements. This allows to implement the algorithm like this:

var nodes = 0;
var depth = 0;
var counter = {};
var graph = {};

var n = +readline();
for (var i = 0; i < n; i++) {
  var [xi, yi] = readline().split(' ').map(Number);

  if (graph[xi] === undefined) graph[xi] = [], counter[xi] = 0, nodes++;
  if (graph[yi] === undefined) graph[yi] = [], counter[yi] = 0, nodes++;

  graph[xi].push(yi);
  graph[yi].push(xi);
  counter[xi]++;
  counter[yi]++;
}

while (nodes > 2) {
  // Create lists for delete elements
  var delA = [];
  var delB = [];
  
  // Loop over all remaining nodes
  for (var c in counter) {
    
    // Skip if it's not a leaf
    if (counter[c] !== 1)
      continue;
    
    // Scan over all neighbours of the leaf
    for (var n of graph[c]) {
      if (n in counter)
        delA.push(n); // Mark neighbour as deleted (needs to be postponed since we loop over counter)
    }
    // Mark leaf to be deleted. This brings a huge performance benefit since the JS engine must copy counter
    delB.push(c);
  }
  // Clean up marked vertices
  for (var la of delA)
    counter[la]--;
  for (var la of delB)
    delete counter[la], nodes--;
  
  // Increment depth
  depth++;
}

// If two nodes are remaining, we need one step more
if (nodes === 2)
  depth++;
print(depth);

Go to overview

All images are copyright to Codingame