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 Missing Soldiers problem solution

YASH PAL, 31 July 2024
In this HackerEarth Missing Soldiers problem solution An infinite army of ants is marching on an infinite 2-D plane. Since ants are disciplined, here’s how they march: each ant chooses exactly one x coordinate and moves along it in positive y direction, starting from (x, 0). There exists exactly one ant for each x coordinate on that plane and hence there are infinite ants!
There are N horizontal barriers lying on this plane. The ith barrier is defined by (xi, yi) and di, which means that the barrier is blocking all ants which want to pass through points lying on line segment connecting (xi, yi) and (xi + di, yi). Once an ant encounters a barrier, it stops moving.
Given all the barriers, your task is to find the total number of ants, that will be ever blocked at some point in their march.
HackerEarth Missing Soldiers problem solution

HackerEarth Missing Soldiers problem solution.

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

#define pb push_back
#define mp make_pair
#define fr freopen("input.in", "r", stdin)
#define fw freopen("output.out", "w", stdout)

vector<pair<int, int> > a;

vector<pair<int, int> > merge(const vector<pair<int, int> > &x) {
int n = x.size();
if (n == 1) return x;
vector<pair<int, int> > res;
res.pb(x[0]);
for (int i = 1; i < n; ++i) {
if (x[i].first <= res.back().second) {
res.back().second = max(res.back().second, x[i].second);
} else {
res.pb(x[i]);
}
}
return res;
}

int main() {
fr; fw;
LL ans = 0;
int n, x, y, d;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d %d %d", &x, &y, &d);
a.pb(mp(x, x + d));
}
sort(a.begin(), a.end());
a = merge(a);
for (int i = 0; i < a.size(); ++i) {
ans += (a[i].second - a[i].first + 1LL);
}
cout << ans;
return 0;
}

Second solution

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define DBG cerr << "debug here" << endl;
#define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;

typedef long long ll;
const int MINN = 1;
const int MAXN = 1e5;
const int MINV = 1;
const int MAXV = 1e9;
pii v[MAXN];
int main()
{
ios_base::sync_with_stdio(0);
int n;
cin >> n;
assert(n >= MINN && n <= MAXN);
FOR(i, n)
{
int x, y, d;
cin >> x >> y >> d;
assert(x >= MINV && x <= MAXV);
assert(y >= MINV && y <= MAXV);
assert(d >= MINV && d <= MAXV);
v[i] = mp(x, x + d);
}
sort(v, v + n);
int res = 0;
int cur = 1;
//INVARIANT: cur is the first not already covered point
FOR(i, n)
{
cur = max(cur, v[i].fi);
if(v[i].se >= cur)
{
res += v[i].se - cur + 1;
cur = v[i].se + 1;
}
}
cout << res << endl;
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