ENGXOR - Editorial

editorial
, , , ,
27

read this

28

@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.

29

time limit is O(qn) which is large according to constraint.

30

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.

1 Like
31

why we shouldn’t use endl?

32

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.

1 Like
33

because endl is slower than “\n”. endl is manipulator and “\n” is a character @praven609

34

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

35

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;

}

36

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 :slight_smile:

1 Like
37

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;

}

38

Ooooo right
Thanks buddy

39

very good editorial . thanks @tmwilliamlin

1 Like
40

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);
       }
      }
1 Like
41

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??

42

Parity means the number of set bits of a number in binary representation is either odd or even.simply, count number of 1’s,if its divisible by 2 means parity is 0(even) other wise 1(odd).

43

More generally, the parity of x is even if x is divisible by 2 and odd if it is not.

44

Apologies got confused

45

Thankyou for the editorial. It really helped me.

46

I have this stupid little doubt in the sample test case. The query given is 3 whose binary representation is 11 so the parity of set bits is even which means every element’s parity will change 2 times. This will result in no change in the number of even set bits of the array but the answer comes out (2, 4) which would happen if the number of set bits of the parity were odd.
Any help would be appreciated.
Thanks :smiley: