PROBLEM LINK:
Author: sherlock8696
Tester: naveen19991124
DIFFICULTY:
EASY
PROBLEM:
The problem is to find max edge possible in undirected graph such that the total no. of edges should not be greater than the total no. of connected components.
EXPLANATION:
By little obervation we can see that the best way to build a graph is to make a 2-edge-connected component with k vertices and remaining n-k vertices as n-k components with single vertex each. , so here the total no. of connected components in graph would be n-k +1 . So the max edge possible in graph is min(n-k+1 , k*(k-1)/2).
- For subtask we can iterate over k from 1 to n and find the best solution.
- Or as the graph of above equation is somewhat inverted parabola(increasing and then decreasing with k). , we can use binary search to find best possible k in log(N) time complexity .
- Or solving further the equation, It comes out that the best possible k is near to the sqrt(2(n-1) -1) .
SOLUTIONS:
Binary search (log(N))
//AUTHOR - NAVEEN KUMAR
//The Game Is ON!!!
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define nl "\n"
#define mem(v,t) memset(v,t,sizeof(v))
//MAIN CODE
int main()
{
fast
ll t = 1;
cin>>t;
while(t--){
ll n;
cin>>n;
ll lo = 1;
ll hi = n;
ll ans = 0;
ll fans = 0;
while(lo<=hi)
{
ll mid = lo + (hi-lo)/2;
if(mid-1<=n-mid+1 && (mid*(mid-1))/2<=n-mid+1)
{
ans = mid;
fans = max(fans,mid*(mid-1)/2);
lo = mid+1;
}
else
{
if(mid-1<=n-mid+1)
{
fans = max(fans,n-mid+1);
}
hi = mid-1;
}
}
cout<<fans<<"\n";
}
return 0;
}
//The Game Is OVER!!!
O(1) solution
import math
for _ in range(int(input())):
n = int(input())
if(n==1):
print(0)
continue
val = int(math.sqrt(2*(n-1) - 1))
ans = min(val*(val-1)//2 , n-val +1)
val+=1
ans = max(ans, min(val*(val-1)//2 , n-val +1) )
print(ans)