HackerRank HackerX Problem Solution

In this post, we will solve HackerRank HackerX Problem Solution.

Update: A slight modification in the problem statement (see below)

Evil Nation A is angry and plans to launch N guided-missiles at the peaceful Nation B in an attempt to wipe out all of Nation B’s people. Nation A’s missile i will arrive in nation B at time t_i. Missile i communicates with its headquarters by unique radio signals with a frequency equal to f_i. Can you help the peaceful Nation B survive by building a defensive system that will stop the missiles dead in the sky?

Defensive system:

The only way to defend Nation B from the attacking missile is by counter attacking them with a hackerX missile. You have a lot of hackerX missiles and each one of them has its own radio frequency. An individual hackerX missile can destroy Evil Nation A’s attacking missile if the radio frequency of both of the missiles match. Each hackerX missile can be used an indefinite number of times. Its invincible and doesn’t get destroyed in the collision.

The good news is you can adjust the frequency of the hackerX missile to match the evil missiles’ frequency. When changing the hackerX missile’s initial frequency fA to the new defending frequency fB, you will need \|fB – fA\| units of time to do.

Each hackerX missile can only destroy one of Nation A’s missile at a time. So if two evil missiles with same frequency arrive at the same time, you need at least two hackerX missiles with the same frequency as the evil missiles to avoid damage.

If two evil missles with same frequency arrive at the same time, we can destroy them both with one hackerX missile. You can set the frequency of a hackerX missile to any value when its fired.

What is the minimum number of hackerX missiles you must launch to keep Nation B safe?

Input Format:
The first line contains a single integer N denoting the number of missiles.
This is followed by N lines each containing two integers t_i and f_i denoting the time & frequency of the i^th missile.

Output Format:
A single integer denoting the minimum number of hackerX missiles you need to defend the nation.

Constraints:
1 <= N <= 100000
0 <= t_i <= 100000
0 <= f_i <= 100000
t₁ <= t₂ <= … <= t_N

Sample Input #00

Sample Output #00

Explanation #00

A HackerX missile is launched at t = 1 with a frequency f = 1, and destroys the first missile. It re-tunes its frequency to f = 2 in 1 unit of time, and destroys the missile that is going to hit Nation B at t = 2. It re-tunes its frequency back to 1 in 1 unit of time and destroys the missile that is going to hit the nation at t = 3. It is relaunched at t = 5 with f = 1 and destroys the missile that is going to hit nation B at t = 5. Hence, you need only 1 HackerX to protect nation B.

Sample Input #01

Sample Output #01

Explanation #01

Destroy 1 missile at t = 1, f = 1. now at t = 2, there is a missile with frequency 3. The launched missile takes 2 units of time to destroy this, hence we need a new hackerX missile to destroy this one. The first hackerX missile can destroy the 3rd missile which has the same frequency as itself. The same hackerX missile destroys the missile that is hitting its city at t = 5. Thus, we need atleast 2 hackerX missiles.

Table of Contents

HackerX C Solution

 #include <stdio.h>


void conquer(int a[],int b[],int low,int mid,int high){

    int i,m,k,l,temp[100002],temp2[100002];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){
        if(a[l]<=a[m]){
             temp[i]=a[l];
             temp2[i]=b[l];
             l++;
         }
         else{
             temp[i]=a[m];
             temp2[i]=b[m];
             m++;
         }
         i++;
    }
    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=a[k];
             temp2[i]=b[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=a[k];
             temp2[i]=b[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         a[k]=temp[k];
         b[k]=temp2[k];
    }
}
void divide(int a[],int b[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         divide(a,b,low,mid);
         divide(a,b,mid+1,high);
         conquer(a,b,low,mid,high);
    }
}
int main()
{
    int t,at[100002],af[100002],i,j,countmissile=1,saved,bt[1002],bf[1002],timechange,freqchange,k1;
    int z1[100002],z2[100002];
    int ans[100002];
    
    scanf("%d", &t);
    for(i=0;i<t;i++)
    {
        scanf("%d %d",&at[i],&af[i]);
        z1[i]=at[i]-af[i];
        z2[i]=at[i]+af[i];
    }
    divide(z1,z2,0,t-1);
    for(i=0;i<t;i++)
    {
        int var= z2[i-1];
        int low = 0;
        int high = countmissile-1;
        while(low <= high)
        {
            int mid = (low + high )/2;
            if(ans[mid]>var)
                low = mid+1;
            else
                high  = mid -1;
        }
        if(countmissile <= low)
        {
            ans[countmissile] = var;
            countmissile++;
        }
        else{
            ans[low] = var;
        }

    }
    printf("%d", countmissile);
}

HackerX C++ Solution

#include <stdio.h>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

#define NMAX 131072

int N, M, i, j, f, t, x, y, lmax, v[NMAX << 1];
map<pair<int, int>, int> cnt;
map<pair<int, int>, int>::iterator it;
map<int, int> ycoord_map;
set<int> ycoord;
set<int>::iterator yit;

int get_query(int a) {
    int b = NMAX + a - 1, result = 0;

    while (b > 1) {
        if ((b & 1) == 1)
            result = max(result, v[b - 1]);

        b = b >> 1;
    }

    return result;
}

void update(int a, int val) {
    int b = NMAX + a - 1;

    while (b >= 1) {
        v[b] = max(v[b], val);
        b = b >> 1;
    }
}

int main() {
    scanf("%d", &N);

    for (i = 0; i < N; i++) {
        scanf("%d %d", &t, &f);
        x = t - f;
        y = f + t;
        cnt[make_pair(-x, -y)]++;
        ycoord.insert(y);
    }

    for (M = 0, yit = ycoord.begin(); yit != ycoord.end(); yit++) {
        M++;
        ycoord_map[*yit] = M;
    }

    for (it = cnt.begin(); it != cnt.end(); it++) {
        j = ycoord_map[-(it->first.second)];
        lmax = get_query(j);
        lmax++;
        update(j, lmax);
    }

    printf("%d\n", v[1]);

    return 0;
}

HackerX C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'missileDefend' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY missiles as parameter.
     */

    public static int missileDefend(List<List<int>> missiles)
    {
        var points = new List<Point>();
            foreach (List<int> missile in missiles)
            {
                points.Add(new Point(missile[0] - missile[1], missile[0] + missile[1]));
            }

            var sortedArray = points.OrderBy(o => o.X).ThenBy(o => o.Y).Select(s=>s.Y).ToList();

            var list = new SortedSet<int>();
            list.Add(sortedArray[0]);

            for (int i = 1; i < sortedArray.Count; i++)
            {
                var y = sortedArray[i];
                var set = list.GetViewBetween(0,y);
                if (set.Count != 0)
                {
                    list.Remove(set.Last());
                }
                list.Add(y);
            }

            return list.Count();
    }
    
    public class Point {
        public int X {get; set;}
        public int Y {get; set;}
        public Point(int x, int y)
        {
            X = x;
            Y = y;
        }
    }
}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int n = Convert.ToInt32(Console.ReadLine().Trim());

        List<List<int>> missiles = new List<List<int>>();

        for (int i = 0; i < n; i++)
        {
            missiles.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(missilesTemp => Convert.ToInt32(missilesTemp)).ToList());
        }

        int result = Result.missileDefend(missiles);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

HackerX Java Solution

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    static class Point implements Comparable<Point> {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Point o) {
            if (x == o.x) {
                return y - o.y;
            }
            return x - o.x;
        }
    }
    
    public static void solve(Input in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        Point[] ps = new Point[n];
        for (int i = 0; i < n; ++i) {
            int t = in.nextInt();
            int f = in.nextInt();
            ps[i] = new Point(t - f, t + f);
        }
        
        Arrays.sort(ps);
        
        int[] max = new int[n + 1];
        Arrays.fill(max, Integer.MIN_VALUE);
        max[0] = Integer.MAX_VALUE;
        
        for (Point p : ps) {
            int l = 0, r = n;
            while (l < r - 1) {
                int mid = (l + r) / 2;
                if (max[mid] > p.y) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            max[l + 1] = p.y;
        }
        
        int ans = 0;
        while (ans < n && max[ans + 1] > Integer.MIN_VALUE) {
            ++ans;
        }
        
        out.println(ans);
    }

    

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    
    }
}

HackerX JavaScript Solution

function lowerBound(array, bound) {
  var first = 0;
  var count = array.length;

  while (count > 0) {
    var step = Math.floor(count / 2);
    var it = first + step;
    if (array[it] < bound) {
      first = it + 1;
      count -= step + 1;
    } else {
      count = step;
    }
  }

  return first;
}

function processData(input) {
  var lines = input.split('\n');
  var missiles = [];
  var hackers = [];
  var N = parseInt(lines.shift(), 10);

  while (N--) {
    var tf = lines.shift().split(' ');
    var t = parseInt(tf.shift(), 10);
    var f = parseInt(tf.shift(), 10);
    missiles.push([t+f, t-f]);
    hackers.push(Number.MAX_VALUE);
    max = t;
  }

  missiles.sort(function (a, b) {
    return b[0] - a[0] || b[1] - a[1];
  }).forEach(function (missile, i) {
    //console.log(missile, lowerBound(hackers, missile[1]), hackers[lowerBound(hackers, missile[1])], missile[1]);
    hackers[lowerBound(hackers, missile[1])] = missile[1];
  });
  //console.log(hackers);

  console.log(lowerBound(hackers, Number.MAX_VALUE));
} 


process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

HackerX Python Solution

n = int(input())
inp = (map(int, input().split()) for i in range(n))
p = sorted(list((a + b, a - b) for a, b in inp))
a = list(y for x, y in p)
d = []
for x in a:
    low, high = -1, len(d) # >, <=
    while high - low > 1:
        mid = (low + high) >> 1
        if d[mid] > x:
            low = mid
        else:
            high = mid
    if high == len(d):
        d.append(x)
    else:
        d[high] = x
print(len(d))