UVa 11300 - Spreading the Wealth

Problem link: http://uva.onlinejudge.org/external/113/11300.html

Problem in short -

Given n people sitting on a circular table, each with some number of coins, you have to redistribute the coins in a manner so that everyone has equal number of coins. Any person can only pass coins to his left or right. Calculate the minimum number of coins that need to be transferred.

Floating Median

Today I've started to brush up my data structure knowledge. I've started with Binary Indexed Tree (BIT). TopCoder has an excellent tutorial on this. Initial segment of the tutorial is a bit hard to understand as it starts with notations and mathematical formulations but if you read that segment 2/3 times, things should be clear.

The problem I've solved requires you to -

Given a sequence of N integers in the range [0,M), find the sum of medians of N-K+1 contiguous subsequences of length K. (1<=N<=250,000; 1<=K<=1000, M=65536).