Algorithm


Problem Name: Data Structures - Almost Equal - Advanced

Problem Link: https://www.hackerrank.com/challenges/almost-equal-advanced/problem?isFullScreen=true

In this HackerRank in Data Structures - Almost Equal - Advanced solutions,

A Sumo wrestling championship is scheduled to be held this winter in the HackerCity where N wrestlers from different parts of the world are going to participate. The rules state that two wrestlers can fight against each other if and only if the difference in their height is less than or equal to K,
(i.e) wrestler A and wrestler B can fight if and only if |height(A)-height(B)|<=K.

 

Given an array H[], where H[i] represents the height of the ith fighter, for a given l, r where 0 <= l <= r < N, can you count the number of pairs of fighters between l and r (both inclusive) who qualify to play a game?

Input Format
The first line contains an integer N and K separated by a single space representing the number of Sumo wrestlers who are going to participate and the height difference K.
The second line contains N integers separated by a single space, representing their heights H[0] H[1] ... H[N - 1].
The third line contains Q, the number of queries. This is followed by Q lines each having two integers l and r separated by a space.

Output Format
For each query Q, output the corresponding value of the number of pairs of fighters for whom the absolute difference of height is not greater that K.

Constraints
1 <= N <= 100000
0 <= K <= 109
0 <= H[i] <= 109
1 <= Q <= 100000
0 <= l <= r < N

Sample Input

5 2
1 3 4 3 0
3
0 1
1 3
0 4

Sample Output

1
3
6

Explanation
Query #0: Between 0 and 1 we have i,j as (0,1) and |H[0]-H[1]|=2 therefore output is 1.
Query #1: The pairs (H[1],H[2]) (H[1],H[3]) and (H[2],H[3]) are the pairs such that |H[i]-H[j]| <=2. Hence output is 3.
Query #2: Apart from those in Query #1, we have (H[0],H[1]), (H[0], H[3]), (H[0], H[4]), hence 6.

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void QQ(int x,int y);
void add(int X);
void removee(int X);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);
int read(int idx);
void update(int idx,int val,int MaxVal);
int H[300000],rH[300000],q[2][100000],qq[2][100000],idx[300000],tree[300001],NN,cl,cr;
long long ans[100000],x;

int main(){
  int K,Q,i,j;
  scanf("%d%d",&NN,&K);
  for(i = 0; i  <  NN; i++){
    scanf("%d",&H[3*i]);
    H[3*i+1] = H[3*i]-K;
    H[3*i+2] = H[3*i]+K;
    idx[3*i] = 3*i;
    idx[3*i+1] = 3*i+1;
    idx[3*i+2] = 3*i+2;
  }
  sort_a2(H,idx,3*NN);
  for(i = j = 0; i  <  3*NN; i++){
    if(i && H[i] != H[i-1])
      j++;
    rH[idx[i]] = j;
  }
  scanf("%d",&Q);
  for(i = 0; i < Q; i++){
    scanf("%d%d",&q[0][i],&q[1][i]);
    q[1][i]++;
  }
  for(i = 0, j = (int)sqrt(NN); i  <  Q; i++){
    qq[0][i] = q[0][i]/j;
    qq[1][i] = q[1][i];
    idx[i] = i;
  }
  sort_a3(&qq[0][0],&qq[1][0],idx,Q);
  for(i = cl = cr = 0, x= 0; i  <  Q; i++){
    QQ(q[0][idx[i]],q[1][idx[i]]);
    ans[idx[i]]=x;
  }
  for(i = 0; i  <  Q; i++)
    printf("%lld\n",ans[i]);
  return 0;
}
void QQ(int x,int y){
  while(cl < x)
    removee(cl++>;
  while(cl>x)
    add(--cl);
  while(cr < y)
    add(cr++);
  while(cr>y)
    removee(--cr);
  return;
}
void add(int X){
  int y = read(rH[3*X+2]+1);
  if(rH[3*X+1])
    y-=read(rH[3*X+1]);
  x+=y;
  update(rH[3*X]+1,1,3*NN);
  return;
}
void removee(int X){
  int y=read(rH[3*X+2]+1);
  if(rH[3*X+1])
    y-=read(rH[3*X+1]);
  x-=y-1;
  update(rH[3*X]+1,-1,3*NN);
  return;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a = (int*)malloc(m*sizeof(int));
  right_a = (int*)malloc((size-m)*sizeof(int));
  left_b = (int*)malloc(m*sizeof(int));
  right_b = (int*)malloc((size-m)*sizeof(int));
  for(i = 0; i  <  m; i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i = 0; i  <  size-m; i++){
    right_a[i] = a[i+m];
    right_b[i] = b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size){
  int i = 0, j = 0;
  while (i  <  left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i]  < = right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}
void sort_a3(int*a,int*b,int*c,int size){
  if (size  <  2)
    return;
  int m = (size+1)/2,i;
  int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
  left_a = (int*)malloc(m*sizeof(int));
  right_a = (int*)malloc((size-m)*sizeof(int));
  left_b = (int*)malloc(m*sizeof(int));
  right_b = (int*)malloc((size-m)*sizeof(int));
  left_c = (int*)malloc(m*sizeof(int));
  right_c = (int*)malloc((size-m)*sizeof(int));
  for(i = 0; i  <  m; i++){
    left_a[i] = a[i];
    left_b[i] = b[i];
    left_c[i] = c[i];
  }
  for(i = 0; i  <  size-m; i++){
    right_a[i] = a[i+m];
    right_b[i] = b[i+m];
    right_c[i] = c[i+m];
  }
  sort_a3(left_a,left_b,left_c,m);
  sort_a3(right_a,right_b,right_c,size-m);
  merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  free(left_c);
  free(right_c);
  return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
  int i = 0, j = 0;
  while (i  <  left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else if (left_a[i] == right_a[j]) {
      if(left_b[i] < =right_b[j]){
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
      }
      else{
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
      }
    } else if (left_a[i]  <  right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    }
  }
  return;
}
int read(int idx>{
  int sum = 0;
  while(idx>0){
    sum+=tree[idx];
    idx-=(idx&-idx);
  }
  return sum;
}
void update(int idx,int val,int MaxVal){
  while(idx < =MaxVal){
    tree[idx]+=val;
    idx+=(idx&-idx);
  }
  return;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
#define rep(i, s, n) for(int i=int(s); i < =int(n); ++i)
#define rf freopen("in.in", "r", stdin)
#define wf freopen("out.out", "w", stdout)
using namespace std;
#define mp make_pair
#define ll long long
const int mx=1e5+10;

#define gc getchar_unlocked
void scan(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c < 48 || c>57);c = gc());
    for(;c>47 && c < 58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}

static ll b2d[410][410], b1d[mx][410];
static int h[mx], szb[410], lb[410], rb[410];
pair < int, int> bb[410], *buck[410];
int n, k, q, sqr;

inline void cum2d()
{
    rep(i, 1, 409) rep(j, 1, 409)
        b2d[i][j] += b2d[i-1][j]+b2d[i][j-1]-b2d[i-1][j-1];
}
inline void cum1d()
{
    rep(i, 0, n) rep(j, 1, 409)
        b1d[i][j] += b1d[i][j-1];
}

inline ll inonev(int* v, int sz)
{
    if(sz <= 0) return 0;

    ll ret = 0; int up=0;
    rep(i, 0, sz-1)
    {
        while(v[up]  < = v[i]+k and up;
        buck[i+1]=new pair < int, int>[e-s+1]; szb[i+1]=e-s+1;
        
        rep(j, s, e)
            buck[i+1][j-s] = mp(h[j], j),
            lb[j-s] = h[j];
        sort(lb, lb+szb[i+1]);
        sort(buck[i+1], buck[i+1]+szb[i+1]);

        ll val=inonev(lb, szb[i+1]);
        b2d[i+1][i+1] += val;

        rep(j, 1, i)
        {
            val=0; int up=0, low=0;
            rep(l, 0, szb[i+1]-1)
            {
                while(buck[j][low].first  <  buck[i+1][l].first-k and low=l and buck[sqrl][i].second<=r)
                lb[szl++]=buck[sqrl][i].first;
        rep(i, 0, szb[sqrr+1]-1>
            if(buck[sqrr+1][i].second>=l and buck[sqrr+1][i].second<=r)
                rb[szr++]=buck[sqrr+1][i].first;

        ans+=inonev(lb, szl); 
        if(sqrr+1==sqrl) {printf("%lld\n", ans); continue;}
        ans+=inonev(rb, szr);

        ans += intwov(lb, szl, rb, szr);
        ans += b2d[sqrr][sqrr]-b2d[sqrr][sqrl]-b2d[sqrl][sqrr]+b2d[sqrl][sqrl];

        rep(i, l, sqr*sqrl-1)
            ans += b1d[i][sqrr]-b1d[i][sqrl];
        rep(i, sqr*sqrr, r)
            ans += b1d[i][sqrr]-b1d[i][sqrl];

        printf("%lld\n", ans>;
    }
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;

public class Solution {

  static int nn;
  static int block;
  static int[] fenwick;
  static long cnt = 0;

  static class B implements Comparable < B> {
    int l;
    int r;
    int id;
    
    @Override
    public int compareTo(B o) {
      int i = l/block;
      int j = o.l/block;
      if (i != j) {
        return i - j;
      }
      if (r != o.r) {
        return r - o.r;
      }
      return l - o.l;
    }
  }
  
  static int getSum(int x) {
    int s = 0;
    for (; x != 0; x &= x-1)
      s += fenwick[x-1];
    return s;
  }

  static class Node {
    int l;
    int r;
    int h;

    public Node(int l, int r, int h) {
      this.l = l;
      this.r = r;
      this.h = h;
    }

    void remove() {
      add(h, -1);
      cnt -= getSum(r) - getSum(l);
    }

    void add() {
      cnt += getSum(r) - getSum(l);
      add(h, 1);
    }

    void add(int x, int v) {
      for (; x  <  nn; x |= x+1)
        fenwick[x] += v;
    }
  }

    
  static public int lowerBound(int[] arr, int len, int key) {
    if (key  < = arr[0]) {
      return 0;
    }
    if (key > arr[len - 1]) {
      return 0;
    }
    
    int index = Arrays.binarySearch(arr, 0, len, key);
    if (index  <  0) {
      index = - index - 1;
      if (index < 0) {
        return 0;
      }
    } 
    return index;
  }
  
  static public int upperBound(int[] arr, int len, int key) {
    int index = Arrays.binarySearch(arr, 0, len, key+1);
    if (index  <  0) {
      index = - index - 1;
      if (index < 0 || index > len) {
        return 0;
      }
    }
    return index;
  }
  
  public static int unique(int[] arr) {
    if (arr.length == 1) return 1;
    int len = 1;
    while (len  <  arr.length && arr[len] != arr[len-1]) { 
      len++;
    }
    for (int i = len + 1; i  <  arr.length; i++) {
      if (arr[i] != arr[len - 1]) {
        len++;
        arr[len - 1] = arr[i];
      }
    }
    return len;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    int[] a = new int[n];
    int[] c = new int[n];
    for (int i = 0; i  <  n; i++) {
      int item = Integer.parseInt(st.nextToken());
      c[i] = a[i] = item;
    }
    Arrays.sort(c);
    nn = unique(c);
    
    Node[] nodes = new Node[n];
    for (int i = 0; i  <  n; i++) {
      int l = lowerBound(c, nn, a[i]-k);
      int r = upperBound(c, nn, a[i]+k);
      int h = lowerBound(c, nn, a[i]);
      nodes[i] = new Node(l, r, h);
    }
    
    st = new StringTokenizer(br.readLine());
    int q = Integer.parseInt(st.nextToken());
    
    B[] b = new B[q];
    block = (int) Math.max(1.0, Math.sqrt((double)(n)*n/Math.max(1, q)));
    for (int i = 0; i  <  q; i++) {
      st = new StringTokenizer(br.readLine());
      b[i] = new B();
      b[i].id = i;
      b[i].l = Integer.parseInt(st.nextToken());
      b[i].r = Integer.parseInt(st.nextToken()) + 1;
    }
    Arrays.sort(b);
    int l = 0;
    int r = 0;
    fenwick = new int[n];
    long[] result = new long[q];
    for (int i = 0; i  <  q; i++) {
      while (l < b[i].l) {
        nodes[l++].remove();
      }
      while (b[i].l  <  l) {
        nodes[--l].add();
      }
      while (b[i].r < r) {
        nodes[--r].remove();
      }
      while (r  <  b[i].r) {
        nodes[r++].add();
      }
      result[b[i].id] = cnt;
    }

    for (int i = 0; i  <  result.length; i++) {
      bw.write(String.valueOf(result[i]));

      if (i != result.length - 1) {
        bw.write("\n");
      }
    }

    bw.newLine();

    bw.close();
    br.close();
  }
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Starfleet solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Burger Happiness solution in Hackerrank - Hacerrank solution C, C++, java,js, Python