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

×

CHEFARRB - Editorial

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

asked 18 Dec '16, 23:05

tuananh93's gravatar image

5★tuananh93
116613
accept rate: 0%

edited 19 Dec '16, 00:52

admin's gravatar image

0★admin ♦♦
19.8k350498541


@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]." ?

link

answered 19 Dec '16, 01:12

rohit_0801's gravatar image

5★rohit_0801
3049
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) yougaindra2★

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.

link

answered 19 Dec '16, 02:24

yougaindra's gravatar image

2★yougaindra
913
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) yougaindra2★

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

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

link

answered 19 Dec '16, 09:25

geek_geek's gravatar image

4★geek_geek
43914
accept rate: 16%

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

link

answered 19 Dec '16, 10:23

arvindnair's gravatar image

5★arvindnair
112
accept rate: 0%

edited 19 Dec '16, 14:31

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

link

answered 19 Dec '16, 12:01

prayas_sahni's gravatar image

1★prayas_sahni
311
accept rate: 0%

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

link

answered 19 Dec '16, 12:39

harshit23897's gravatar image

4★harshit23897
32
accept rate: 0%

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.

(26 Feb '17, 00:13) rcsldav20175★

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

link

answered 19 Dec '16, 12:53

utsavgoel's gravatar image

2★utsavgoel
412
accept rate: 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

link

answered 19 Dec '16, 13:35

manish_97's gravatar image

3★manish_97
1
accept rate: 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 :)

link

answered 21 Dec '16, 08:36

jaideeppyne's gravatar image

5★jaideeppyne
2616
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) rcsldav20175★

Please elaborate...

link

answered 21 Dec '16, 19:52

yprac's gravatar image

4★yprac
1
accept rate: 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

ganeshjadhav's gravatar image

3★ganeshjadhav
0
accept rate: 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

link

answered 19 May '18, 12:46

girish151's gravatar image

4★girish151
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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