Why am I getting a TLE in all cases?
Using Python3:
import sys
from sys import stdin, stdout
T=int(stdin.readline())
for x in range(0,T):
N,Q = map(int,input().split())
A = list(map(int,input().split()))
for q in range (0,Q):
P=int(stdin.readline())
x = bin§.count(‘1’)
eve = 0
for i in range(0,N):
y = bin(A[i]).count(‘1’)
if x%2 ==0:
if y%2 ==0:
eve = eve+1
else:
if y%2!=0:
eve = eve+1
stdout.write(str(eve) + " " + str(N-eve))"Tnstead of __builtin_popcount(x) we can directly use __builtin_parity(x)
basically if f(N) represents nu[quote=“kabirsingh2027, post:9, topic:56715, full:true”]
Instead of __builtin_popcount(x) we can directly use __builtin_parity(x)
basically if f(N) represents number of set bits in binary representation of N, then
f(N xor K) = f(N) xor f(K)
where f(x) is __builtin_parity(x), a built-in function in C++.
[/quote]
mber of set bits in binary representation of N, then
f(N xor K) = f(N) xor f(K)
where f(x) is __builtin_parity(x), a built-in function in C++."
This is wrong . say f is popcount then f(1 xor 1) = 0 != 1 + 1 =2 . Are you sure ? It doesnt even work for parity,
Parity is equal…
Edit: 1 xor 1 is 0 not 2.
don’t use endl.
@tmwilliamlin Although this is not a conventional way of thinking about the problem. This generates a Thue-Morse sequence. I based my logic on this -
#include <bits/stdc++.h> using namespace std; typedef long long ll; unordered_map<ll,bool>um; ll max_a = 65536; bool normalize_count(ll number) { int indx = number / max_a; bool similar_seq = 0; if (um[indx]==0) similar_seq = 1; //cout<<indx<<" "<<similar_seq<<" "; bool count = 0; //while (number) //{ count = count ^ um[number % max_a]; //number /= max_a; //} //cout<<count<<endl; if (similar_seq) return count; return 1-count; } void memo() { um[0] = 0; int value = 0; for (ll i=0;i<max_a;i++) { ll x = i ^ (i-1); if ((x ^ (x>>1)) & 0x55555555) value = 1 - value; um[i] = value; } } ll read_int(){ char r; bool start=false,neg=false; ll ret=0; while(true){ r=getchar(); if((r-'0'<0 || r-'0'>9) && r!='-' && !start){ continue; } if((r-'0'<0 || r-'0'>9) && r!='-' && start){ break; } if(start)ret*=10; start=true; if(r=='-')neg=true; else ret+=r-'0'; } if(!neg) return ret; else return -ret; } int main() { //ios_base::sync_with_stdio(false); //cin.tie(NULL); memo(); int tc; tc = read_int(); while (tc--) { int elem, quer; elem=read_int();quer=read_int(); int set_even=0, set_odd=0; //vector<ll>numbers(elem,0),queries(quer,0); vector<int>numbers(elem,0); for (int i=0;i<elem;i++) { int number; number = read_int(); //printf("%d",number); if (um.find(number) == um.end()) { ll k = normalize_count(number); if (k) set_odd++; else set_even++; } else { if (um[number]) set_odd++; else set_even++; } } /*for (ll i=0;i<quer;i++) { cin>>queries[i]; }*/ for (int i=0;i<quer;i++) { ll no =0, ne=0; //fastscan1(query); //scanf("%lld",&query); int query; query=read_int(); ll set_query = 0; if (um.find(query) == um.end()) { set_query = normalize_count(query); if (set_query%2 == 0) { set_query = 0; um[query] = 0; } else { set_query = 1; um[query] = 1; } } else { if (um[query] == 0) set_query = 0; else set_query = 1; } if (set_query == 0) printf("%d %d\n",set_even,set_odd); else printf("%d %d\n",set_odd,set_even); } /*int q; cin>>q; for (int i=0;i<q;i++) { int k; cin>>k; cout<<normalize_count(k)<<endl; }*/ } return 0; }
read this
@tmwilliamlin Hey can you please tell why i am getting tle by making seperate funtion for counting set bits insted of __buitin_parity(x)
here is the code getting tle
#include<bits/stdc++.h> using namespace std; int count_bits(int k) { int b; while(k) { b+=k%2; k/=2; } return b%2; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--) { int a,i,n,q,cr[2]={}; cin>>n>>q; for(i=0;i<n;++i) { cin>>a; ++cr[count_bits(a)]; } for(int p; q--; ) { cin >> p; int z=count_bits(p); cout << cr[z] << " " << cr[z^1] << "\n"; } } }
while if i replace the count_bits function by __buitin_parity the soln gets accepted.
Please help.
Thanks in advance.
time limit is O(qn) which is large according to constraint.
brother when you are calling a function it take time suppose your (t ,n) is large and so it is O(nq) time which is large to constrain so thats why its going to tle.
why we shouldn’t use endl?
modulo and division operations are slow. I optimised your count bits function by only using bit operations.
bool count_bits(int k)
{
bool b=0;
while(k)
{
b^=(k&1);
k>>=1;
}
return b;
}
Then it gets accepted in 0.5 seconds. __builtin_parity() is still faster though.
Hi,
Can anyone suggest me how do I get rid of TLE in subtask 2
(PYTH 3.6)
https://www.codechef.com/viewsolution/30579279
Not very sure how to improve my program(This is my first time working with bits).
Thankyou
why is this giving wrong answer?
#include
using namespace std;
int countOne(int n)
{
int count = 0;
while (n)
{
n = n & (n - 1);
count++;
}
if (count % 2 == 0)
return 1;
else
return 0;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t–)
{
int n, q;
cin >> n >> q;
int arr[n];
for (int i = 0; i < n; ++i)
cin >> arr[i];
while (q--)
{
int p;
cin >> p;
int even = 0;
for (int i = 0; i < n; ++i)
{
arr[i] ^= p;
if (countOne(arr[i]))
even++;
}
cout << even << " " << n - even << endl;
}
}
return 0;
}
Because for every Test Case, Your array will get updated and in question the array to be used is the original one only.
You have to Xor new P’s with the old array for the given test cases in queries.
You need to keep a utility array for new operations 
why this code is giving compilation error, prog.cpp:5:10: error: ‘::main’ must return ‘int’
int main()
#include<bits/stdc++.h>
#define int long long int
#define endl “\n”
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n,p;
cin>>n>>p;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int even=0,odd=0;
for(int i=0;i<n;i++)
{
int check = __builtin_popcount(a[i]);
if(check%2==0)
even++;
else
odd++;
}
while(p--)
{
int input;
cin>>input;
int even1=even,odd1=odd;
int check1 = __builtin_popcount(input);
if(check1%2!=0)
{
even1=odd;
odd1=even;
}
cout<<even1<<" "<<odd1<<endl;
}
}
return 0;
}
Ooooo right
Thanks buddy
Why did my code only manage to get 30 points?
public static void main (String[]args) throws java.lang.Exception
{
// your code goes here
Reader in = new Reader();
int t = in.nextInt ();
for (int i = 0; i < t; i++)
{
int n = in.nextInt();
int q = in.nextInt();
int odd=0;
int even=0;
for (int j = 0; j<n ; j++)
{
if (Integer.bitCount(in.nextInt())%2==0) even++;
else odd++;
}
for (int j = 0; j<q;j++)
{
int p =in.nextInt();
if (Integer.bitCount(p)%2==0)
{
System.out.println(even + " " + odd);
}
else System.out.println(odd + " " + even);
}
}
i know this is very basic question, but i had to ask,
what do u mean by “parity of number of set bits”,
i mean what is parity??