hackerrank java challenge

https://www.hackerrank.com/contests/codewhiz-java-march-2016/challenges

Not much algorithm but a nice exercise on Java features.

interface Comparable {
  int compareTo(E o);
}

try {
} catch (Exception e) {
  throw e;  // rethrow
}

lambda expression

https://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html

num -> {
  for (int i = 2; i * i <= num; ++i) {
    if (num % i == 0) return false;
  }
  return true;
}

A nice OS book, Three Easy Pieces

http://pages.cs.wisc.edu/~remzi/OSTEP/

Disclaimer, I found this on Internet and know nothing about the author. This is a nice book that explains things quite well.

bash

http://mywiki.wooledge.org/BashSheet#Syntax

If you need to run several commands in background, do it like this:

./cmd1 args1 & ./cmd2 args2 & ./cmd3 args3

; is used to separate commands executed synchronously.

install mesos

Turns out to be much more work than expected.

I had to install a few packages manually because my ubuntu is too old, and apt-get cannot find anything.

libapr and its friends
svn headers
libcurl
and cyrus sasl

final command line is:
../configure LD_LIBRARY_PATH=/usr/local/lib SASL_PATH=/usr/local/lib/sasl2 --with-apr=/usr/local/apr --with-svn=/usr/local --with-curl=/usr/local --with-sasl=/usr/local

just typed make and it would take a while to finish.

Ramsey's theorem

The problem is classic, given 6 people, either there is a group of 3 who know each other, or there is a group of 3 who do not know each other, assuming the known relationship is bidirectional.

Proof from West's Graph Theory book.
Use pigeon-hole principle, among 6 nodes, in G and ~G, at least one of them have deg 3, because deg_G(v) + deg_~G(v) = 5. Let's say it is G, and node v has deg >= 3. Now we consider 3 neighbors of v, none of them have an edge between them, otherwise we have a triangle. It follows that the three neighbors form a triple with no edges.

Facebook Hacker Cup Round 2

Problem B: Carnival Coins.

Problem: You play a game with N coins. Each round you can use some number of coins and flip all of them. If the number of heads is at least K, then you win a point. You keep playing until all N coins are used. Calculate the expected number of points, assuming you play optimally. Flipping a single coin turns head with probability P.

Constraints: N <= 3000, K <= N, 0 <= P <= 1

First, we can calculate the probability prob[n][k], getting exactly k head when flipping n coins. Then it is easy to get cum[n] which is the probability to get at least K heads with n coins.

prob[n][k] = P * prob[n-1][k-1] + (1-P) * prob[n-1][k]
and prob[0][0] = 1.0

cum[n] = prob[n][K] + prob[n][K+1] + ... + prob[n][K]

Next, we need to compute dp[n], which is the expected number of points with n coins, if play optimally.
dp[n] could be cum[n] if we flip all n coins at once. Or we could split n coins into two subsets, one with j coins and the other with n-j coins, for j = 1 to n-1. Then dp[n] is the max among cum[n], dp[1] + dp[n-1], ..., dp[n-1] + dp[1]

Implementation is straightforward.

During contest, I missed both observation. Was calculating prob[n][k] using binomial coefficients and N=3000 is simply too big for double. Didn't see the recurrence. Also not seeing the simple dp to split coins into two subproblems.

===========================================
Problem  C : Snakes and Ladders

This problem looks intimidating, as N is 200000, so we need a O(nlogn) solution. What I have observed during contest:
1. It might help to find ladders with same height and no higher ladders in between. This is because for such ladders, any pair can hang a snake.
2. To compute the sum (X_j - Xi)^2, we can actually compute this sum in linear time.

Looking at the sum again, it is actually simple.
sum_(1<=i= sum_(1<=i= (n-1) * sum_(1<=i<=n) X_i^2 - second

while second = (sum_(1<=i<=n) X_i)^2 - sum_(1<=i<=n) X_i^2

To partition snakes into adjacent sets, we process each ladder in order of their x-value, and maintain a stack of previous heights in decreasing order. For each ladder, it kills all previous smaller heights, and append the current height to end of stack.

Indeed prime codespring

https://www.hackerrank.com/contests/indeed-prime-codesprint/challenges

Problem D flatland-roads

Given an undirected connected graph with n = 10^5 vertices and m = 2*10^5 edges, and P = 15. Find out the number of vertices reachable from v using at most P bridges, for every vertex v.

1. All bridges can be identified by dfs. Let d[u] be the time that vertex u is discovered in dfs, and low[u] be the d[] value of the vertex w with minimum d[] value, such that w is adjacent to either u or one of its descendants. In undirected graph, dfs traversal only has tree edge and back edge, and only tree edge may become a bridge. It is easy to see that edge (u,v) is a bridge if and only if u is a parent of v and d[v] = low[v].

2. If we remove all bridges, each component behaves the same in counting. So we can collapse nodes in the same component into a super vertex, and the results graph is a tree!

3. Now that we have a tree, we can compute the numbers recursively. A few book-keeping in place. Let
reach[c][k] be the number of vertices that supernode c may reach with at most k superedges (bridges).
all[c][k] be the number of vertices that supernode c may reach with at most k superedges, either via its child, or via its parent.

Base case: reach[c][0] = all[c][0] = supernode[c].size
Recurisve step:
reach[c][k] = supernode[c].size + sum_{child} reach[child][k-1]
all[c][k] = reach[c][k] + all[parent][k-1] - reach[c][k-2]
we need to subtract the path from parent back to c so that we do not double count.

The dependency is a bit tricky to figure out, and I did the dumb thing of DP with memoization.

code here


Problem C needs an AVL tree or Red-Black tree with each node keeps a count of nodes in its subtree, and I really need to write one myself. Also a good place to test my implementation, if I ever wrote one. Writing RB-tree is tricky.

Problem E, I do not know.