Problem Name: Minion AND Range; Problem Code: MINIAND

general
1

I was trying to solve the problem, which deals with executing Q queries on a sequence of +ve numbers, and each query is of type [L, R], where I need to find whether bitwise-AND of A[L\ldots R] will be EVEN or ODD.
The solution which I implemented gives TLE.
How can I optimise the solution for an AC, and as it is query problem, either you do some pre-computation in order to find the answer to queries in constant time or use a data-structure to answer the query in less than O(n) time as the query is related to ranges.

Problem Link: CodeChef: Practical coding for everyone

As I have already seen some of the submission, and I can only understand the most of them have used prefix sum method, so please don’t only give me the source-code, I really appreciate it, if someone can explain the logic in plain English or can provide a well-documented code.

@tds115 @ssjgz @hitch_hiker42

Thanks for reading.
Peace :v:

1 Like
2

Just check if an even number exists inbetween by prefix sums.

1 Like
3

You can use a prefix array to count the parity, but i simply used a segment tree :stuck_out_tongue:

I know it’s too much😂but i had the template ready… Segment Tree won’t let u down if u implement it correctly

4

@just1star Can you tell me how to use prefix array, I know prefix array but in this problem context, how to use it, Do I need to store the count of even numbers upto a[i]?

@anon73162591 Segment tree is one of the option which will comes first in mind when dealing with range queries, How did you use the segment tree?

Thanks for reading.
Peace :v:

5

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

6

The problem involves checking whether a range of elements has a bitwise and (&)= even or not. we know that :
even & even=even
even & odd=even
odd & odd = odd
now we know that even a single occurance of a even number will make the whole array (or range)even.
now the task is to find if ranges contain or not a even number for this we can use a prefix array and store the number of even number till each index.
atlast check for if even[r]-even[r]!=0 then even else false.
we can use an prefix array for same

3 Likes
7

I made a segment tree to return me the bitwise AND between ranges… I just took that and checked if it was even or odd…

8

Solved the problem, here is my Solution, thanks for valuable suggestions.

Peace :v: