Three Medians of Triangles are Concurrent

There are two proofs with the same basic idea, proving that two medians intersect and split the line connecting one endpoint and its midpoint into 2:1.

A cute proof from Wolfram, we are to show the intersection cuts the line into 2:1, so we need to complete some triangle with some split already 2:1.
http://demonstrations.wolfram.com/TheMediansOfATriangleAreConcurrentAVisualProof/

The other way is to connect the two midpoints and show that an upside down triangle is similar to the bottom triangle. They are because the segment with two midpoints parallel to the base.

fast io in programming competition

copied from neal's cf blog. 

ios::sync_with_stdio(false);
cin.tie(nullptr);

Reading Bill Coughran

https://www.sequoiacap.com/people/bill-coughran/

Bill was once leading Google's Engineering team and he has many interesting perspective in his sequoia profile linked above.

For example, (you do not need a lot of engineers) the best team is 2 to 8 people in the same room, and a team with good people can steer themselves.

Bill stayed in Bell labs for 20 years, and he thought he should left sooner. Change every few years is healthy.

Back to writing

After a long break, I find it compelling to start writing again, and not limit myself to programming competition or interview problems.

Candy distribution problem

Candy distribution problem

There are n students in a circle, each of them start with a[0] ... a[n-1] candies. There is also an infinite pile of candies. Each round, student i checks his candies a[i], if a[i] is odd, then he gets one candy from the pile to make a[i] even, and then pass a[i]/2 to student i+1. Note that student n-1 will pass half of his candies to student 0. The process stops when all students have equal number of candies.

The problem is, does this ever converge, that is, does this process always end in finite steps?

The answer is:














YES.

Proof: W.l.o.g. let student 0 be the one with maximum number of candies. That is, a[0] >= a[i] for i = 0..n-1. Let b[0] = a[0] if a[0] is even, a[0]+1 if a[0] is odd. We claim that no student has more than b[0] candies in the process. This puts a ceiling on the number of candies a student can have. On the other hand, Let amin = a[j] be the minimum candies when students started, then each step, some student with amin candies will have their number of candies strictly greater. An induction will yield that the students will have equal number of candies eventually.

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.

CF 319, hackerrank worldcup

div2
problem B
Given n = 10^6 integers and integer m <= 1000, check whether a subset of the integers sum up to a number that is a multiple of m.

This looks like subset sum but is actually not. I had several false starts and one route that looks promising is that if we are not looking for sum, instead we look for subtraction, then it is easy, just find two numbers with same remainder modulu m. However we need sum here. The solution is actually simple, keep a map of remainders that you have seen already, and update with next element, either you use it or not, then you get an updated list of remainders that you can make with element 1..k. In the end you just check whether you have hit remainder = 0.


Hackerrank university worldcup

swapping bridges: the key is that with n nodes and n directed edges, the graph is a collection of disjoint cycles. Proof by induction.

worldcup game: it appears to be a PSPACE-complete problem, and thus insurmountable. However, we are dealing with a tree here and the answer is, one player takes the biggest subtree and the other player takes the rest. So the answer would be the same if each player is trying to minimize the opponent's score. One dfs on the tree is enough.

Bishop war: at the current row, you only care your previous row, yet each cell can attack left or right or both, thus you need 2 bits to encode the state, 0,1,2,3. This makes the encode/decode slightly more complicated. And there is one catch, you need to skip invalid previous row to speed things up. For my case, a speed up of 7s to .5s was observed.

Alien's age: Haven't solved yet but looks it is a binary search on the max age, and to do the check, you can use 4 types of footprints to run through the matrix, mark cells as don't care if you already covered them. And use count of 0,1,2 for none, taken, don't care. You also need prefix sum to make it fast to query a range of column or diagonal.

The web technology - CGI

In the old days, web servers were serving static content only, that is, when a browser requests www.example.com/mypage.html, there is actually a file named mypage.html and the server will fetch the page and return it to the client in its response.

Then people want more dynamic stuff and CGI is the first solution. When a browser requests example.com/cgi-bin/myscript.pl, the server is not returning the script itself, instead, the server will run myscript.pl and send back the output. The binary/script is normally put in a directory called cgi-bin, and perl is a popular language to write that script. However, you can put anything in cgi-bin, anything executable, for example, a c++ binary, provided that the server knows how to execute it.

This approach launches a separate process for each request and has several consequences. Forking a process and then shut it down is expensive, especially when the actual computation is cheap and quick.

Competing technologies available, Java servlet, Microsoft ASP.

status update

I have graduated from UC Riverside and now works as a software enginner.

facebook hacker cup round 2

I was lucky enough to get into round 2, but it was a disaster.
After 3 hours, I had 10pt problem submitted, but I know somehow it would fall. End up getting 0 points.

lazy sort: the observation is that at any time, the partial solution must be a consecutive segment of (1..n), or (n..1). For some reason I was confusing it with a harder problem, where you can pop_front and pop_back, in addition to push_back and push_front.
The solution processes the given list, and keep track of current min and max, and the start and end of remain list. Now if there is a solution, then either the head or the tail of the remaining list is min-1 or max+1, and only one of the four possibility holds. So you can deterministically follow that one, or return false.

all critical: the problem asks for expectation. As usual there are two possible approaches, one is using definition, that is, we compute an infinite sum, pr(X=n) * n for n = 0 to inf. It takes a dynamic programming dp(s, l), meaning the probability to get s success in the first l rounds. dp(0, 0) = 1.0, dp(s, l) could come from dp(k, l-1) for k = 0, 1, 2, ..., s, that is, dp(s, l) = sum_{k} dp(k, l-1) * (N-k, s-k) because in round l-1 we had k success, and there can be at most N = 20 success. In round l we must have s - k success, and that must come from N-k candidates. Once we have dp(N, l) for l = 1, 2, ..., n for some large enough n, we can compute expectation as sum_{l} [dp(N,l) - dp(N, l-1)] * l. The problem asks for a precision of 1e-5, so L = 1e6 should be enough.
The other approach uses recursive idea. Let E[n] be the expected number of trials when there are exactly n possible success. Now consider the first trial. We could have 0, 1, ..., n success. If we have 0 success, then we need another E[n] trials, if we have 1 success, then we need another E[n-1] trials, ..., therefore
E[n] = 1 + E[n] * (1-p)^n + E[n-1] * C(n,1) * p * (1-p)^n-1 + ... + E[n-k] * C(n,k) * p^k * (1-p)^(n-k) + ... + E[0] * p^n
You should convince yourself that E[0] = 0. Then it is simple to calculate E[n] for n = 1 to N, and E[N] is the answer.

auto complete strikes back: The first step is to build a trie with all words. Then we solve the problem recursively on the tree. Consider a subtree rooted at T, let cost(T, k) be the cost to get k words if we only use words in this subtree. Then cost(root, K) is our answer. Obviously cost(T, 0) is 0. To get k words, we need to get k1 from child c1, k2 from child c2, ..., such that k1 + k2 + ... = k, and the cost is the sum of the child subtree's cost. A special case is that when T is a word, then the sum of k1, k2, ... maybe k-1. The cost to get the word in T is the number of links to follow to get to node T, which can be stored when we build the trie, call it the depth. Another case that warrants special treatment is k = 1, in this case we can have a cost of T.depth because T must have at least one word in its subtree and to get one word we only need to arrive at node T and no further.
One implementation challenge is to manage memory. Both new/delete and use a global array to allocate node will work, but my mistake to put a local array of size 26*100 caused stack overflow and segmentation fault, and it takes quite some time to find out the culprit.

problem D is supposed to be a complicated segment tree problem. To be continued.

syntax highlight template

syntax highlight

$(document).bind('click', function(e) {
            var $clicked = $(e.target);
            if (! $clicked.parents().hasClass("staticMenu")){
                $(".staticMenu dd ul").hide();
                $(".staticMenu dt a").removeClass("selected");
            }        });

Java generics

Java introduced generics, but then I realized that it does not have the equivalent of typedef as C/C++. So if you have something like

Map<String, Future<MyLongClass>> mp = new HashMap<String, Future<MyLongClass>>();

 
this is tedious and annoying, why do I have to type the same thing twice? In java 7, you can write this

Map<String, Future<MyLongClass>> mp = new HashMap<>();

For java 6 and earlier, here is one solution, which seems to be the approach of google guava library as well.

http://www.ibm.com/developerworks/library/j-jtp02216/

public class Util {
  static Map newHashMap() {
    return new HashMap();
  }
}

Here is a small test file

// UtilTest.java
import java.util.HashMap;
import java.util.Map;

public class UtilTest {
    public static void main(String[] args) {
        Pair<Integer, String> p1 = new Pair<>(1, "apple");
        Pair<Integer, String> p2 = new Pair<>(2, "pair");
        boolean same = Util.<Integer, String>compare(p1, p2);
        System.out.println(same);

        Map<String, String> hashMap = Util.newHashMap();
        hashMap.put("key", "value");
        for (Map.Entry<String, String> entry : hashMap.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}

remove acroread from ubuntu

sudo apt-get purge adobereader-enu

a nim-like game

Two players, starting with one pile of n stones. The players take turns. In one move, the current player can pick any pile of stones and split into 2 or 3 new piles with each new pile having at least 1 stone. The player cannot make a move loses. Given n, can you determine the winner, assuming both play optimally?

The answer is deceptively simple, so spend at least one day before you look at the solution below.





























Solution:
n = 1, first player loses
n >= 2, if n is even, then the first player can split into two equal piles and mimic the second players move, so the first player wins.
else n is odd, but then the first player can split into 1, k, k, assuming n = 2*k +1. Then the first player can again mimic the second players moves. So the first player wins as well.

In summary, the first player wins for all n >= 2. Simple, huh?