Contest: HackerRank World Cup Qualifiers

I’ve been sick with a cold for the past couple of days, so this is probably going to be a shorter blog. But I thought it would be fun to write about my latest HackerRank contest – the World Cup Qualifiers. It took place last weekend. At first I was a bit apprehensive, because the contest allowed teams of up to 3 people to participate. I was worried that the problems might take too long for one person to solve, but I took a leap of faith and participated anyway (as a solo team). I’m glad I did, because it was actually a really cool contest! I placed 151 out of 4408 *teams*, so overall not too bad at all.  Unfortunately this was an unrated contest, so no medals were handed out. I also had to create a new handle for my lone wolf team, which I called golambda, so the contest rankings show up on this handle instead of my usual cbrghostrider.

The top 50% of the teams qualified for the *semi-finals*, which are going to be this weekend. Unlike the qualifiers, the semi-finals are going to be extremely brutal, because only 50 teams will make it to the finals. There are definitely more than 50 competitive programming pros that are much much better at this than I am, so I fear it is an automatic knockout for me. But I’m still going to compete, because it is a ton of fun! 🙂

The qualifiers had 6 problems of varying difficulty levels. Here’s a quick summary of the contest.

#	Problem	My Solution	Algorithmic Technique	Time Complexity per test	Level
1	WC Team Formation	GitHub	Basics	O(1)	Easy
2	Swapping Bridges	GitHub	Union-Find, Basics	O(n log n)	Moderate
3	World Cup Game	GitHub	Tree Minimax, Memoization	O(n)	Moderate
4	Bishop War	GitHub	Backtracking w/ pruning	O(2^(mn))	Difficult
5	Alien Age	GitHub	Dynamic Programming, Greedy	O(m*n*(log m + log n))	Advanced
6	Ikbals Arrays	N/A	Segment Trees	N/A	Advanced

 

Here are some notes on the problems:

Swapping Bridges:

Initially this problem sounds fairly complicated. But when you read it closely, you realize that the constraints on the problem limit the amount of complexity drastically. Specifically each city has *exactly* one incoming and outgoing edge. Given the other constraints, the only topologies possible are circular lists. i.e. the entire graph is a disjoint collection of circular lists. Furthermore, every time we perform the permitted operation of bridge-swap, we merge two such circles. The problem can be solved in O(n), but why bother when I already have a Union-Find implementation ready? So I saved some (implementation) time and solved it in O(n log n) using Union-Find.

World Cup Game:

This was actually a really cool and elegant game theory problem, and had me stumped for a while. I finally solved it, and loved it so much I immediately decided to blog about it. I won’t say much about it here, because I have an entire section underneath the talks about it.

Bishop War:

This is a variation on the N-Queens problem, with Bishops instead of Queens. Some random obstacles are also added to the chess board. I had a functional version ready quick, but struggled a bit to get it running within the time limits. I experimented with various pruning strategies to solve this problem. Initially I only had a few submissions passing, but I gradually improved the pruning until I could get 40/41 tests passing within 2 seconds. Interestingly, the editorial has a better algorithm, with a O(m*n*2^(2m)) complexity. My O(2^(n*m)) is definitely much worse in theory, but in practice all that pruning I did reduces the search space drastically.

Alien Age:

This was another cool problem, and involved dynamic programming, which I love so much. After solving the first portion using DP, we need another algorithmic technique to finally solve the problem. I had thought of the same approach as the editorial (binary search after DP), but ended up going with another approach (greedy choice after DP). Both results are functionally correct, though mine is just a tad less efficient O(n*m*(log n + log m)) instead of the editorials O(n*m*(log min(m, n))).

Ikbals Arrays:

I did not actually attempt this problem during the contest. I’ve seen this type of problem before, and know that it involves using a segment tree. The issue however is that I don’t have a ready segment tree implementation in my personal library yet. Also I was completely thrown off by the constraints of the problem (the array size could be up to 10^9, which is insane!). I (wrongly) concluded that even if I wrote a segment tree implementation, the tree itself would be too freaking huge, and would result in Memory-Limit-Exceeded (HackerRank only allows 640MB memory during the contest). I figured there was some other technique that needed to be used. Apparently I concluded wrong, and the problem is solvable using segment trees (though I’m still stumped by how to avoid the MLE issue).

World Cup Game

Ok, so now for my favorite problem. This problem was a game theory-ish problem, and very elegant. It definitely had an “aha-moment” to it, and really made me smile when I figured it out. I have the problem statement, constraints, and an example below:

Problem Statement

Bob invented a game on a tree for the Hackerrank World Cup! The game is played by two players. Players will take turns and in each move they will choose a node, but they have to follow some rules:

Rule 1: A player can’t choose a node which is already chosen by himself or by his opponent in previous rounds.

Rule 2: If the player is making his first move, he can choose any node as long as he doesn’t violate the first rule.

Rule 3: If it is not the first move of the player, he has to choose a node which is adjacent to one of the nodes he already selected in previous moves.

If a player is not able to make a move, he misses that turn and the game continues. The game ends when neither player can make a move.

In each node there are some tokens. The score of a player is the sum of numbers of tokens in the nodes he has chosen. Each player will try to maximize his own score.

For a given tree, calculate the maximum score that can be obtained by the first player. Assume that both players are playing optimally (none of them will make any mistakes).

Input Format

First line contains N, number of nodes in a tree. The nodes are numbered from 1 to N.

Second line contains N numbers, ith number denotes number of tokens in node i.

Each of the next N−1 line contains two integers U and V which indicates there is an edge in the tree between node U and nod e V.

Constraints

1≤N≤500000

1≤A[i]≤10^9

Output Format

Print maximum score of first player, if both players play optimally.

Sample Input

3

4 2 4

1 2

2 3

Sample Output

6

Explanation

One scenario is, First player chooses node 2 and then the second player will choose node 1 or node 3 and then first one will choose the last node. In both scenarios, the first player will have 6 points.

Solution

I usually give a pretty detailed solution for my favorite problems, including efficiency and correctness claims. However, rarely do we just *solve* the problem when we first see it. Often, it involves quite a bit of struggle, with false starts and walks down dead ends and into pitfalls.

For this problem, I think I am going to first describe my initial *incorrect thought process*, and how overwhelming it can get. I think it is interesting to look back and reflect on how the solution unfolded. It is also enlightening to look back on the exact moment that we get the “aha” in problems that have this “aha-moment”. Following this, I will describe the *correct thought process*, followed by notes on the correctness and efficiency of the algorithm.

Incorrect Thought Process

When we first read the problem, the situation seems bleak. How do we even begin to solve this?

Consider the very first step. The first player can choose absolutely any node to begin with. Therefore whatever strategy we choose, we need to iterate through all the nodes at least on the first choice. The first node for the second player is an almost similar problem.

Ok, let’s forget about the first node for the moment. Let’s say the game is in progress, and player 1 has to make the choice of the next node. Do we at least have a simpler problem here? Very quickly our thoughts can pull us in multiple directions. Here are some ad-hoc things I considered:

• If a node has score more than the sum of all scores of all other remaining nodes, I want to choose it. This is a pseudo-greedy criteria.
• I obviously want to try and choose a node with many points, to maximize my final score.
• I want to choose a node with as many neighbors as possible. This will open up many options for me in the future (considering rule 3).
• I also want to choose nodes that have neighbors with high points. This is so that I can try to claim those neighbors in the future.
• [Already the overall situation is starting to look chaotic and bleak by this point… Notice that I really have no idea what kind of algorithm I’m trying to get. I’m just brainstorming at this point, and it isn’t going very well.]
• Ok, how about we try to choose nodes that will limit the choices we present to our opponent. Maybe we should choose nodes that will block off our opponent. [How do I do this?]

I could go on and on. But the above bullets summarize the primary problem. All I have so far are random and chaotic thoughts, and really no algorithm. I was tempted to just *code some ad-hoc algorithm* based on the above criteria, to at least get some partial credit. This is a *horrible* thought, and I am so glad I did not pursue it. The bottom line is that you want to solve the problem on paper first, and convince yourself that your approach is rock solid. Only then should you start typing any code. Otherwise you will spend a lot of time painfully debugging and hacking away at a piss-poor “algorithm”.

Another thing to notice is the constraint on the input. The tree can have as many as half a million nodes. This rules out algorithmically intense algorithms, because the algorithm essentially has to run in linear time to process such a huge amount of data.

The situation looks bleak.

Correct thought process

Before I go ahead, lets clarify one thing. Although the problem says “tree”, what we really have (given the input sample) is an “un-rooted” tree. i.e. a tree with no specific node marked as a root. Essentially, we have a spanning tree in an undirected graph. i.e. The tree in this problem is really an undirected graph with no cycles and forms one big connected component.

Many times, it is instructive to draw out a slightly non-trivial example on paper, and try to reason about the problem. Visualizing the problem helps the brain focus on the issues at hand, and can lead to interesting solutions.

This is the approach that I now employed. Notice that the sample example is extremely trivial, and as such doesn’t hint at any possible solution. Here is the actual example I drew out on paper. I purposely didn’t assign any points to the nodes, because I wanted to reason about the topology before I started complicating the problem by thinking about actual point values.

 

Here’s a critical step. Let’s just pick a node (say the red one), and simulate what happens. Say player 1 picks the central node. Once you do this you realize something. The entire graph has now split into multiple trees, which are disconnected from each other. This is due to rule #1, which says that no player can re-pick an already picked node. Also since the starting point is a tree, there were no cycles. Therefore all future plays will have to choose a node from one of the disconnected trees (the 4 branches of the middle node).

Ok, this is good! Why? Because this immediately makes us realize the following. The second player is *stuck* with only 1 tree! Why is this? Well, consider rule #3. Once the second player picks a random node for his first play, he can only pick nodes in that sub-tree.

At this point, I had the epiphany. “Oh my God, this is a minimax problem!”

How so? We now have 2 key pieces of information. After the first player makes his first choice, for the remaining trees, the second player will:

• Choose the tree with the highest total weight.
• Choose the node that is directly adjacent to the first player’s node in this tree.

Consider that after the first player makes his first choice, the second player is limited to one sub-tree. Now ideally he wants to claim the largest such tree to maximize his final score, and therefore bullet one holds!

Also, ideally he wants to claim ALL nodes in his tree. This will give him his maximum score. If he does not choose the node adjacent to player 1’s node, then player 1 will pick that node in the second player’s tree in his next play. Thus player 2 won’t have *his* maximum score. Therefore bullet two holds!

And that’s it! At this point, believe it or not, the whole problem is solved. The game will play out as follows.

Player 1 will pick a node with the following characteristic. Out of all the sub-trees for that node, consider the maximum value subtree. Player 1 will pick a node that “minimizes this maximum value”. This is why it is a minimax problem! This is because he knows that players 2 will pick the maximum value sub-tree from the trees that remain. And he wants to lose the fewest points, and therefore picks a node that minimizes this value for player 2.

Player 2 will predictably pick out the maximum value sub-tree from the resulting sub-trees, and specifically pick out the node next to player 1’s. After that the game just plays out by picking adjacent nodes (breaking ties arbitrarily). Knowing how the game will play out, we can compute the desired scores.

Notice how elegant this solution is:

• Everything hinges on the first play by the first player.
• This solution very elegantly satisfies all the ad-hoc sub-points we listed earlier.

Try to construct a counter-example for this algorithm, and you will find that you are unable to do so! Now the actual implementation is trivial, save for one detail. You need to do top-down DP (memoization) so that you don’t recomputed the sub-tree sizes again and again. Here is my final solution, which runs in linear time, and consists of very little code.

What a beautiful problem! 🙂