I can’t understand what is wrong in my code ?? plz help
https://www.codechef.com/viewsolution/80193617
2 Likes
1 << j will overflow for j \gt 31, since it computes in int. Use 1LL << j instead.
Unfortunately, that appears to be your only mistake.
2 Likes
https://www.codechef.com/viewsolution/80275344
Runtime error: RE (SIGSEGV) for some of the tests.
Anyone knows why?
@zoharbarak
It is because you have defined a as a vector of int, and it should be long long .
Now what happens is that cin expects an int, but in the input buffer is a big number. So this creates some anomalies and in the end, cin doesn’t behave well.
1
2 1
1000000000000000 1000000000000000
1 1 1 2 2
If you try this custom test case in your original code, you will get a runtime error on CodeChef ide.
Also, you should look for overflow in your final calculation of res
Modified Accepted Solution: CodeChef: Practical coding for everyone
1 Like
Thanks 
You are not inputting anything inside the loop for “q”…So the 1st value (i.e. k) becomes the n of the next test case, and further operations are performed according to that, which can cause TLE.
There can be upto 5\cdot 10^4 testcases, and you’re creating an array of size 10^5 \times 61 for each one. That’s over 10^{11} operations just to allocate the memory, it’s no surprise that you get TLE.
1 Like
1<<j will overflow
use
1LL<<j instead
1 Like
Hello All,
Can anyone please tell me what’s wrong with my code, it was failing one test case.
My Code
Thanks.
@celestialidiot
Using k = log2(mx) was causing errors.
Use k = 59.
Modified Accepted Solution
https://www.codechef.com/viewsolution/80307160
Thanks
Take my whole day to code. learn a new concept of prefix sum on bit. I was thinking that this don’t exists . There were no blog post that I find related to this .
If anyone Have set of question to practice on prefix on bit . Please do reply or mail it (yadav11adu@gmail.com).
#include <bits/stdc++.h>
using namespace std;
#define int long long int
// count the xor value whose kth bit is set
void solve(){
int n,q;
cin>>n>>q;
vector<int> v(n);
vector<vector<int>> prefix(n,vector<int> (62));
for(int i=0;i<n;i++){
cin>>v[i];
vector<int> temp(60);
for(int j=0;j<=60;j++){
if((v[i]>>j)&1) temp[j] = 1;
else temp[j] = 0;
if(i == 0) prefix[i][j] = temp[j];
else prefix[i][j] = prefix[i-1][j] + temp[j];
// cout<<prefix[i][j]<<" ";
}
// cout<<endl;
}
while(q--){
int k,l1,r1,l2,r2;
cin>>k>>l1>>r1>>l2>>r2;
l1--,r1--,l2--,r2--;
int pr1;
if(l1 - 1 < 0) pr1 = 0;
else pr1 = prefix[l1-1][k];
int pr2;
if(l2 - 1 < 0) pr2 = 0;
else pr2 = prefix[l2-1][k];
int FirstSet = prefix[r1][k] - pr1;
int FirstUnSet = (r1 - l1 + 1) - FirstSet;
int SecondSet = prefix[r2][k] - pr2;
int SecondUnSet = (r2 - l2 + 1) - SecondSet;
// cout<<FirstSet<<" "<<FirstUnSet<<" "<<SecondSet<<" "<<SecondUnSet<<endl;
cout<<FirstSet*SecondUnSet + FirstUnSet*SecondSet<<endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
1 Like
The issue there is the lines
counts1[j]=counts1[j]+[counts1[j][-1]+((l[i])%2)]
counts0[j]=counts0[j]+[counts0[j][-1]+((((l[i])%2)+1)%2)]
If A is an array of length N, doing A = A + [x] in Python takes \mathcal{O}(N) time since it creates a copy of A, appends to it, then assigns the new list to A.
Because of this, your code is actually \mathcal{O}(60N^2),
Since you want to append to the array, just use Python’s inbuilt append function instead, which works in \mathcal{O}(1): this change alone makes your code fast enough, see submission.
You aren’t going to find a blog post on it because it’s not actually anything special or a ‘technique’.
If you can find the prefix sums of one array, you can obviously do it for 2 arrays, 3, arrays, \ldots, 60 arrays, right? That’s essentially what you’re doing here: applying prefix sums on 60 different arrays.
1 Like
can you help me understand how you have used prefix sum here or maybe provide some links to understand how to use prefix sum.
I can’t understand why we are taking prefix[n][62].
prefix[n][62]
Here n represent the number of element in array .
62 → represent number of bits require to represent a single number of type long long int.
we have taken bit prefix sum of n element in array . It is small part of bit manipulation
Here is the code which you would able to understand better
#include “bits/stdc++.h”
using namespace std;
#define int long long int
#define now(x) cout<<#x<<" : "<<x<<endl;
bool arrSame(vector<int>& bits,vector<int>& ors){
for(int i=0;i<bits.size();i++){
if((bits[i] > 0 and ors[i] == 0) or
(bits[i] == 0 and ors[i] > 0))
return false;
}
return true;
}
bool orCalculate(vector<int> v,vector<int> ors,int mid){
vector<int> bits(32,0);
for(int i=0;i<mid;i++) for(int j=30;j>=0;j--)
if(v[i] & (1ll<<j)) bits[j]++,ors[j]--;
if(arrSame(bits,ors)){
// cout<<mid<<endl;
return true;
}
for(int i=mid;i<v.size();i++){
for(int j=30;j>=0;j--){
if(v[i - mid] & (1ll<<j)) bits[j]--,ors[j]++;
if(v[i] & (1ll<<j)) bits[j]++,ors[j]--;
}
if(arrSame(bits,ors)){
// cout<<mid<<endl;
return true;
}
}
return false;
}
void solve() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < v.size(); i++) {cin >> v[i];}
vector<int> bits(32,0);
for(int i=0;i<v.size();i++) for(int j=30;j>=0;j--)
if(v[i] & (1ll << j)) bits[j]++;
int low = 1, high = n+1, ans = -1;
while (low <= high) {
int mid = (low + high) >> 1;
if (orCalculate(v, bits, mid)) {
ans = max(ans, mid);
low = mid + 1;
} else {
high = mid - 1;
}
}
// cout<<"ASDF : ";
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
Some basic code for better understanding
***Count the set bits in array***
vector<int> set(32,0);
for(int i=0;i<n;i++)
for(int j=30;j>=0;j--)
if(v[i] & (1ll << j)) set[j]++;
***Basic Manipulation***
int onmask = (1<<i);
int offmask = ~(1<<j);
int togglemask = (1<<k);
int checkmask = (1<<m);
cout<<( n | onmask )<<endl;
cout<<( n & offmask )<<endl;
cout<<( n ^ togglemask )<<endl;
cout<<( (n & checkmask) == 0 ? "false" : "true" )<<endl;
// check weather the bits are set or not
for(int j = 0;j<32;j++){
int mask = (1 << j);
bits[j] += ((mask & v[i]) == mask);
}
***Power of Two***
1<<n pow(2,n) ***,*** ***double*** fmod(n,mod)
***How many BST are possible with n nodes?***
(2n)! / (n+1)! n!
***How do I pass multiple ints into a vector at once?***
`vector<int> array;` ``
`array.insert(array.end(), { 1, 2, 3, 4, 5, 6 });`
``
`Concatenating two vectors`
`vector1.insert( vector1.end(), vector2.begin(), vector2.end() );`
``
Power Setcheck weather bit is set with respect to no
``
Check K-th Bit Set
return (n&(1<<k));
return (1&(n>>k));
Set K-th Bitreturn (N | (1 << K));
***Storing in desc order in map***
`map<` `int` `, string, greater<` `int` `> > mymap;`
`` `multimap<` `int` `, string, greater<` `int` `> > mymap;`
`` `set<` `int` `, greater<` `int` `> > s1;`
``
`Priority Queue`
``
`` `// Creates a max heap`
` ` `priority_queue <` `int` `> pq;`
`// Creates a min heap`
` ` `priority_queue <` `int` `, vector<` `int` `>, greater<` `int` `> > pq;`
``
``
`Finding No of Digit in Integer`
` ` `// Find total number of digits - 1`
` ` `int` `digits = (` `int` `)` `log10` `(n);`
``
**Negative No Modo**
((a%n) + n)%n)
**Binary Exponentiation**
int power(int a , int b) {
if(b == 0)
return 1;
int res = power(a , b>>1);
if(b & 1)
return (res * res % mod) * a % mod;
return res * res % mod;
}
int binExpIter(int a,int b){
int ans = 1;
while(b){
if(b&1) ans = (ans * a) %M;
a = (a*a) % M;
b >>= 1;
}
return ans;
}
***Negative Mod***
#define ma_mod(a,n) ((a%n)+a)%n
**Number of Subsequences** nC0 + nC1 + nC2 + … nCn = 2n
***Decimal to Binary***
`int` `decToBinary(` `int` `n)` {
` ` `for` `(` `int` `i = 31; i >= 0; i--) {`
` ` `int` `k = n >> i;`
` ` `if` `(k & 1)`
` ` `cout << ` `"1"` `;`
` ` `else`
` ` `cout << ` `"0"` `;`
` ` `}`
`}`
***Substring of s String***
`for` `(` `int` `i = 0; i < str.length(); i++) {`
` string subStr;`
` ` `// Second loop is generating sub-string`
` ` `for` `(` `int` `j = i; j < str.length(); j++) {`
` ` `subStr += str[j];`
` ` `cout << subStr << endl;`
` ` `}`
`}`
1 Like
Sir I have been Observing you skill , while few contest . Please do suggest some topic that I must do I order to improve coding skill while coding
why is it giving WA please let me know
https://www.codechef.com/viewsolution/84632584
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define f(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define pb push_back
using namespace std;
void test(){
int n,q;
cin>>n>>q;
vector<ll> a(n);
f(i,n)cin>>a[i];
vector<vector<int>> setbit(n+1,vector<int>(61,0));
for(int i=1; i<=n; i++){
for(int j=0; j<60; j++){
if(a[i-1]>>j & 1)setbit[i][j] = setbit[i-1][j]+1;
else setbit[i][j] = setbit[i-1][j];
}
}
while(q--){
int k,l1,r1,l2,r2;
cin>>k>>l1>>r1>>l2>>r2;
int x=setbit[r1][k]-setbit[l1-1][k], y=setbit[r2][k]-setbit[l2-1][k];
int ans = x*(r2-l2+1-y) + y*(r1-l1+1-x);
cout<<ans<<"\n";
}
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests=1;
cin>>tests;
while(tests–){
test();
}
}
// 1 2 3 4 5
// 1 2 4 3 2 k=1, l1=1 r1=3 l2=5 r2=5 001 010 100 011 010
// k=0 1 1 1 2 2
// k=1 0 1 1 2 3
// k=2 0 0 1 1 1
// k=3 0 0 0 0 0
// .
// .
// .
// k=60 0 0 0 0 0