Contest: HackerRank Women’s Cup

This weekend I competed in the HackerRank Women’s Cup contest. And yes… I checked with HackerRank to make sure that I was *eligible* to compete even though I’m not a woman. 🙂 There was a catch however. Though I could compete, I was *not eligible* to win any prizes. Those were reserved only for women.

Anyway, I placed 45 out of 1137 participants, which was a pretty good placement. I scored full points on the first 6 problems, but only partial points on the last one (since 15/33 tests passed on that one, but the rest timed out). I tried many different things to speed up the last problem (e.g. using interval trees), but the optimal solution involved using segment trees again.

Here is a summary of the problems, and my solutions:

#	Problem	My Solution	Algorithmic Technique	Time Complexity	Space Complexity	Level
1	Possible Maximum	GitHub	Basics	O(n^2)	O(1)	Easy
2	Project Earth	GitHub	Math, AdHoc	O(1)	O(1)	Easy
3	Magical Pearls	GitHub	Heaps	O(n log n)	O(n)	Moderate
4	Cabalistic Hills	GitHub	Eulerian Cycle, Graphs	O(|E| + |V|)	O(|E| + |V|)	Moderate
5	Magical String	GitHub	Pre-compute AdHoc	O(n) precomp O(1) query	O(n)	Moderate
6	Coding Camp	GitHub	Sorting, AdHoc	O(m^2 log m)	O(m+n)	Difficult
7	Counting Pairs	GitHub	Brute Force	Query 1 O(1) Query 3 O(1) Query 2 O(min(n, (s2-s1)))	O(n)	Difficult

Here’s a fun problem from the contest:

Problem: Cabalistic Hills

Problem Statement

Antony and Cleopatra are true soul mates and, like true soul mates, they fight. Instead of giving her an elixir like last time, Antony wants to bestow her with the magical lamp available at the Cabalistic Hills.

The Cabalistic Hills were created by Lucifer millions of years ago. They have N hills numbered 1 to N. The magical lamp is situated at the peak of hill N. Some of these hills are connected by one way rope bridges(directed), and these rope bridges are the only way to reach hill N and return back to hill 1. Each rope bridge disappears after being used once.

Lucifer has created traps for the climbers. Some rope bridges do not lead to hill N, and some lead to hill N but without a way to return back to hill 1. Antony MUST use all the rope bridges in his journey from hill 1 to N and back to 1 or he is imprisoned by Lucifer.If multiple ropes are connecting two hills then it should be counted multiple times and all of the ropes must be used once. You must advise Antony whether the hills are safe to climb or they are devious trap! Given N hills and M pairs of connected hills, determine whether it’s a trap.

Input Format

The first line contains T: the number of test cases. Each test case contains N and M separated by space. Next M lines contains v1, v2 separated by a space where v1 and v2 represent the hills connected by a rope bridge.

Constraints

1≤T≤15

1≤N≤10^5

0≤M≤2×10^5

Output Format

Output T lines. For each test case, either print “Go on get the Magical Lamp” or, if it’s a trap, “Danger!! Lucifer will trap you” without quotes.

Sample Input

2

4 4

1 2

2 3

3 4

4 1

4 3

1 2

2 3

3 1

Sample Output

Go on get the Magical Lamp

Danger!! Lucifer will trap you

Solution

As kids, we have all at some point been posed the Boyd Puzzle. The riddle asks us to draw a certain figure, starting from one point, and ending at the same point with these rules:

• You cannot lift your pencil off the paper.
• You cannot cover the same line twice.
• You must draw all the lines in the figure.

This is an unsolvable riddle, for the particular figure posed, and there is actually a mathematical theorem that proves the same. In fact the famous mathematician Euler proved it rigorously with his famous problem “Seven Bridges of Konigsberg”. This was a major historical development, and laid the foundations of graph theory, which is so ubiquitous in computer science!

So what does this have to do with our current problem? Our problem is a generalized version of this Boyd’s Puzzle, where we need to give a yes/no answer to “Is it possible to construct a Eulerian cycle for the provided input?”

i.e. Let’s construct a graph with the input. Now if you read the problem statement carefully you will notice the following.

• We must start at 1, visit N, and come back to 1 (i.e. trace a cycle).
• We must also visit *every edge*, only in the direction stated.
• We can visit every edge exactly once (the bridges disappear after travel).
• We *must* use all bridges.

We see that this problem is a sneaky way of asking us to detect a Eulerian Cycle in the graph! Once you realize this, the problem becomes extremely simple. Indeed, there exists a polynomial time algorithm to do this. The algorithm is as follows.

A directed graph has a Eulerian Cycle if and only if:

1. All vertices with in/out edges belong to the same single strongly connected component.
2. For each vertex in-degree(v) == out-degree(v)

We can do #1 above by running Kosaraju’s SCC algorithm like one of our previous contests. We can keep some bookkeeping information along the way to figure out #2 quite easily as well.

Note: The diagram below is credited to mathworld since I was too lazy to draw my own.

It is interesting that detecting/constructing a Eulerian Cycle (using all edges exactly once) is a polynomial time algorithm, but constructing a Hamiltonian Cycle (using all vertices exactly once) is an NP-Complete problem!

 

 

 

 

 

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