CHEFARRB - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Misha Chorniy
Tester: Tuan Anh Tran Dang
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Tuan Anh Tran Dang

DIFFICULTY

EASY

PREREQUISITE

NONE

PROBLEM

Given an array of N integer. Calculate how many contiguos sub-array that have the OR-sum larger or equal to K.

SOLUTION

For each position i we will find the smallest j ≥ i such that the OR-sum of A[i…j] larger than or equal to K then we would know that there is N - j + 1 valid sub-array starting at i. Notice that with i fixed OR-sum of A[i…j] increses when j increases (OR-sum increases when we add more numbers). With that we can use binary search with each i to find j If we can calculate OR-sum of A[i…j] efficiently (one way to calculate OR-sum of any A[i…j] is building the segment tree).

The mentioned solution seems to be overkill with this easy problem not to say that it doesn’t give the best run time. We can avoid binary search and use the two pointer technique where one pointer is the position of i and the other one is j. With each i we try to increase j until we got the OR-sum of A[i…j] larger than or equal to K. The OR-sum between i and j can be maintained by keeping the number of bit 1 at each position among all numbers in the sub-array A[i…j]. Basically we maintain an array cnt[0…31] where cnt[i] is the the numbers of numbers in A[i…j] that hava 1 at the ith bit.

All we do is increase i or j, update the cnt[] array and calculate the OR-sum. Update the cnt[] or calculate OR-sum from cnt[] both take O(32) (which is corresponding to the number of bits the max value of A[i]). So the total complexity would be O(N×log(max A[i])).

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

2

@admin setter and tester solution is not visible. Can you please explain this line : “The OR-sum between i and j can be maintained by keeping the number of bit 1 at each position among all numbers in the sub-array A[i…j].” ?

3

in the line “cnt[i] is the the numbers of numbers in A[i…j] that hava 1 at the ith bit.” , use of i seems ambiguos.

4

if any number in A[i…j] has a set bit at position k then OR-sum of this subarray will have kth bit set, so by maintaining the number of 1s at each position for any subarray using cnt array as mentioned above you can calculate the OR-sum. You can look at this solution https://www.codechef.com/viewsolution/12301785 that I wrote after competition

5

@yougaindra

What do you feel is the ambiguity. Did you understand the logic. You need help in understanding logic or implementation.

6

I did using a sparse table of almost similar complexity O(n log n ) ,

Code in Python : https://www.codechef.com/viewsolution/12299242

7

Can be done using segment tree and binary search in O(nlognlogn). For every position i, we can binary search the minimum index greater than i for which the subarray [i,index] have OR value greater than K. For finding out OR values of different segments, we can use seg trees.
Code: https://www.codechef.com/viewsolution/12298985

8

The segment tree approach is O(nlognlogn) which really seemed a overkill.

9

I am not able to understand the cnt[] part. How to update it, what is it. Can anybody explain?

10

I tried to do it using segment trees but i’m missing out somewhere, can anybody help?
http://ideone.com/OEiuJF here is the code

11

can anyone tell me what is wrong with this solution i am using sliding window technique
it passes all given test cases
https://www.codechef.com/viewsolution/12302833

12

@arpit728 I understood the logic and have already solved the problem. The statement is ambiguos because i represent two different things in that line i.e. i represents starting point of subarray A[i…j] and also it presents the position of bit in cnt[i].

13

Can anyone please tell, that for each number in the array how can I find efficiently which are the set bits(1) in the binary representation of that number , so that we can store 1 in those positions of the cnt[] array.

P.S. I’m a not quite used to bit manipulation in problems :slight_smile:

14

Please elaborate…

15

cnt part:

cnt[N][32]//for each index one cnt array of 32 size

first, mark which bits are present in cnt[i];

and then get cumulative sum.

now you want whether subarray [i…j] has or value greater than k

simple subtract bitwise cnt[j]-cnt[i-1]

now check it has the value greater than k or not.

16

you can refer this solution…

https://www.codechef.com/viewsolution/12936619

let me know if any part you didn’t understand!!

17

It could be done using 2 pointer concept and segment tree in O(n log n). here is the code https://www.codechef.com/viewsolution/16744917

18

can someone explain for the given example n=3,k=3
and value are 1,2,3 the output is 4 but i am getting sub arrays as 5 i.e.,
(1,2),(1,3),(2,3),(1,2,3),(3)=5