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