HackerEarth Missing Soldiers problem solution

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.

#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;
}

HackerEarth Missing Soldiers problem solution

HackerEarth Missing Soldiers problem solution.

Second solution

Leave a Reply

Pages

Practice