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.