TopCoder SRM 473 Div 1 Medium (RightTriangle)

Problem Link : http://www.topcoder.com/stat?c=problem_statement&pm=10976

In this problem,

given some points on the perimeter of a circle that were selected from a poll of equidistant points, we have to calculate how many different right triangles we can make from those points. points are placed using a generator program. If a position is filled up by a previous point, it will be placed on the next available position.

Now this problem has 2 parts -

Product of Prices

I've solved another Binary Indexed Tree problem today. It is the Div 1 Hard problem from TopCoder SRM 424. This problem is a bit harder to formulate than the previous one. You can check the complete analysis of the problem in the official match editorial. And don't forget to check the tutorial if you have any difficulty understanding BIT.

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).