TLE in ENGXOR

Continuing the discussion from ENGXOR - Editorial:

Why am I getting tle in subtask 2??
https://www.codechef.com/viewsolution/30429316

You are getting a TLE because your method for checking number of 1’s in query is O(n) you try using this method instead because it operates in O(1) time.

private static int meth(int a)
{
a^=a>>16;
a^=a>>8;
a^=a>>4;
a&=0xf;
return (0x6996 >> a) & 1;
}
It returns 1 for odd no of 1s and 0 for even

2 Likes

This property might come in hand(this is similar to XOR but kinda extended):

  • XOR of two numbers where both have even/odd set bit count => Output has even set bits.

      Example:
       x = 3   (011)  [HAS 2 SET BITS] 
       y = 15 (1111)  [HAS 4 SET BITS]
      
       Both have even SET bits. 
       Their XOR is 12 (1100). It have even bits. 
    
  • XOR of two numbers where both have different number of set bit(one has even bit and another has odd bits) => Output has odd set bits.

4 Likes

Yeah I have done the same
Checked for number of elements with even number of 1s(C1) and odd number of 1s(n-c1).
Then for each query if the query contains even number of 1s then print c1,n-c1 else n-c1,C1.

But Integer.bitCount uses O(1) time

The input/output is quite large, please use fast reading and writing methods.

yeah but i have used the fastest i/o method using datastream .

I don’t use Java so I can’t say.

1 Like

You didn’t. For fast output you need to use PrintWriter.

In your code:
On line 142, I added: PrintWriter out = new PrintWriter(System.out);
On line 156&158 I replaced: System.out.println with out.println
On line 160, I added: out.flush();

https://www.codechef.com/viewsolution/30531037

3 Likes

Thanks @hackinet

1 Like