Cliques (InterviewStreet CodeSprint Fall 2011)

Hint.md

Turan's theorem gives us an upper bound on the number of edges a graph can have if we wish that it should not have a clique of size x. Though the bound is not exact, it is easy to extend the statement of the theorem to get an exact bound in terms of n and x. Once this is done, we can binary search for the largest x such that f(n,x) <= m. See: http://en.wikipedia.org/wiki/Tur%C3%A1n's_theorem

problemsetter.cpp

#include<stdio.h>

int solve1(int n,int k)
{
 int g1 = n%k ;
 int g2 = k - g1 ;
 int sz1 = n/k + 1 ;
 int sz2 = n/k ;
 int ret = g1*sz1*g2*sz2 + g1*(g1-1)*sz1*sz1/2 + g2*(g2-1)*sz2*sz2/2 ;
 return ret ; 
}

int solve(int n,int e)
{
 int k,low = 1,high = n + 1 ;
 while(low + 1 < high)
 {
  int mid = low + (high - low)/2 ;
  k = solve1(n,mid) ;
  if(k < e) low = mid ;
  else high = mid ;
 }
 return high ;
}

int main()
{
 int i,j,n,k,runs ;
 scanf("%d",&runs) ;
 while(runs--)
 {
  scanf("%d%d",&n,&k) ;
  int ret = solve(n,k) ;
  printf("%d\n",ret) ;
 }
 return 0 ;
}

How to extend the statement of Turan's theorem to get an exact bound in terms of n and x? I cannot figure it out. Could you be more specific?