You are not logged in. Please login at www.codechef.com to post your questions!

×

# CHEFARRB - Editorial

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

EASY

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:

asked 18 Dec '16, 23:05 116613
accept rate: 0% 19.8k350498541

 0 @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]." ? answered 19 Dec '16, 01:12 304●9 accept rate: 10% 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 (19 Dec '16, 02:29)
 0 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. answered 19 Dec '16, 02:24 91●3 accept rate: 0% @yougaindra What do you feel is the ambiguity. Did you understand the logic. You need help in understanding logic or implementation. (19 Dec '16, 09:02) arpit7281★ @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]. (19 Dec '16, 14:47)
 0 I did using a sparse table of almost similar complexity O(n log n ) , Code in Python : https://www.codechef.com/viewsolution/12299242 answered 19 Dec '16, 09:25 439●14 accept rate: 16%
 0 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 answered 19 Dec '16, 10:23 11●2 accept rate: 0%
 0 The segment tree approach is O(nlognlogn) which really seemed a overkill. answered 19 Dec '16, 12:01 31●1 accept rate: 0%
 0 I am not able to understand the cnt[] part. How to update it, what is it. Can anybody explain? answered 19 Dec '16, 12:39 3●2 accept rate: 0% cnt part: cnt[N]//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. (26 Feb '17, 00:13)
 0 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 answered 19 Dec '16, 12:53 41●2 accept rate: 0%
 0 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 answered 19 Dec '16, 13:35 1 accept rate: 0%
 0 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 :) answered 21 Dec '16, 08:36 261●6 accept rate: 3% you can refer this solution.. https://www.codechef.com/viewsolution/12936619 let me know if any part you didn't understand!! (26 Feb '17, 00:16)
 0 Please elaborate... answered 21 Dec '16, 19:52 4★yprac 1 accept rate: 0%
 0 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 link This answer is marked "community wiki". answered 03 Jan '18, 22:11 0 accept rate: 0%
 0 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 answered 19 May '18, 12:46 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×184
×43
×36
×3

question asked: 18 Dec '16, 23:05

question was seen: 3,729 times

last updated: 19 May '18, 12:46