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 -

1. Finding an efficient algorithm to calculate the final position of the generated points.
2. For a set of points determining how many right triangles are there.

For part 1, I've used a Binary Indexed Tree (BIT) or Fenwick Tree to find final position of each point. For each point, if the position is filled up I've used a binary search to find the first position after that (note that positions wraps around) which is not filled. It was possible to remove the binary search and directly finding on the tree. But the implementation would be tricky.

There can be many other approaches for part 1. Check the official match editorial for alternative methods. Specially check the O(N) algorithm.

For part 2, we know from Thales' Theorem that - 

If A, B and C are points on a circle where the line AC is a diameter of the circle, then the angle ABC is a right angle.

It can be easily proved using Inscribed Angle Theorem that the reverse of Thales' Theorem (that is for an inscribed angle on a circle to be right, the two other points have to form a diameter) is also true.

So, for each point, we just need to check if there is an opposite point 180 degrees apart. If we find one such pair, we can make right triangles using all the remaining points.

Source code below -

/*
Problem Name : RightTriangle
Problem Number : TopCoder SRM 473 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10976
Problem Type : Geometry, Data Structure, Search
Difficulty : 6 / 10
Interest : 8 / 10
Complexity : O(N(lgP)^2)
Date : November 27, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
using namespace std;

#define rep(i,n) for(i=0;i<(n);i++)
#define MAXV 1000000

int tree[MAXV+2];
bool flag[MAXV+2];

struct RightTriangle{
 int places;
 void update(int dex, int val) {
  while(dex <= MAXV) {
   tree[dex] += val;
   if(dex == 0) break;
   dex += (dex & -dex);
  }
 }

 int read(int dex) {
  int sum = 0;
  while(dex > 0) {
   sum += tree[dex];
   dex -= (dex & -dex);
  }
  return sum;
 }
 
 int find_position(int x) {
  x++;
  //search up
  int base = read(x);
  int lo = x+1, hi = places, mid;
  int cur = read(hi);
  if(cur - base == hi - x) { //all filled up above..so search from below
   lo = 1;
   hi = x - 1;
   base = 0;
   x = 0;
  }
  while(hi-lo>=3) {
   mid = (lo + hi) >> 1;
   cur = read(mid);
   if(cur - base < mid - x) hi = mid;
   else lo = mid + 1;
  }
  for(int i = lo; i <= hi; i++) {
   cur = read(i);
   if(cur - base < i - x) return i;
  }
  assert(0);
 }

 long long triangleCount(int places, int points, int a, int b, int c) {
  if(places & 1) return 0;
  long long i;
  int x;
  int pos;
  this->places = places;
  memset(tree,0,sizeof(tree));
  memset(flag,0,sizeof(flag));
  rep(i,points) {
   x = (a * i * i + b * i + c) % places;
   if(flag[x]) pos = find_position(x); else pos = x+1;
   update(pos, 1);
   flag[pos-1] = 1;
  }
  long long res = 0;
  int half = places / 2;
  rep(i,half) if(flag[i] && flag[i+half]) res += (points-2);
  return res;
 }
};