Algorithm


Problem Name: Data Structures - Costly Intervals

Problem Link: https://www.hackerrank.com/challenges/costly-intervals/problem?isFullScreen=true

In this HackerRank in Data Structures - Costly Intervals solutions

Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least k.

Specifically, let A = [A1,A2, ... , An] be an array of length n and let Al...r = [Al, ...... , Ar] be the subarray from index l to index r. Also,

  • Let MAX(l,r) be the largest number in Al...r
  • Let MIN(l,r) be the smallest number in Al...r.
  • Let OR(l,r) be the bitwise OR of the elements of Al...r.
  • Let AND(l,r) be the bitwise AND of the elements of Al...r.

The cost of Al...r, denoted cost(l,r) is defined as

cost(l,r)  = (OR(l,r) - AND(l,r)) - (MAX(l,r) - MIN(l,r))

The size of Al...r is defined as r - l + r.

You are given the array A and and an integer k. For each index i from 1 to n , your goal is to find the largest size of any subarray Al...r such that 1 <= l <= i <= r <= n and  cost(l,r) >= k.

Consider, array A = [2,4,3,1,7] and k = 6 The possible sub-arrays and their costs would be as follows:

image

Complete the function costlyIntervals which takes two integers n and k as first line of input, and array A1,A2 , ...., An in the second line of input. Return an array of n integers, where the i**th element contains the answer for index i of the input array, 1 <= i <= n. Every element of the output array denotes the largest size of a subarray containing i whose cost is at least k, or - 1 if there is no such subarray.

Constraints

  • 1 <= n <= 10**5
  • 0 <= Ai <= 10**9
  • 0 <= k <= 10**9

Subtasks

  • For 5% of the maximum score, n <= 100
  • For 15% of the maximum score, n <= 5 * 10**3

Sample Input

n = 5, k = 6

A = [2,4,3,1,7]

Sample Output

[-1,2,2, -1, -1]

Explanation

In this example, we have k = 6. There is only one subarray whose cost is at least 6 ,and that is A(2-3) = [4,3] , since cost[2,3] = 6.  Its size is 2. Thus, for i = 2 and i = 3, the answer is 2, and for the others, -1.

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#define INF 200000
int get(int l,int r);
int max(int x,int y);
int min(int x,int y);
void init( int n );
void range_increment( int i, int j, int val );
int query( int i );
void sort_a(int*a,int size,int*new_size);
void merge(int*a,int*left,int*right,int left_size, int right_size,int*new_size);
int N,a[100000],b[100000],map[100001],dp[4][100000][18],dp1[30][100000],dp2[30][100000],tree[400000];

int main(){
  int n,k,s,ns,h,l,m,i,j;
  scanf("%d%d",&n,&k);
  for(i=j=1,map[0]=0;i < =100000;i++)
    if(j*2<=i){
      j*=2;
      map[i]=map[i-1]+1;
    }
    else
      map[i]=map[i-1];
  for(i=0;i < n;i++)
    scanf("%d",a+i);
  for(i=0;i < n;i++)
    dp[0][i][0]=dp[1][i][0]=dp[2][i][0]=dp[3][i][0]=a[i];
  for(j=1;1<<j < =n;j++)
    for(i=0;i+(1<<j)-1 < n;i++){
      dp[0][i][j]=max(dp[0][i][j-1],dp[0][i+(1<<(j-1))][j-1]);
      dp[1][i][j]=min(dp[1][i][j-1],dp[1][i+(1<<(j-1))][j-1]);
      dp[2][i][j]=dp[2][i][j-1]|dp[2][i+(1<<(j-1))][j-1];
      dp[3][i][j]=dp[3][i][j-1]&dp[3][i+(1<<(j-1))][j-1];
    }
  for(i=0;i < n;i++)
    for(j=0;j < 30;j++)
      if(a[i]&(1<<j)>{
        dp1[j][i]=i;
        dp2[j][i]=INF;
      }
      else{
        dp1[j][i]=INF;
        dp2[j][i]=i;
      }
  for(i=n-2;i>=0;i--)
    for(j=0;j < 30;j++){
      dp1[j][i]=min(dp1[j][i],dp1[j][i+1]);
      dp2[j][i]=min(dp2[j][i],dp2[j][i+1]);
    }
  init(n);
  for(i=0;i < n;i++){
    for(j=s=0;j < 30;j++){
      if(dp1[j][i]!=INF)
        b[s++]=dp1[j][i];
      if(dp2[j][i]!=INF)
        b[s++]=dp2[j][i];
    }
    sort_a(b,s,&ns);
    for(j=ns-1;j>=0;j--)
      if(get(i,b[j])>=k){
        if(j==ns-1)
          h=n-1;
        else
          h=b[j+1]-1;
        l=s=b[j];
        while(l<=h){
          m=(h+l)/2;
          if(get(i,m>>=k){
            s=m;
            l=m+1;
          }
          else
            h=m-1;
        }
        range_increment(i,s,s-i+1);
        break;
      }
  }
  for(i=0;i < n;i++)
    printf("%d\n",query(i));
  return 0;
}
int get(int l,int r){
  int a,b,c,d,len;
  len=map[r-l+1];
  a=max(dp[0][l][len],dp[0][r-(1<<len)+1][len]);
  b=min(dp[1][l][len],dp[1][r-(1<<len)+1][len]);
  c=dp[2][l][len]|dp[2][r-(1<<len)+1][len];
  d=dp[3][l][len]&dp[3][r-(1<<len)+1][len];
  return c-d-a+b;
}
int max(int x,int y){
  return (x>y)?x:y;
}
int min(int x,int y){
  return (x < y)?x:y;
}
void init( int n )
{
  N = 1;
  while( N  <  n ) N *= 2;
  int i;
  for( i = 1; i  <  N + n; i++ ) tree[i] = -1;
}
void range_increment( int i, int j, int val )
{
  for( i += N, j += N; i  < = j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
  {
    if( i % 2 == 1 ) tree[i] = max(val,tree[i]);
    if( j % 2 == 0 ) tree[j] = max(val,tree[j]);
  }
}
int query( int i )
{
  int ans = -1,j;
  for( j = i + N; j; j /= 2 ) ans = max(tree[j],ans);
  return ans;
}
void sort_a(int*a,int size,int*new_size){
  if (size < 2){
    (*new_size)=size;
    return;
  }
  int m = (size+1)/2,i;
  int *left,*right;
  left=(int*)malloc(m*sizeof(int));
  right=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i < m;i++)
    left[i]=a[i];
  for(i=0;i < size-m;i++)
    right[i]=a[i+m];
  int new_l_size=0,new_r_size=0;
  sort_a(left,m,&new_l_size);
  sort_a(right,size-m,&new_r_size);
  merge(a,left,right,new_l_size,new_r_size,new_size);
  free(left);
  free(right);
  return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size,int*new_size){
  int i = 0, j = 0,index=0;
  while (i  <  left_size|| j < right_size) {
    if (i == left_size) {
      a[index++] = right[j];
      j++;
    } else if (j == right_size) {
      a[index++] = left[i];
      i++;
    } else if (left[i]  < = right[j]> {
      a[index++] = left[i];
      i++;
    } else {
      a[index++] = right[j];
      j++;
    }
    if(index>1&&a[index-2]==a[index-1])
      index--;
  }
  (*new_size)=index;
  return;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
using namespace std;

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i  <  (b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define pconent(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int> pi;
typedef vector<int> vi;
typedef vector < pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template < class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val))  <  0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x  <  -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

template < class T> struct RMQOR {
    int n;
    vector<T> a;
    vector < vector<T> > f;

    T best(T a, T b) {
        return a | b;
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p)  <  n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i  <  (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i  <  n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l)  <  n; l++) {
            for (int i = 0; i + k  <  n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
RMQOR < long long> rmq_or;
template struct RMQAND {
    int n;
    vector < T> a;
    vector<vector<T> > f;

    T best(T a, T b) {
        return a & b;
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p)  <  n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i  <  (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i  <  n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l)  <  n; l++) {
            for (int i = 0; i + k  <  n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
RMQAND < long long> rmq_and;
template > struct RMQ2 {
    int n;
    vector < T> a;
    vector<vector<T> > f;

    T best(T a, T b) {
        if (cmp()(a, b)) return a;
        return b;
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p)  <  n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i  <  (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i  <  n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l)  <  n; l++) {
            for (int i = 0; i + k  <  n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
RMQ2 < int> rmq_min;
RMQ2<int, greater<int> > rmq_max;

const int maxn = 1e5 + 5;
const int logn = 31;
int n, k;
int a[maxn];
int nxt0[maxn][logn];
int nxt1[maxn][logn];

void solve() {
    cin >> n >> k;
    rmq_or.init(n);
    rmq_and.init(n);
    rmq_min.init(n);
    rmq_max.init(n);
    FOR(i, 0, n) {
        cin >> a[i];
        rmq_or.upd(i, a[i]);
        rmq_and.upd(i, a[i]);
        rmq_min.upd(i, a[i]);
        rmq_max.upd(i, a[i]);
    }
    rmq_or.build();
    rmq_and.build();
    rmq_min.build();
    rmq_max.build();
    static int lst0[logn];
    static int lst1[logn];
    fill_n(lst0, logn, n);
    fill_n(lst1, logn, n);
    FORd(i, n, 0) {
        FOR(j, 0, logn) {
            if (!bit(a[i], j)) {
                lst0[j] = i;
            }
            else {
                lst1[j] = i;
            }
        }
        FOR(j, 0, logn) nxt0[i][j] = lst0[j];
        FOR(j, 0, logn) nxt1[i][j] = lst1[j];
    }
    vector < pi> events;
    FOR(i, 0, n) {
        int mx = -1;
        long long cost = 0, sor = a[i], sand = a[i];
        int ptr = i;
        if (cost >= k) {
            mx = i;
        }
        while (ptr  <  n - 1) {
            int nptr = n;
            FOR(j, 0, logn) {
                if (bit(sand, j)) {
                    chkmin(nptr, nxt0[ptr + 1][j]);
                }
                if (!bit(sor, j)) {
                    chkmin(nptr, nxt1[ptr + 1][j]);
                }
            }
            int lo = ptr, hi = nptr - 1;
            while (lo  <  hi) {
                int mi = lo + hi + 1 >> 1;
                if (rmq_or.query(i, mi) - rmq_and.query(i, mi) - rmq_max.query(i, mi) + rmq_min.query(i, mi) >= k) {
                    lo = mi;
                }
                else {
                    hi = mi - 1;
                }
            }
            int mi = lo + hi >> 1;
            if (rmq_or.query(i, mi) - rmq_and.query(i, mi) - rmq_max.query(i, mi) + rmq_min.query(i, mi) >= k) {
                mx = mi;
            }
            if (nptr == n) {
                break;
            }
            ptr = nptr;
            sor = rmq_or.query(i, ptr);
            sand = rmq_and.query(i, ptr);
        }
        if (~mx) {
            int len = mx - i + 1;
            events.pb(mp(i, len));
            events.pb(mp(mx + 1, -len));
        }
    }
    sort(all(events));
    multiset < int> heap;
    int ptr = 0;
    FOR(i, 0, n) {
        while (ptr  <  sz(events) && events[ptr].fi <= i) {
            int x = events[ptr].se;
            if (x > 0) {
                heap.insert(x);
            }
            else {
                heap.erase(heap.find(-x));
            }
            ptr++;
        }
        cout << (sz(heap) ? *heap.rbegin() : -1) << "\n";
    }
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    solve();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    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 class Node {
    int x;
    long code;
    public Node(int x, long code) {
      this.x = x;
      this.code = code;
    }
  }
  
  public static int[][] build(int[] a) {
    int n = a.length;
    int b = 32 - Integer.numberOfLeadingZeros(n);
    int[][] ret = new int[b][];
    for (int i = 0, l = 1; i  <  b; i++, l *= 2) {
      if (i == 0) {
        ret[i] = a;
      } else {
        ret[i] = new int[n - l + 1];
        for (int j = 0; j  <  n - l + 1; j++) {
          ret[i][j] = Math.min(ret[i - 1][j], ret[i - 1][j + l / 2]);
        }
      }
    }
    return ret;
  }

  public static int rmq(int[][] or, int l, int r) {
    assert l  < = r;
    if (l >= r)
      return Integer.MAX_VALUE;
    int t = 31 - Integer.numberOfLeadingZeros(r - l);
    return Math.min(or[t][l], or[t][r - (1 << t)]);
  }

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

    int[] a = new int[n];
    int[] ra = new int[n];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i  <  n; i++) {
      int item = Integer.parseInt(st.nextToken());
      a[i] = item;
      ra[i] = -a[i];
    }

    int[][] stmin = build(a);
    int[][] stmax = build(ra);

    Node[] efs = new Node[80 * n];
    int efp = 0;

    int[][] oas = new int[0][];
    for (int i = n - 1; i >= 0; i--) {
      int[][] noas = new int[40][];
      int p = 0;
      for (int j = 0; j  <  oas.length; j++) {
        oas[j][0] |= a[i];
        oas[j][1] &= a[i];
        if (p > 0 && noas[p - 1][0] == oas[j][0] && noas[p - 1][1] == oas[j][1]) {
          noas[p - 1][2] = oas[j][2];
        } else {
          noas[p++] = oas[j];
        }
      }
      if (!(p > 0 && noas[p - 1][0] == a[i] && noas[p - 1][1] == a[i])) {
        noas[p++] = new int[] { a[i], a[i], i };
      } else {
        noas[p - 1][2] = i;
      }
      oas = Arrays.copyOf(noas, p);

      int to = n;
      for (int[] oa : oas) {
        int cha = oa[0] - oa[1];
        int low = oa[2] - 1, high = to;
        while (high - low > 1) {
          int h = high + low >> 1;
          if (cha - (-rmq(stmax, i, h + 1) - rmq(stmin, i, h + 1)) >= k) {
            low = h;
          } else {
            high = h;
          }
        }
        if (low >= oa[2]) {
          efs[efp++] = new Node(i, (long) (low - i + 1) << 32 | i);
          efs[efp++] = new Node(low + 1, (long) (low - i + 1) << 32 | i);
        }
        to = oa[2];
      }
    }

    Arrays.sort(efs, 0, efp, (efsa, efsb) -> { return efsa.x - efsb.x;  });

    TreeSet < Long> set = new TreeSet<>();

    int q = 0;
    for (int i = 0; i  <  n; i++) {
      int result = -1;
      while (q  <  efp && efs[q].x <= i) {
        long code = efs[q].code;
        if (set.contains(code)) {
          set.remove(code);
        } else {
          set.add(code);
        }
        q++;
      }
      if (!set.isEmpty()) {
        result = Math.max(result, (int) (set.last() >>> 32));
      }
      bw.write(result + "\n");
    }

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

Demonstration


Previous
[Solved] Counting On a Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] The Strange Function solution in Hackerrank - Hacerrank solution C, C++, java,js, Python