Contest: HackerRank World Cup Semi-Finals

I’ve been overdue for reporting out on my performance in the HackerRank World Cup Semifinals. I’ve been on vacation for the past week, enjoying the beach at Bodega Bay with family. Therefore this blog is a bit late.

As expected, the contest problems were much harder this time around. And the time was reduced to 24 hours as well. I definitely felt the downside to the lack of team members this time around. I feel like I could have placed better with 1 or 2 other people to offload some problems onto. Anyway, I placed 228 out of 1411 *teams*, which, all said and done, wasn’t a terrible performance. In fact it was supposedly good enough to net me a HackerRank T-shirt (which I’m still waiting for), so “Yay!”

I will talk about one of the problems that I really liked in the contest. It was called “Delivery System” (Difficult level problem).

Problem Statement

Bill is the distributor for the “ByteLand Delivery System”. He has some orders to deliver. You have a map of ByteLand, and there are N cities and M directed ways. You also have a set of K different cities where Bill has to make a delivery. You have to find a good order of cities for Bill to visit. The order C is good if and only if, it’s possible to reach City number C[x+1] from City number C[x] for each acceptable x.

As you qualified to the semifinal, Bill thinks you are the one who can solve the problem he is facing!

If there are multiple solutions, print the lexicographically smallest.

Constraints

1≤K≤N≤10^5

1≤M≤2∗10^5

1≤T≤3

Input Format

First line contains one integer T, number of testcases.

For each test:

First line contains three integers N, M and K.

Second line contains K integers, cities Bill has to visit.

Next M line contains two integers X and Y,

denotes that there is a direct way from X to Y.

Output Format

For each test print a line with lexicographically smallest answer,but if there is no answer print -1.

Sample Input

1

4 5 3

4 3 2

3 4

3 1

1 4

2 1

3 2

Sample Output

3 2 4

Explanation

Start from city 3 and go to city 4 in passing by 2 is good and lexicographically smallest.

Solution

This is one of those problems where a solid knowledge of CS graph theory really helps. In fact, the problem is pretty much intractable unless we know two fundamental graph theoretic algorithms, which I will discuss below. This is a good reason why we should make sure we are improving our CS fundamentals constantly. Even if you are extremely smart, solving these problems is a nightmare without applying the appropriate CS algorithms. On the other hand, knowing the correct algorithms makes the problem pretty easy!

For the sake of argument, let’s consider a graph as shown below representing the various cities and the roads.

The problem mentions that we need a “lexicographically smallest” output. i.e. among many possible valid outputs, we need to present the one that is lexicographically smallest.

This suggests the following approach.

First, we find the strongly connected components of the directed graph.

A strongly connected component is a subgraph (with a subset of vertices and subset of edges) such that any vertex in that sub-graph can be reached from any other vertex in that sub-graph. Specifically, we can run Kosaraju’s SCC algorithm, which does 2 DFS traversals in a very specific order.

Why do we want to do this? Consider the example graph shown above. We have 4 SCCs in this graph, which are the four clusters shown in the boxed regions. Now we can figure out the various clusters that our candidate cities fall into. *Within* a single cluster, we know that all the candidate cities we are interested in that lie in that cluster can reach each other. Therefore, we can sort the candidate cities within each cluster. This will give us a lexicographically smallest *local* ordering.

However, just having these local orderings is obviously not enough. We need another fundamental graph algorithm.

Next, we perform a topological sort on the DAG induced by the SCCs.

A DAG is a directed acyclic graph. Once we find the SCCs in our directed graph, we can replace each SCC by a meta-node. This process induces a meta-graph on top of our original graph, which is acyclic by nature (if it were cyclic, it means we didn’t quite find the correct SCCs in the first place). In the example figure shown above, if we consider each *box* to be a meta-node, then the boxes (vertices) and the edges between boxes for a DAG.

DAGs have the property that we can perform topological sort on them. A topological sort is a *partial* ordering, such that each source node appears before *any* destination nodes that it points to. It is called a partial ordering, because (unlike for example sorting numbers) there are multiple correct orders possible.

We perform a topological sort, because we want to know that we are able to traverse the various clusters in order.

For example, let’s call our boxes (meta-nodes) as N, S, E, W (for the four directions), each corresponding to the respective box in the meta-graph. Now consider two cases.

Case 1: Our original list of candidate cities are contained within clusters W, N, and E. In this case, we can visit all the cities in the W cluster first (in lexicographic order), then all the cities in the N cluster (in lexicographic order), and finally all the cities in the E cluster (in lexicographic order again). This will give us an overall correct order, that is also lexicographically smallest. i.e. the problem has a solution in this scenario.

Case 2: Our original list of candidate cities are contained in clusters N, S, E, W. We can of course visit the W cluster first. But now, if we visit the N cluster, we can no longer visit the S cluster. On the other hand, if we visit the S cluster after the W cluster, we can no longer visit the N cluster. i.e. We find that the problem in this case has no solution.

My solution using Kosaraju’s SCC algorithm and topological sorting is on GitHub.

The algorithmic complexity for both algorithms is basically O(|V| + |E|) since we are simply performing multiple DFS traversals and hence very fast. Of course, we also do a vanilla sort *within* each SCC, which can be O(|V| log |V|). So the overall complexity is O(|E| + |V| log |V|)