Table of Contents
HackerX – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ HackerX HackerRank Solution
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define fo(i,a,b) dfo(int,i,a,b)
#define fr(i,n) dfr(int,i,n)
#define fe(i,a,b) dfe(int,i,a,b)
#define fq(i,n) dfq(int,i,n)
#define nfo(i,a,b) dfo(,i,a,b)
#define nfr(i,n) dfr(,i,n)
#define nfe(i,a,b) dfe(,i,a,b)
#define nfq(i,n) dfq(,i,n)
#define dfo(d,i,a,b) for (d i = (a); i < (b); i++)
#define dfr(d,i,n) dfo(d,i,0,n)
#define dfe(d,i,a,b) for (d i = (a); i <= (b); i++)
#define dfq(d,i,n) dfe(d,i,1,n)
#define ffo(i,a,b) dffo(int,i,a,b)
#define ffr(i,n) dffr(int,i,n)
#define ffe(i,a,b) dffe(int,i,a,b)
#define ffq(i,n) dffq(int,i,n)
#define nffo(i,a,b) dffo(,i,a,b)
#define nffr(i,n) dffr(,i,n)
#define nffe(i,a,b) dffe(,i,a,b)
#define nffq(i,n) dffq(,i,n)
#define dffo(d,i,a,b) for (d i = (b)-1; i >= (a); i--)
#define dffr(d,i,n) dffo(d,i,0,n)
#define dffe(d,i,a,b) for (d i = (b); i >= (a); i--)
#define dffq(d,i,n) dffe(d,i,1,n)
#define ll long long
#define alok(n,t) ((t*)malloc((n)*sizeof(t)))
#define pf printf
#define sf scanf
#define pln pf("\n")
#define inf 111111111111111111ll
struct pr {
int x, y;
};
int pcomp(const void *aa, const void *bb) {
pr a = *(pr*)aa;
pr b = *(pr*)bb;
if (a.x != b.x) return a.x - b.x;
return b.y - a.y;
}
int main() {
int n;
sf("%d", &n);
pr *p = alok(n, pr);
ll miny = inf, maxy = -inf;
fr(i,n) {
int t, f;
sf("%d%d", &t, &f);
p[i].x = f + t;
p[i].y = f - t;
if (miny > p[i].y) miny = p[i].y;
if (maxy < p[i].y) maxy = p[i].y;
}
fr(i,n) p[i].y -= miny;
maxy -= miny;
qsort(p, n, sizeof(pr), pcomp);
int ans = 0;
maxy++;
int ht = 1;
for (int sz = maxy, nsz = sz + 1 >> 1; sz > 1; ht++, sz = nsz, nsz = sz + 1 >> 1);
int *tr[ht];
for (int sz = maxy << 1, nsz = sz + 1 >> 1, h = 0; sz > 1; h++, sz = nsz, nsz = sz + 1 >> 1) {
tr[h] = alok(nsz, int);
fr(i,nsz) tr[h][i] = 0;
}
fr(i,n) {
int mx = 0;
for (int h = 0, R = p[i].y; R; h++, R >>= 1) {
if (R & 1) {
int vl = tr[h][--R];
if (mx < vl) mx = vl;
}
}
mx++;
if (ans < mx) ans = mx;
for (int h = 0, R = p[i].y; h < ht; h++, R >>= 1) {
if (tr[h][R] < mx) tr[h][R] = mx; else break;
}
}
pf("%d\n", ans);
}
Java HackerX HackerRank Solution
import java.io.*;
import java.util.Arrays;
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) {
// System.err.println(p.y);
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;
}
// System.err.println(Arrays.toString(max));
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());
}
}
}
Python 3 HackerX HackerRank 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))
Python 2 HackerX HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
from sys import stdin, stdout
read_ints = lambda: map(int, raw_input().split())
read_floats = lambda: map(float, raw_input().split())
def main(testcases = None):
n = read_ints()[0]
node = []
if testcases:
print "#case %s" % testcases
for i in range(n):
t, f = read_ints()
node.append((t-f, t+f))
node.sort()
if testcases:
print node
tmp = []
tmp.append(node[0][1])
size = 1
for i in range(1, n):
if node[i][1] < tmp[-1]:
if testcases:
print i, node[i][1], -1, tmp[-1]
tmp.append(node[i][1])
size += 1
else:
pos = bi_search(tmp, size, node[i][1])
if testcases:
print i, node[i][1], pos, tmp[pos]
tmp[pos] = node[i][1]
print size
# array descend
def bi_search(array, size, target):
l = 0
r = size-1
ret = -1
while (l <= r):
mid = (l + r) // 2
if array[mid] == target:
return mid
if array[mid] < target:
ret = mid
r = mid -1
if array[mid] > target:
l = mid + 1
return ret
if __name__ == '__main__':
'''
t = read_ints()[0]
for i in range(t):
#main(i+1)
main()
'''
main()
C HackerX HackerRank 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);
}
Leave a comment below
