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.