Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Road Demolishing problem solution

YASH PAL, 31 July 2024
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

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes