Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • 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
Programming101
Programming101

Learn everything about programming

HackerEarth Number of overtakes problem solution

YASH PAL, 31 July 2024
In this HackerEarth Number of overtakes, problem-solution A race is organized among N horses of a kingdom. Every horse has a velocity (in m/sec) that is denoted by an array V elocity[] where Velocity[i] represents the velocity of the ith horse. The indexing of the array is 0-based.
All the horses are standing at different starting positions. The starting position of every horse is represented by an array pos[] where pos[i] denotes the starting position of the ith horse. The indexing of the array is 0-based. The pos[] array is a permutation of integers 1 to N. A horse who is standing at  position is considered to be ahead of the horse who is standing at position j if and only if i > j.
The finish line of the race is 10^100000) meters ahead. An overtake occurs when horse A, whose starting position is less than horse B, finishes the race earlier than horse B. Your task is to determine the number of overtakes that has occurred during the race.
HackerEarth Number of overtakes problem solution

HackerEarth Number of overtakes problem solution.

#include<bits/stdc++.h>
#define ll long long int
using namespace std;

ll _mergeSort(int arr[], int temp[], int left, int right);
ll merge(int arr[], int temp[], int left, int mid, int right);

ll mergeSort(int arr[], int array_size)
{
int temp[array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}

ll _mergeSort(int arr[], int temp[], int left, int right)
{
int mid;
ll inv_count = 0;
if (right > left) {
/* Divide the array into two parts and
call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left) / 2;
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid + 1, right);

inv_count += merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}

ll merge(int arr[], int temp[], int left,
int mid, int right)
{
int i, j, k;
ll inv_count = 0;

i = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];

/* this is tricky -- see above
explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}

while (i <= mid - 1)
temp[k++] = arr[i++];

while (j <= right)
temp[k++] = arr[j++];

for (i = left; i <= right; i++)
arr[i] = temp[i];

return inv_count;
}

int main(){
int N;
cin>>N;
assert(N >= 2 && N <= 100000);

int Velocity[N];
for(int i = 0 ; i < N ; i++)
{
cin>>Velocity[i];
assert(Velocity[i] >= 1 && Velocity[i] <= 10000000);
}

int pos[N];
for(int i = 0 ; i < N ; i++)
{
cin>>pos[i];
assert(pos[i] >= 1 && pos[i] <= N);
}

int final[N];
for(int i = 0 ; i < N ; i++)
{
final[pos[i]-1] = Velocity[i];
}

ll ans = mergeSort(final,N);
cout<<ans<<endl;
}

Second solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

template<typename T>
struct MOS{
tree<pair<T, int>, null_type, less<pair<T, int>>, rb_tree_tag,tree_order_statistics_node_update> os;
map<T, int> cnt;
int size(){
return os.size();
}
int order_of_key(const T &x){
return os.order_of_key({x, 0});
}
int ge(int x){
return os.size() - order_of_key(x);
}
void insert(const T &x){
os.insert({x, cnt[x]++});
}
void erase(const T &x){
os.erase({x, --cnt[x]});
}
};
MOS<int> os;

typedef long long ll;

const int maxn = 1e6 + 17;
int n;
pair<int, int> p[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> p[i].second;
for(int i = 0; i < n; i++)
cin >> p[i].first;
sort(p, p + n);
ll ans = 0;
for(int i = 0; i < n; i++)
ans += os.ge(p[i].second + 1), os.insert(p[i].second);
cout << ans << 'n';
}
coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

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
©2025 Programming101 | WordPress Theme by SuperbThemes