Answers to: ANDMIN - Editorialhttps://discuss.codechef.com/questions/82486/andmin-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ANDMIN">Practice</a><br>
<a href="http://www.codechef.com/COOK71/problems/ANDMIN">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/pushkarmishra">Pushkar Mishra</a> </p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Segment Trees</p>
<h1>PROBLEM:</h1>
<p>Given is an array $A$ of length $N$. There are two types of operations that we need to handle on this array:</p>
<ul>
<li>0 $l$ $r$: report the minimum of all the numbers in the range $l$ to $r$.</li>
<li>1 $l$ $r$ $x$: change all the numbers in the range $l$ to $r$ such that $A[i]$ = bitwiseAnd($A[i]$, $x$), $\forall l \leq i \leq r$.</li>
</ul>
<h1>EXPLANATION:</h1>
<p>The nature of the problem clearly hints towards segment trees. We need to efficiently perform the bitwiseAnd operation over a range of numbers and then report the minimum. Reporting the minimum is a standard operation with segment trees: we just have to store the minimum for the corresponding range at each node of the segment tree, and we can answer the queries in $\mathcal{O}(\log N)$ time. But how do we update the minimums when an update operation is requested? </p>
<p>There are no such apparent properties of bitwiseAnd operation that can be applied to a range. There isn't a notion of an elegant lazy propagation either since we need to perform range-update and range-minimum query. </p>
<p>But there is one nice property that we can observe about our update operation: if in a particular update operation, we have an $x$ such that its $i^{th}$ bit (rightmost bit is $0^{th}$ bit) is 0, then the $i^{th}$ bit of all the numbers in the range to be updated becomes 0; and for the rest of the execution of our program, remains 0. This is because there is no way to turn a 0 bit to 1 using bitwiseAnd operations only. </p>
<p>This gives us a huge hint about an efficient algorithm that we can use. It tells us that we are only interested in the those bits of $x$ which are 0, because the 1 bits are not going to change anything. </p>
<p>Furthermore, for a particular node in the segment tree, if we know that there exists no number within its range of indexes such that some bit in that number is 1 while the same bit is 0 in $x$, then we don't need to bother updating it or its descendants because again nothing is going to change. </p>
<p>So now we know how to build our segment tree, i.e., what information to store in each of its node. Each node of the segment tree will have a boolean array named $bits$ of length 32 and an integer $mini$. In the array $bits$, $bits[i]$ = true indicates that there is at least one number in the range represented by the node such that its $i^{th}$ bit is 1. Accordingly, if it is false then there is no number within the range of the node such that its $i^{th}$ bit is 1. The integer $mini$ represents the minimum of all the numbers within the range of the node. </p>
<p>So we now have a way to initialise our segment tree. It is given below as pseudo-code: </p>
<pre><code>void buildNode (node r):
if(r == leaf) {
//let us say that this leaf corresponds to A[index] of the given array.
segTree[r].bits[i] = value of ith bit of A[index]; //for i = 0 to 31
segTree[r].mini = A[index];
return;
}
if(r != leaf) {
buildNode(r->left);
buildNode(r->right);
segTree[r].bits[i] = bitwiseOr of ith bits of r's children; //for i = 0 to 31
segTree[r].mini = minimum(segTree[r->left].mini, segTree[r->right].mini);
}
}
</code></pre>
<p>The update function is very similar, except that we impose the condition that we discussed earlier. If a node $r$ falls within the range to be updated, we will recurse down to update its descendents if and only if there exists an $i$ such that the $i^{th}$ bit in $x$ is 0 but $segTree[r].bits[i]$ is 1. If during update, we reach a leaf node, we simply do $segTree[leaf].mini$ = bitwiseAnd($segTree[leaf].mini$, $x$). </p>
<p>The query operation is a standard range-minimum query operation which can be performed with the help of the stored $mini$ values. If the reader doesn't know about it then he/she can refer here <a href="http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/">range-min query using segment trees</a>. </p>
<p>What is the complexity of our approach? If we look closely, each bit in each number of the array can only set to 0 once. Reaching a number, i.e., reaching a leaf takes $\mathcal{O}(\log N)$ time in a segment tree. Since there are $\log A_{max}$ bits at maximum in any number within the given array $A$, therefore, it will take $\mathcal{O}(\log A_{max})$ per number to set its bits to 0. Since there are $N$ numbers in total, thus, the net complexity is $\mathcal{O}(N\log N\log A_{max})$ per test case. </p>
<p>Please see editorialist's/setter's program for implementation details. </p>
<h1>COMPLEXITY:</h1>
<p>$\mathcal{O}(N\cdot\log N\cdot\log A_{max})$ per test case.</p>
<h1>SAMPLE SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/COOK71/Setter/ANDMIN.cpp">Author</a><br>
<a href="http://www.codechef.com/download/Solutions/COOK71/Tester/ANDMIN.cpp">Tester</a><br>
<a href="http://www.codechef.com/download/Solutions/COOK71/Editorialist/ANDMIN.cpp">Editorialist</a></p>enTue, 26 Jul 2016 10:28:28 +0530Answer by kishore1https://discuss.codechef.com/questions/82486/andmin-editorial/83638<p>Source limit is being given in almost every problem as 50000 Bytes.. What does it mean..??
In this problem.. The N could be atmost (10^5)...
so, if we declare an integer array of size 10^5.. then (10^5)*2 = 200000 Bytes are required..
but source limit is given as only 50000 Bytes..
What does it mean??
please explain me this..</p>kishore1Tue, 26 Jul 2016 10:28:28 +0530https://discuss.codechef.com/questions/82486/andmin-editorial/83638Answer by arunnsithttps://discuss.codechef.com/questions/82486/andmin-editorial/82697<p><a href="/users/8082/pushkarmishra">@pushkarmishra</a> .
We can keep two values in your structure : </p>
<ol>
<li>sol= min value over the range </li>
<li>Bor = BitwiseOR over the range.</li>
</ol>
<p>Now we can update the tree in the building the tree fashion and neglect a range if X&Bor==Bor . quite similar to the editorial though.</p>arunnsitMon, 27 Jun 2016 13:41:17 +0530https://discuss.codechef.com/questions/82486/andmin-editorial/82697Answer by arunnsithttps://discuss.codechef.com/questions/82486/andmin-editorial/82696<p><a href="/users/52053/sandeep9">@sandeep9</a> . At an intuitive level as it looks , we cant use lazy propagation ! because the moment you update a range with lazy, you need to update the min value ( i.e our solution for the node) at that very moment . But theres no simple way to do so .</p>
<p>suppose theres a node [L,R] with min value A and while updating the solution of this node , you mark it as lazy and update A with A=A&X . This is the thing which is going wrong . Theres no certainty that new solution will be A&X .</p>
<p>EXAMPLE : let the node [L,R] contain values {1,2,3,8} , solution for this node is 1 . now an update query comes with X=7 over [L,R] , now according to the lazy solution the answer will be 1&7= 1. but actually 8&7 = 0 . so our answer should be 0 but you take it as 1. </p>
<p>hope you are getting it ! </p>arunnsitMon, 27 Jun 2016 13:19:48 +0530https://discuss.codechef.com/questions/82486/andmin-editorial/82696Answer by shariquemohdhttps://discuss.codechef.com/questions/82486/andmin-editorial/82686<p>I tried it do with lazy propogation, but got WA( and I am not able to find the bug). Here's the link to my code-> <a href="https://www.codechef.com/viewsolution/10624668.">https://www.codechef.com/viewsolution/10624668.</a><br>
I am not able to understand my mistake. Any help is highly appreciated.[NOTE: boolean array "check" is used to check if a node in the lazy segment tree contains any value or not].</p>shariquemohdMon, 27 Jun 2016 09:46:09 +0530https://discuss.codechef.com/questions/82486/andmin-editorial/82686Answer by sandeep9https://discuss.codechef.com/questions/82486/andmin-editorial/82661<p>Why we can't use lazy propogation here ?</p>sandeep9Mon, 27 Jun 2016 00:30:09 +0530https://discuss.codechef.com/questions/82486/andmin-editorial/82661