In this HackerEarth Road Demolishing problem solution King Tle4Ever just appointed Moron as the new Engineer for his country Time Limit Exceeded. In the country of Time Limit Exceeded there are n cities and there is a direct road between each pair of cities. Now cleaning up these roads costs Tle4Ever a lot of money so he wants to demolish some of the roads but not all for sure. He wants to demolish these roads in such a way that if he picks any subset of size q of these cities, than in this subset there should exist at least one pair of cities that doesn't have a direct road between them.

He asks Moron to come up with a demolishing plan satisfying his conditions. Now, as Moron is not good at coming up with plans, he asks you to help him. Now as coming up with such a plan is really difficult, given n and q you have to tell minimum number of roads that you have to demolish to satisfy King's condition.


HackerEarth Road Demolishing problem solution


HackerEarth Road Demolishing problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ios_base::sync_with_stdio(false);
int t;
cin>>t;
assert(t>=1 && t<=100000);
while(t--)
{
ll n,q;
cin>>n>>q;
assert(n>=3 && n<=1000000);
assert(q>=3 && q<=n);
q--;
ll ans=n*n-(n%q)*((n+q-1)/q)*((n+q-1)/q);
ans=ans-(q-n%q)*(n/q)*(n/q);
ans/=2;
ans=(n*(n-1))/2-ans;
assert(ans>0);
cout<<ans<<endl;
}
return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ios_base::sync_with_stdio(false);
int t;
cin>>t;
assert(t>=1 && t<=100000);
while(t--)
{
ll n,q;
cin>>n>>q;
assert(n>=3 && n<=1000000);
assert(q>=3 && q<=n);
q--;
ll ans=n*n-(n%q)*((n+q-1)/q)*((n+q-1)/q);
ans=ans-(q-n%q)*(n/q)*(n/q);
ans/=2;
ans=(n*(n-1))/2-ans;
assert(ans>0);
cout<<ans<<endl;
}
return 0;
}#define ff first
#define ss second
#define TR(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 2000000000
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define all(x) x.begin(),x.end()


int main()
{
int t;
scanf("%d",&t);
assert(1 <= t && t <= 100000);
while(t--)
{
ll n,q;
scanf("%lld%lld",&n,&q);
assert(3 <= n && n <= 1000000);
assert(3 <= q && q <= n);
q--;
ll ans = n*n - (n%q)*((n+q-1)/q)*((n+q-1)/q) - (q - n%q)*(n/q)*(n/q);
ans /= 2;
ans = (n*(n-1))/2 - ans;
printf("%lld\n",ans);
}
return 0;
}