ABCXOR Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

1626

PREREQUISITES:

None

PROBLEM:

You are given two integers N and K. Find number of ordered triplets (A, B, C) that satisfy the following conditions:

  • 0 \le A, B, C \lt 2^N
  • A, B and C are distinct
  • A \oplus B \oplus C = K

Here, \oplus denotes the bitwise XOR operation.

EXPLANATION:

Observation 1: Given any number A \;(\leq 2^N), we can always select two numbers B and C such that their XOR is K.
This is because for each bit of A, we can set bits of B and C accordingly such that the final XOR of the three is equal to the bit of K.
Let’s have bit representation of a number X be as:

X = X_NX_{N-1}......X_1

Now for K if at any position i (going from right to left), its bit would be K_i. Lets take two cases:

  • K_i = 1:
    • For A_i = 1: To make final XOR as 1, (B_i,C_i) could be either (1,1) or (0,0)
    • For A_i = 0: To make final XOR as 1, (B_i,C_i) could be either (1,0) or (0,1)
  • K_i = 0:
    • For A_i = 1: To make final XOR as 0, (B_i,C_i) could be either (1,0) or (0,1)
    • For A_i = 0: To make final XOR as 0, (B_i,C_i) could be either (1,1) or (0,0)

Observation 2: None of the numbers can be K since then the other two numbers would become equal to each other.

Thus now for selecting A we would have 2^N - 1 options. As for B and C, for each bit position of A, we would have 2 ways of selecting bits of B and C. Among all the possible selections of B and C, there shall be 1 case where B is equal to A and 1 case where C will be equal to A. Thus after subtracting these cases we will have 2^N - 2 ways of selecting B and C. Thus our final answer would be:

ans = (2^N - 1) \times (2^N - 2)

TIME COMPLEXITY:

O(logN), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

4 Likes

This is a perfect example of que which can destroy ur confidence.
om shanti :pray:

29 Likes

Observation 1:
3 * 3 - 3 = 6

Observation 2:
7 * 7 - 7 = 42

Observation 3:
511 * 511 - 511 = 260610

Observation 4:
For N and K the answer will be
(2^N - 1)(2^N - 1) - (2^N - 1)

9 Likes

Yet another formula-

(2^N C 3 / 2^ N) * 6

i.e
number of ways to choose 3 numbers from entire possible numbers/ all possible numbers * number of ways to arrange 3 numbers

1 Like

Thus now for selecting A we would have 2^N-1 options.

And how did it got proved?

1 Like

Interesting.

I went thinking like this. If a bit in K is 0, then I have 4 options for the same bit in A,B,C \rightarrow 000, 011, 101, 110. If a bit in K is 1, then I also have 4 options 111, 100, 010, 001.

All triplets that xor to K is then 4^{n}. Of course, the task says numbers in a triplet need to be distinct. So I subtract all cases when 2 numbers are the same, which is 3\cdot (2^{n}-1) \rightarrow there are 2^n possible numbers, and if two are the same and third one is K (without a loss of generality A = B = x and C=K) I have 2^n-1 choices for x (multiplied by 3 because there are 3 options for which number is K). I also want to exclude (K,K,K) from the final count so I will subtract 1.

4^n-3\cdot(2^n-1)-1

18 Likes

//6 = 2 multiply 3 n=2 1<<2 =4 (4-1) multiply (4-2)
//42=6 multiply 7 n=3 1<<3=8 (8-1) multiply(8-2)
//260610=510 multiply 511 n=9 1<<9=512 (512-1 ) multiply (512-2)
https://www.codechef.com/viewsolution/67419259

I got amazed by the answer i got which didn’t depend upon k at all. Great question.

how did you calculate when two numbers are same can you please elaborate more ?

Lets see
making b == c → (for unset bit we have 0 11 case + 0 00)
(for set bit we have 1 11 case + 1 00)
see the last two bit remians the same for b and c
ways: (2^(set_bit count) )*(2^( n - set_bit count))

similary for a==b and a==c

Now we have to add two case which is reduces 3 time (a==b==c)
ans = 4^n - (2^n)*3 + 2

2 Likes

Total number of choices 2^n from which you cant take k ( as the other two will become the same which is not allowed )
So total choice = 2^n - 1

1 Like

A \oplus B \oplus C = K, if A = B = x, then A \oplus B = 0 \implies 0 \oplus C=K \implies C=K.
How many triplets have the form (x, x, K)?
If x \neq K, then out of 2^n numbers (in range 0 to 2^n-1, there is 2^n numbers) you can choose 2^n-1 for x (if you use all numbers but K). If you change the choice for which number is K, A=C=x, B=K, then that’s another 2^n-1 extra triplets to remove and same is the case for B=C=x, A=K.
In total there is 3 \cdot (2^n -1) cases where one number is K and others are equal.

K \oplus K \oplus K = K. When we counted 3 \cdot (2^n - 1) we explicitly avoided (K,K,K), by not choosing x = K. Therefore, we need to subtract 1 to remove (K, K, K) from the total count 4^n.

3 Likes

Thanks buddy.

thanks

I also went with thinking… but couldn’t exclude 2 equal numbers and all 3 equal numbers
Now i understood… nyc explaination tnks bhai :heart:

who can’t get it…
4^n is total number of (distinct) triplates, whose xor is k
if 2 nums are same than thier xor will be zero and 3rd number will have to be k
a==b then c=k ,…,… (2^n-1 ways)
a==c then b=k ,…,… (2^n-1 ways)
b==c then a=k ,…,… (2^n-1 ways)
a=b=c = k ,…,… (1 ways)

1 Like

Why we are diving it by all possible values ? This I did not get. Please help!

The value of A can range from [0 - 2^n) (2^n is not included), so we can say we have 2^n choices. Out of them A cannot be equal to K because if A==K then B should we equal to C. so 2^n - 1 choices!

Hope you understood!

I came up with the solution
4^n - 3*2^n + 2

  • for every bit, be it 1 or 0, we have 4 choices,

eg) for K’s i’th bit is 1 lets say, so i’th bit in {a,b,c} could be {1,1,1}, {1,0,0}, {0,1,0}, {0,0,1}.
if K’s i’th bit is 0, then {a,b,c} could be {1,1,0}, {1,0,1}, {0,1,1}, {0,0,0}.
Hence 4 options for every bit, thus the 4^n.

  • We cannot have duplicates, for any pair in {a,b,c}, we can have 2^n duplicates possible.

eg) for K’s i’th bit is 1 lets say, so i’th bit in {a,b,c} could be {1,1,1}, {1,0,0}, {0,1,0}, {0,0,1}.
for a to be same as b, we see {1,1,1} and {0,0,0} has a = b, i.e 2 in those 4.
we can make pairing a,b or b,c or c,a so we subtract 3 * 2^n

  • As we have decreased a=b, b=c, c=a cases, we have removed the case a=b=c total of three times, we only needed to removed it once. so we add the case a=b=c case twice.

every bit has only 1 case where a=b=c, so we add 2 * (1^n) .

Final answer = 4^n - 3 * 2^n + 2

1 Like

OSM :+1:

hey @mankesh nice explaination