HackerEarth Road Demolishing problem solution

YASH PAL, 31 July 202416 February 2026

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("%lldn",ans);
    }
    return 0;
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply