Good explanation!
I read it. But didnāt get the logic of AND.
No, I think we canāt Solve this question using Fenwick Tree. As for the Fenwick tree, the function needs to be reversible like sum. But itās possible to solve using a Segment Tree.
Hereās my solution using Segment tree:- https://www.codechef.com/viewsolution/45273276
1 Like
AND has the following property => AND is always less than or equal to the maximum of 2 noās.
=> so We need not worry of AND of subarrays as it will always less than or equal to a value which already has been considered alone,
Eg. [2,3] => {2}|{2&3}|{3} => 2&3 = 2, but we already considered {2} so considering {2&3} is of no use.
Hope I cleared your doubt 
Please anybody explain this syntax I copied from the code in editorial
Hi @ak1010, auto is a keyword which tries to assign the datatype of the object which is being assigned to variable āwhich is del in this caseā.
Also, [&](int val){ ā¦} this is a lambda function you can read more about on google, basically it is an inline function which takes inout as āint valā and captures every function or variable defined outside ālike and and cnt[]ā and returns a new value.
1 Like
Thank you so much, that is what I was looking for. The keyword for this type of syntax. Lambda Function. Had I asked this question on stack overflow I wpuld have been banned from thte community.
1 Like
@tripathi1729 thanks a lot for this because i was not getting it from the proof explained above and now i can relate .
1 Like
Just to add to tripathi1729ās excellent explanation: Imagine that this problem did not include the part about looking at all non-empty subarrays of A, and determining their āscoresā by doing a bitwise AND. Imagine that it instead said, you need to find the bitwise OR of all of the values in A.
The key idea: That āsimplerā problem is actually exactly the same problem!
Because for each element of A, there is a subarray that just has that element. And so the bitwise AND of the elements of that subarray is just that element. So every element of A will still be in the list of scores of all of the non-empty subarrays of A that you construct. And you donāt need to worry about any other elements (from other subarrays), since they are constructed by AND-ing more values, and so at best they will certainly not create any additional bit position with a 1 in it when you OR them all together.
1 Like
learn from #anujbhaiyaa in youtube only 3 videos are there but best
Hi all,
I am getting error can you guys please check.
I have attached my code below.
T = int(input())
while T:
N,Q = map(int,input().split(ā ā,2))
A = list(map(int,input().split()))
ANDOP = []
for i in range(len(A)):
ANDOP.append(A[i])
for j in range(len(A)):
if j != (len(A)-1):
AND = A[j]&A[j+1]
ANDOP.append(AND)
val = A[0]
for i in range(len(A)):
if i != (len(A)-1):
val &= A[i]
ANDOP.append(val)
val = A[0]
for i in range(len(ANDOP)):
if i != (len(ANDOP)-1):
val |= ANDOP[i]
OROP = val
print(OROP)
while Q:
X,V = map(int,input().split(ā ',2))
A[X-1] = V
ANDOP = []
for i in range(len(A)):
ANDOP.append(A[i])
for j in range(len(A)):
if j != (len(A)-1):
AND = A[j]&A[j+1]
ANDOP.append(AND)
val = A[0]
for i in range(len(A)):
if i != (len(A)-1):
val &= A[i]
ANDOP.append(val)
val = A[0]
for i in range(len(ANDOP)):
if i != (len(ANDOP)-1):
val |= ANDOP[i]
OROP = val
print(OROP)
Q -= 1
T -= 1
if the indentations are same as that are here than there will be indentation error
you have also used AND before intializing it
/* package codechef; // donāt place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be āMainā only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc= new Scanner (System.in);
int t=sc.nextInt();
while(tā>0)
{
int n=sc.nextInt();
int q=sc.nextInt();
int a[]=new int[n];
int qr[][]=new int[q][2];
for(int i =0;i<n;i++)
a[i]=sc.nextInt();
for(int j=0;j<q;j++)
{
qr[j][0]=sc.nextInt();
qr[j][1]=sc.nextInt();
}
solve(a,qr);
}
}
static void solve(int a[],int qr[][])
{
int dp[]=new int[32];
for(int i=0;i<a.length;i++)
{
int ele=a[i];
int j = 0;
while(ele !=0 )
{
dp[j] += ele%2;
ele = ele/2;
j++;
}
}
int ans=0;
for(int i=31;i>=0;i--)
{
if(dp[i]!=0)
ans=ans+(int)Math.pow(2,i);
}
System.out.println(ans);
int q=qr.length;
for(int i =0 ;i<q ;i++)
{
ans=0;
int index=qr[i][0]-1;
int val=qr[i][1];
int rem=a[index];
int j = 0;
while(rem !=0 )
{
dp[j] -= rem%2;
rem = rem/2;
j++;
}
j = 0;
while(val !=0 )
{
dp[j] += val%2;
val = val/2;
j++;
}
for(int k=31;k>=0;k--)
{
if(dp[k]!=0)
ans=ans+(int)Math.pow(2,k);
}
System.out.println(ans);
}
}
}
The code is running fine on sample test input but showing me WA when submitted can someone tell which edge case Iām missing .
My logic was the same as given in the editorial, but the only thing that i was not doing was update the array for each query i.e i was not doing this step - arr[x]=v;
But my doubt is that in the end we just want to print the answer, and i was getting correct answer for every query, so does it even mattered if we updated the array or not?
Bcz of which i got WA.
Making the update in array is absolutely necessary without this you cannot get correct answer.
Consider the case in which two queries update same index one after the other , according to your method you will still remove bits according to the older value present in the array but the removal of bits has to be done on the basis on updated value so you will get an incorrect answer.
You can try to run your code with such a testcase to verify.
Yeah you are absolutely correct ā¦i just didnāt think of a case where we could have 2 queries updating the same index one after the other!
I got it now. Thanks!
I got TLE using this with time of 1.01 sec .Can anyone tell how to optimize
using namespace std;
int finder(int n,int *a)
{
int i,ans = 0;
for(i=0;i<n;i++)
{
ans = ans|a[i];
}
return ans;
}
int main() {
int n,i,num,q,b;
cin>>n;
while(n--)
{
cin>>num>>q;
int *p = new int[num] ;
for(i=0;i<num;i++)
{
cin >> p[i];
}
cout << finder(num,p)<<endl;
while(q--)
{
cin>>i>>b;
p[i-1]=b;
cout<<finder(num,p)<<endl;
}
}
return 0;
}As soon as your solution hits the time limit, further TC are not judged and you get result as TLE , so the execution time shown in such cases do not matter like 1.01 sec.
The time complexity of your solution for each testcase is O(N*Q) which is of the order 10^10, so this will not be accepted. You should read the editorial and try to optimize according to it.
OK. Thanks .I got ur point
Bro. Just another Thing .Can bit manipulaton & and | be compared to intersection and union as in mathematical set theory.