Costly Intervals


Problem Statement :


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

The size of Al . . .r is defined as r - l +1.
You are given the array  and and an integer . For each index  from  to , your goal is to find the largest size of any subarray  such that  and .

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 ith 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.


Solution :



title-img


                            Solution in C :

In C++ :






#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Inf = 1000000007;
const int Maxn = 100005;
const int Maxm = 20;
const int Maxb = 31;

int n, k;
int a[Maxn];
int mx[Maxn][Maxm], mn[Maxn][Maxm];
int nxt[Maxn][Maxb][2];
int res[Maxn];
vector <int> add[Maxn], rem[Maxn];
map <int, int> M;

int Get(int ind, int forb, int &Mn, int &Mx, int cur)
{
    int pnt = ind;
    for (int i = Maxm - 1; i >= 0; i--)
        if (pnt + (1 << i) <= forb) {
            int candmx = max(Mx, mx[pnt][i]);
            int candmn = min(Mn, mn[pnt][i]);
            if (ll(cur) - ll(candmx - candmn) >= k) {
                Mx = candmx; Mn = candmn;
                pnt += 1 << i;
            }
        }
    int res = pnt;
    for (int i = Maxm - 1; i >= 0; i--)
        if (pnt + (1 << i) <= forb) {
            Mx = max(Mx, mx[pnt][i]);
            Mn = min(Mn, mn[pnt][i]);
            pnt += 1 << i;
        }
    return res;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        mx[i][0] = mn[i][0] = a[i];   
    }
    for (int j = 1; j < Maxm; j++)
        for (int i = 1; i + (1 << j) <= n + 1; i++) {
            int nxt = i + (1 << j - 1);
            mx[i][j] = max(mx[i][j - 1], mx[nxt][j - 1]);
            mn[i][j] = min(mn[i][j - 1], mn[nxt][j - 1]);
        }
    for (int i = 0; i < Maxb; i++)
        nxt[n + 1][i][0] = nxt[n + 1][i][1] = n + 1;
    for (int i = n; i > 0; i--)
        for (int j = 0; j < Maxb; j++)
            for (int k = 0; k < 2; k++)
                if (bool(a[i] & 1 << j) == k) nxt[i][j][k] = i;
                else nxt[i][j][k] = nxt[i + 1][j][k];
    for (int i = 1; i <= n; i++) {
        int Or = a[i], And = a[i];
        int Mn = Inf, Mx = -Inf;
        int st = i;
        while (st <= n) {
            int lim = n + 1;
            for (int j = 0; j < Maxb; j++) {
                if (!(Or & 1 << j)) lim = min(lim, nxt[st + 1][j][1]);
                if (And & 1 << j) lim = min(lim, nxt[st + 1][j][0]);
            }
            int got = Get(st, lim, Mn, Mx, Or - And);
            if (got > st) {
                int cand = got - i;
                add[i].push_back(cand); rem[got].push_back(cand);
            }
            for (int j = 0; j < Maxb; j++) {
                if (!(Or & 1 << j) && lim == nxt[st + 1][j][1]) Or |= 1 << j;
                if (bool(And & 1 << j) && lim == nxt[st + 1][j][0]) And ^= 1 << j;
            }
            st = lim;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < add[i].size(); j++)
            M[add[i][j]]++;
        for (int j = 0; j < rem[i].size(); j++)
            if (--M[rem[i][j]] == 0) M.erase(rem[i][j]);
        if (!M.empty()) {
            map <int, int>::iterator it = M.end(); it--;
            printf("%d\n", it->first);
        } else printf("-1\n");
    }
    return 0;
}








In Java :





import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.TreeSet;

public class D2 {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        int n = ni(), K = ni();
        int[] a = na(n);
        
        int[] ra = new int[n];
        for(int i = 0;i < n;i++)ra[i] = -a[i];
        
        int[][] stmin = build(a);
        int[][] stmax = build(ra);
        
        int[][] efs = new int[80*n][];
        int efp = 0;
        int esp = 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);
            
//            tr(i, oas);
            
            int to = n;
            for(int[] oa : oas){
                // [oa[2], to)
                int cha = oa[0] - oa[1];
                int low = oa[2]-1, high = to;
                while(high - low > 1){
                    int h = high+low>>1;
                    // [i,h]
//                    tr(h, oa, to, cha, -rmq(stmax, i, h+1) - rmq(stmin, i, h+1));
                    if(cha - (-rmq(stmax, i, h+1) - rmq(stmin, i, h+1)) >= K){
                        low = h;
                    }else{
                        high = h;
                    }
                }
                if(low >= oa[2]){
//                    tr(i, oa, to, low);
                    efs[efp++] = new int[]{i, low - i + 1, i};
                    efs[efp++] = new int[]{low+1, low - i + 1, i};
                }
                to = oa[2];
            }
        }
        
        int I = -1;
        int[] anss = new int[n];
        Arrays.fill(anss, I);
        
        Arrays.sort(efs, 0, efp, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        TreeSet<Long> set = new TreeSet<Long>();
        
        int q = 0;
        for(int i = 0;i < n;i++){
            while(q < efp && efs[q][0] <= i){
                long code = (long)efs[q][1]<<32|efs[q][2];
                if(set.contains(code)){
                    set.remove(code);
                }else{
                    set.add(code);
                }
                q++;
            }
            if(!set.isEmpty()){
                Long first = set.last();
                anss[i] = Math.max(anss[i], (int)(first>>>32));
            }
        }
        
        for(int v : anss){
            out.println(v);
        }
    }
    
    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;
    }
    
    // [a,b)
    public static int rmq(int[][] or, int l, int r)
    {
        assert l <= r;
        if(l >= r)return Integer.MAX_VALUE;
        // 1:0, 2:1, 3:1, 4:2, 5:2, 6:2, 7:2, 8:3
        int t = 31-Integer.numberOfLeadingZeros(r-l);
        return Math.min(or[t][l], or[t][r-(1<<t)]);
    }

    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new D2().run(); }
    
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}








In C :






#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;
}








In Python3 :




import sys
def cost(a):
    x = 0
    y = 1
    for i in a:
        x |= i
        y &= i
    return((x-y)-(max(a)-min(a)))
    
def costlyIntervals(n, k, A):
    ans = []
    for m in range(n):
        cs = -1
        for i in range(0,n-1):
            for j in range(i,n):
                l = A[i:j+1]
                if A[m] in l:
                    x = cost(l)
                    if x >= k:
                        cs = max(cs,len(l))
        ans.append(cs)
    return(ans)
                        
    
    

if __name__ == "__main__":
    n, k = input().strip().split(' ')
    n, k = [int(n), int(k)]
    A = list(map(int, input().strip().split(' ')))
    result = costlyIntervals(n, k, A)
    print ("\n".join(map(str, result)))
                        




View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →