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
Created
October 13, 2011 19:06
-
-
Save yuvipanda/1285180 to your computer and use it in GitHub Desktop.
Cliques (InterviewStreet CodeSprint Fall 2011)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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 ; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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?