PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Yash Goyal
Testers: Abhinav Sharma[inov_360 | CodeChef User Profile for Abhinav sharma | CodeChef], Nishank Suresh [iceknight1093 | CodeChef User Profile for Nishank Suresh | CodeChef]
Editorialist: Pratiyush Mishra
DIFFICULTY:
Easy-Medium
PREREQUISITES:
None
PROBLEM:
Given two arrays A and B each of length N.
Find the value \sum_{i=1}^N\sum_{j=1}^N \max(A_i\oplus B_j,A_i\& B_j).
Here \oplus and \& denote the bitwise XOR operation and bitwise AND operation respectively.
Quick Explanation:
First of all let us see that pattern in max(x \oplus y, x \& y).
If the MSB of x and y are i and j respectively, then ,
- if i \neq j then x \oplus y > x \& y.
- if i=j, then x \oplus y < x \& y. This is because maximum of both will be the one with highest bit ON.
Now, for array b store the following for each i, sum of all values of b that has i as its MSB. Now, iterate through a[i] and add contribution according to its MSB to the sum.
Explanation
We will define arrays to store different values as follows:
msb[i] → number of elements in a having their most significant bit as i.
bits[i] → number of elements in a having their i_{th} bit on.
bit\_table[i][j] → number of elements in a having their most significant bit as i, with j_{th} bit on.
We will calculate values for these arrays using simple bit manipulation and then proceed to calculate the sum as follows.
We will loop through the elements of B and see for each element as B_i, having it most significant bit as k.
-
If all bits of B_i is unset then we would simply take the sum of array A and add it to our answer, since A_j \oplus B_i = A_j, 0 \leq j < n
-
Otherwise we would loop through the bits of B_i and for each bit say j
- if j_{th} bit is set, then we add the following to our final answer:
answer +=(1< < j) \times bit_table[k][j]
- if j_{th} bit is not set, then we add the following:
TIME COMPLEXITY:
O(N) for each test case.