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

×

ANDSQR - Editorial

8
7

PROBLEM LINK:

Div1
Div2
Practice

Setter- ShavelV
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey

DIFFICULTY:

MEDIUM

PRE-REQUISITES:

Fenwick Tree supporting range updates and range query, or segment tree with lazy propagation, Properties of AND, Observations

PROBLEM:

Given an array $A$, answer $Q$ queries which ask the number of subsequences in range $[L,R]$ whose bitwise AND is a perfect square.

QUICK-EXPLANATION:

Key to AC- AND of numbers can change no more than $LogN$ time, and hence there are at most $O(NLogN)$ different values possible. It is hence possible to update answer over a group or range, which can be done via segment tree or fenwick tree.

Notice that there are at most $O(NLogN)$ values of AND possible in total. Now, either of the $2$ approaches are possible-

  • Most Popular Solution- Pre-process the location of different $LogN$ AND values you can obtain from index $i$, or preprocess the distance upto which $j'th$ bit of $A_i$ remains same. Both of these can be used for next step, where, while operating over a element, we determine the groups with which the AND gives perfect square. Range update the corresponding interval, and for answering, we can use range sum query. We need to sort the queries for this approach.
  • Setter's Solution- Store the queries in an array of vector. $Query[r]$ will store all queries ending at index $r$, along with index of query in original order. The next step can be summarized in $2$ words. Maintain groups. Store the pair $\{GroupValueOfAND,i\}$ in a vector and update this vector every iteration. If $2$ groups get same $AND$ value then merge them. We can see that we can reduce this to range updates and range queries on fenwick tree and/or segment tree now.

EXPLANATION:

The editorial will focus on one of the $2$ solutions, and that will be the most popular solution used by the participants - simply because the solution is pretty crisp and simple :). Setter's solution has been very briefly described in quick explanation, and setter's notes will be provided for people interested in his approach. His solution has been made commented so things are clear. We will discuss only one because difference between both solutions isnt very much, except for the fact that the participant's solution is quite intuitive and easy to understand :)

As usual, answers to all the (Why?)'s and proofs will be given in my corner - along with extra resources and related problems.

Lets run through first subtask quickly. Sine $N \le 100$, you could brute force. Take the range $[l,r]$ in input, and then iterate over all sub-arrays in this range, i.e. over all $i$ from $l$ to $r$ as starting point of subarray, and for each starting point, over $j$ from $i$ to $r$ as ending point of the sub-array. If the AND of the subarray satisfies the condition, increment the answer by $1$. This works in $O(Q*N^2)$. Lets move over to the meaty party now :D

Most Popular Solution-

Let me break this into 3 parts - Intuition, Pre-processing, and answering Queries.

1. Intuition-

This solution uses the observation that the AND value can change at most $LogN$ times. (Why? P-1). It is easy to see that AND is a non-increasing function. If we AND the current AND-sum received so far (of the sub-array) with next element, it will either remain constant or decrease.

We know that it can decrease only at most $Log_2N$ times, and if it remains constant, then we can do range operations on the group as a whole instead of doing it individually. This was the intuition a participant can pick up to at least gain a direction of how to solve this problem.

2. Pre-Processing -

Now, moving on the the most popular question, how to solve this problem :). Since total number of AND values are $NLog_2N$, we can make a $2-D$ array to store the positions of (atmost) $Log_2N$ distinct values of AND for all sub-arrays starting from index $i$. In other words, array $P[i][j]$ will store the location of $j'th$ change in AND sum for subarrays beginning at index $i$. One of the ways by which many contestants and red coders did it was, by checking the location when the $j'th$ bit changed. If $j'th$ bit remains constant, then we are assured that at least that bit wont change during AND, else if that bit changes, then we found a location where the AND is changing. The location closest to $i$ among all the bits will be the location upto which this group has same AND.

There are multiple implementations possible, but for sake of completeness I have given this above described implementation in tab below for those who arent able to come up with the implementations.

View Content

3. Querying-

Do yourself a favor and sort the queries. So MANY contestants underestimate this! Sort the queries on basis of their beginning and/or ending points. If you want to measure how effective it can be, it can change "iterating over the array every time we have to answer a query" to "iterating once to answer all queries collectively." This step is the heart of square root decomposition and Mo's algorithm's.

Now, look at what we have in pre-processed array. We have positions of next change of AND. This means we can quickly jump forward over groups in array. What does this mean? It means if we iterate backwards, from $N-1$ to $0$ (0-based indexing), then for every index we have to do calculations for at most $Log_2N$ groups ahead of it. Good!

Keep a main pointer pointing at end of array, or in simpler words, iterate from $i=N-1$ to $0$ now :p. Now, since AND of one element is that element itself, initialize current AND (say currand) as $A_i$ and starting position of this AND (say, st) as $st=i$. Now, use the pre-processed array to directly jump to the beginning of next group, and find new value of currand. If this AND value satisfies the condition, then we do a increment by 1 the values in range $[st,ed]$ where we define $ed$ as ending point of the old group. Update the values of currand, and set st to point at starting element of new group as this is where the new currand begins. Once main pointer arrives at the beginning point, or $l$ value of current query, its time to answer it! To get the solution for a query, we simply find sum of range $[L,R]$ given in query. As simple as it is!

Now, how do we do it? We can use segment tree with lazy-propagation. But I want you guys to explore another data structure, fenwick tree. Initially my plan was to make this editorial like my other segment tree ones, telling parent child relation, what to store in node and other stuff, but this time I decided to simply describe the idea and leave the how part to you guys. Almost all the good coders used Fenwick tree. BIT, or Fenwick tree, can be at least $4$ times faster than and efficient than segment tree, both in terms of memory and speed. The best part is, which allowed me to leave this part for you guys, is that the operation involved is simply standard range update and range query operation with almost no twist. Nothing can be a better chance to explore and master a data structure than this. I have searched thoroughly to get the bestest resources for you guys to see and hence implement and see the data structure yourself, so buckle up! A wind of change is blowing :).

A minor spoiler for the process- We maintain $2$ fenwick trees, and use updating concept similar to difference array. Like, in difference array, to update the range $[L,R]$ by $K$, we did $A[L]+=K$ and $A[R+1]-=K$. Similarly we will break our query of updating in range $[L,R]$ into $2$ parts and execute it. Also, a term "linear" function will be involved at the tutorials, dont let it get to you, its just simple stuff like $(a-b)x=ax-bx$. You'll see this yourself when you read the tutorials :)

Now, do you think you get the idea? If yes, then answer this- What does our update represent? (in case your ans was no, hop on to my corner to understand this! :D)

Another interesting question, we see that we are updating in range of the group. How does it prevent over-counting, or counting only subarrays inside range $[L,R]$? As in, say my array is $[2,2,1,1]$. I will do an update on range $[3,4]$ (1-based indexing) for $1$ at index $2$ and then another update over same range for $1$ at index $1$. If I give query $[2,4]$, how will the above algorithm give correct answer? Refer to the code in tab below and then to the explanation-

View Content

SOLUTION

The solutions are pasted here for your convenience in case the links arent activated by @admin yet :)

Setter

View Content

Tester

View Content

Editorialist will be put on demand. But till then, take this solution for reference. Shoutout to @abdullah768 for being a good boi writing clean codes :)

$Time$ $Complexity=O(QLogN+N*LogA *LogN)$ (setter's solution)
$Space$ $Complexity=O(NLogA_i)$ where $A_i$ is maximum element in $A$ approximately.

CHEF VIJJU'S CORNER :D

1. Why AND changes at most $Log_2N$ times?

View Content

2. What does update over the range represent?

View Content

3. How does the above algo not count sub-arrays outside the range if its simple sum-

View Content

4. Setter's Notes-

View Content

5. Resources-
- Resource 1 - Fenwick Tree introduction.
- Resource 2 - A brief answer to give you a spoiler on what to expect.
- Resource 3 - I liked this blog.
- Resource 4 - This is also quite cool.

6 Hall of fame for Noteworthy Solutions-

  • taran_1407 - Solved it online (i.e. his solution would work even if queries are online) !!

  • abdullah768 - Neat Code.

  • codebreaker123 - Solved using Mo's algorithm + Hilbert's order.

7. Related Problems-

This question is marked "community wiki".

asked 16 Sep '18, 01:00

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 20 Sep '18, 17:42

It should be N log (max(A[i])) instead of N log N.

(18 Sep '18, 09:22) lohit_974★

Aah, yup XD. My bad.

(18 Sep '18, 11:56) vijju123 ♦♦5★

Solved it online just using Segment tree and handy observation that 0,1, and any 2^(2*k) give square number after AND with any number. See solution: https://www.codechef.com/viewsolution/20031934 A bit tricky combine function, but nothing special...

link

answered 18 Sep '18, 21:31

lboris's gravatar image

6★lboris
3815
accept rate: 40%

I think this blog is currently the best explanation of Hilbert's order for Mo's algorithm, which can be used to solve this problem. Although it was not the expected solution, I think it is a great improvement of Mo's algorithm, which can be used in many problems.

link

answered 18 Sep '18, 22:39

shavelv's gravatar image

0★shavelv
162
accept rate: 100%

Really great question. I didn't even think of using lazy prop segment trees of fenwick trees. I saw the $N \leq 10^5$ and the 3 second time limit thought this must be a square root decomposition problem. I was able to get my square root decomposition solution to work after I figured out how to calculate an answer for the query $[l,r]$ using the precomputed answers and additional information about queries $[l,x)$ and $[x,r]$. Then it was a matter of picking $\sqrt{N}$ special values of $x$ so that either a query will have a small distance ($O(\sqrt{N})$) between $l$ and $r$ and can be calculated directly or $l \leq x$ and $r \geq x$ for some special value $x$. I did sort the queries by their $l$ value but is was more to deal with space complexity than time complexity since with sorting you only ever need the store the results of the precomputations for one value of $x$ at a time.

link

answered 21 Sep '18, 12:33

usernameson's gravatar image

4★usernameson
16
accept rate: 100%

If you still have doubt, remember that in the code snippet given above the setter's and the tester's codes, the ith value in the fenwick tree at any instance tells us the no. of subarrays starting at cl and ending at i which have an AND that is a perfect square.

link

answered 01 Oct '18, 20:23

roll_no_1's gravatar image

6★roll_no_1
413
accept rate: 16%

Very nice editorial with lots of things to learn. Its always a fun to read your editorials and it was published before the usual codechef time. Thanks! for your hardwork behind this :)

link

answered 17 Sep '18, 19:55

pant0000's gravatar image

4★pant0000
1114
accept rate: 10%

3

Thanks a lot dear. A lot of time goes into writing this (which is partly the reason I couldnt complete selina, factorize and lost story in time.). This editorial, counting time needed for observing contestant's solution, decoding algos used and finally writing the editorial took 8.5 hours roughly XD.

(17 Sep '18, 21:52) vijju123 ♦♦5★

@vijju123 your editorials are the best.

link

answered 17 Sep '18, 20:55

skyhavoc's gravatar image

4★skyhavoc
1616
accept rate: 0%

Thanks dear <33333333333

(17 Sep '18, 21:56) vijju123 ♦♦5★

...agree :D

(17 Sep '18, 22:08) l_returns5★

me too....

(18 Sep '18, 20:44) gyanendra3713★

Can someone please post some reference to Gilbert's Order. Can't find it anywhere.

link

answered 18 Sep '18, 01:34

gupta_samarth's gravatar image

4★gupta_samarth
112
accept rate: 0%

edited 18 Sep '18, 01:34

http://codeforces.com/blog/entry/61203 - here is it, an improvement of Mo's algorithm

(19 Sep '18, 12:38) mgch6★
1

*Hilbert order

(19 Sep '18, 20:43) meooow ♦6★

Blockquote the AND value can change at most LogN times.

What does this mean?

link

answered 17 Sep '18, 18:47

mca_123's gravatar image

4★mca_123
151
accept rate: 0%

The AND sum of, assume any $K$, can change at most $LogN$ times before reaching $0$. Check the proof in bonus section for why part.

(17 Sep '18, 18:54) vijju123 ♦♦5★

the value N at the start of the range has LogN bits, at most LogN set (${=}1$). AND with subsequent values will only reset bits ($\to 0$), never set them.

(17 Sep '18, 21:46) joffan5★

Great Question and Editorial!! Thumbs up :)

link

answered 18 Sep '18, 11:12

ripulvohra8's gravatar image

5★ripulvohra8
514
accept rate: 0%

What are the groups here exactly refer to, this is where I am getting stuck. The pre processing part is nice and I also get how 'st' is changing but stuck with 'ed'. What is initial value of 'ed' and it would be great if anyone here can explain this with an example.

link

answered 18 Sep '18, 14:54

goelnandan's gravatar image

4★goelnandan
1
accept rate: 0%

@goelnandan

Groups in setter's solution is a collection of subarrays with same AND.

Stuck at ed? Even after reading notes 2 and 3 in my bonus corner?

$ed$ starts from end of current group, like $st$ at start of this group. $ed's$ next value will be end of next group. Group, beginning at $i$ and ending at $j$, here refers to subarray whose AND sum doesnt change in range $[i,j]$. When I say AND sum in range $[i,j]$ , take and-sum at $[i,i]$ to be $A_i$ and make sure it doesnt change till we reach $j$.

Consider subarrays beginning at $i$ where $i$ goes from $[N-1,0]$. Now, of course, since we are considering subarrays beginning at current $i$, then by the time we reach $st$ our current AND-SUM would be $(A_i,..,A_{st-1})$. AND sum of the entire group of $[st,ed]$ doesnt change anywhere in between $st$ and $ed$. One such case is if the group comprises of same elements.

Now, take AND sum of group and current AND sum. If it satisfies condition, then it means, "For subarrays beginning at $i$, we have suitable endpoints in range $[st,ed]$." Increment values in that range to denote that "We found $1$ more index $i$ such that AND sum of subarray from $i$ to $[st,ed]$ satisfy our condition."

If its still unclear, refer to code and work it out! Thats the best way :)

link

answered 18 Sep '18, 18:57

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

if anyone can tell what is wrong with my solution i have followed editorial ://www.codechef.com/viewsolution/20230890

link

answered 18 Sep '18, 20:27

hacker920's gravatar image

4★hacker920
1
accept rate: 0%

If in this question we were having xor instead of and operation then also we can use the fenwick tree approach or we need to use MO algo then?

As most of the time i am bit confused that BIT can be used only if we have to perform the inverse operations so if we have xor in place of and can we use BIT approach.

link

answered 19 Sep '18, 22:51

honey11's gravatar image

2★honey11
11
accept rate: 0%

edited 19 Sep '18, 22:55

Here you should apply the concept. Fenwick tree was used only for a simple range update. The concept of AND was used in preprocessing part. That thing sadly doesnt hold for XOR, so the preprocessing part fails for XOR, but if you can come up with something for that, then fenwick tree can be used in next step.

(19 Sep '18, 23:39) vijju123 ♦♦5★

what does the editor mean my constant bit in pre-processing part. if the and j th bit is 0 then why and is changing .it's all messy and why initialaizing with n+1

LL fsu[31][N];
    for(i=0;i<31;i++)//Initialize 
        fsu[i][n]=n+1;
    for(i=n-1;i>=1;i--)
    {
        for(j=0;j<31;j++)
        {
            if((1<<j)&a[i+1])//If the bit is set
                fsu[j][i]=fsu[j][i+1];
            else //If the bit changes
                fsu[j][i]=i+1;
        }
    }

somebody explain it bit easier as of level pf beginner

link

answered 20 Sep '18, 16:57

harishskr's gravatar image

2★harishskr
152
accept rate: 0%

We are interested in places where AND changes. We hence dont care about bits which are $0$. And why n+1? Thats depends on implementation and definition you used. This guy used "Let it store beginning of next group w.r.t that bit." so it makes sense.

You can look at the model solution shared for full code.

(20 Sep '18, 17:43) vijju123 ♦♦5★

whenever 0 is encounter in any of j th bit then that's the case when And changes as set bit might get off ; yep it might be case that it might be off before we didn't need to worry about this case.

(21 Sep '18, 00:55) gyanendra3713★

@vijju123 thanks for CHEF VIJJU'S CORNER

link

answered 02 Oct '18, 13:17

knakul853's gravatar image

3★knakul853
863
accept rate: 16%

Notice that there are at most $O(N*LogN)$ values of AND possible in total. Now, either of the 2 approaches are possible-

It should be - Notice that there are at most $O(N*Log(MaxA_i))$ values of AND possible in total. Now, either of the 2 approaches are possible-

link

answered 21 Nov '18, 11:12

aryanc403's gravatar image

6★aryanc403
2.5k1516
accept rate: 10%

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:

×371
×240
×239
×171
×59
×53
×33
×33

question asked: 16 Sep '18, 01:00

question was seen: 6,377 times

last updated: 21 Nov '18, 11:12