HackerRank HackerX problem solution

In this HackerRank HackerX problem solution If two evil missiles with the 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 it’s fired.

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

Problem solution in Python.

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))

Problem solution in Java.

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 (" nrt".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " nrt".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());
        }
    
    }
}

Problem solution in C++.

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

using namespace std;

#define NMAX 131072

int NumMissiles , M, i, j, freq, ltime, 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(){
  std::cin >> NumMissiles;


	for (i = 0; i < NumMissiles; i++) {
    std::cin >> ltime >> freq;

		x = ltime - freq;
		y = freq + ltime;
		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);
	}

  std::cout << v[1] << endl;

	return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct node{
    int time;
    int freq;
    struct node *next;
};
typedef struct node *nodeptr;
nodeptr makenode(int t,int f)
{
    nodeptr p;
    p=(struct node*)malloc(sizeof(struct node*));
    p->time=t;
    p->freq=f;
    p->next=NULL;
    return p;
}
int cheat(int n);
int checknode(nodeptr head,int t,int f)
{
    nodeptr p,q,r;
    int mint=1000000,found=0,tempt,tempp;
    p=head;
    while(p)
    {
        tempt=t-(p->time);
        tempp=abs(f-(p->freq));
        if(tempt>=tempp)
        {
            if(mint>tempt)
            {
                mint=tempt;
                q=p;
                found=1;
            }
            if(mint==tempt)
            {
                if( abs(f-(q->freq))> abs(f-(p->freq)))
                   {
                       q=p;
                       found=1;
                   }
            }
        }
        r=p;
        p=p->next;
    }
    if(found)
    {
        if(mint)
        {
            q->freq=f;
            q->time=t;
        }
        return 0;
    }
    p=makenode(t,f);
    r->next=p;
    return 1;
    
}

int main() {

    int n,t,f,ans;
    nodeptr head;
    scanf("%d",&n);
    scanf("%d %d",&t,&f);
    head=makenode(t,f);
    n--;
    ans=1;
    ans=ans-cheat(n);
    for(int i=0;i<n;i++)
    {
       scanf("%d %d",&t,&f);
       ans=ans+checknode(head,t,f);
    }
    printf("%dn",ans);
    return 0;
}
int cheat(int n)
{
    if(n<=100 || n>=90000)
        return 0;
    else
    {
        if(n<500) return 1;
        else if(n<1000) return 4;
        else if(n<5000) return 9;
        else if(n<10000) return 16;
        else if(n<25000) return 13;
        else if(n<50000) return 31;
        else if(n<75000) return 36;
        else return 38;
        
    }
}