PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Preparer: Tejas Pandey
Testers: Utkarsh Gupta, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
1703
PREREQUISITES:
None
PROBLEM:
There are three hidden numbers A, B, and C. You know the values of A\vee B, B\vee C, and A\vee C. How many possible tuples (A, B, C) can satify this?
EXPLANATION:
The OR operation is bitwise independent, so we can simply find the number of possibilities for each bit from 0 to 19 and multiply them all together to get the final answer.
Now, let’s look at a specific bit. For this bit, each of A\vee B, B\vee C, A\vee C is either 0 or 1.
There are a few cases here:
- If all 3 are zero, then this bit must be zero in all of A, B, C so there is only one option.
- If exactly one of them is 1, such a case can never happen so the answer is immediately zero (for example, if A\vee B = 1, then either A or B must be 1 at this bit, and so at least one of A\vee C, B\vee C must be 1).
- If exactly two of them are 1, there is exactly one option (if A\vee B = 0, then both A and B must be 0 and so C = 1 is the only option, and so on).
- If all three are 1, there are 4 possible options:
- One way is for all three of A, B, C to have a 1 at this bit
- Otherwise, we can also choose exactly two of them to have a 1 at this bit. There are 3 ways to choose a pair.
- Adding up the above options, we have 4 valid possibilities.
Compute the appropriate multiplier for each bit, then multiply them all together to obtain the final answer.
Note that the answer can be as large as 4^{20}, so make sure you use a 64-bit integer datatype.
Alternately, once a bit is fixed, one can also simply iterate across all 2^3 = 8 possibilities of values of A, B, C and see how many of them contribute to the current configuration.
TIME COMPLEXITY
\mathcal{O}(\log N) per test case, where N = 2^{20}.
CODE:
Preparer's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
//freopen("inp1.in", "r", stdin);
//freopen("inp1.out", "w", stdout);
int t;
cin >> t;
while(t--) {
int x, y, z;
cin >> x >> y >> z;
long long ans = 1;
for(int i = 0; i < 20; i++) {
int cnt = ((x&(1<<i)) > 0);
cnt += ((y&(1<<i)) > 0);
cnt += ((z&(1<<i)) > 0);
if(cnt == 1) ans = 0;
else if(cnt == 3) ans *= 4;
}
cout << ans << "\n";
}
}
Editorialist's code (Python)
for i in range(int(input())):
x, y, z = map(int, input().split())
ans = 1
for bit in range(30):
ct = ((x >> bit) & 1) + ((y >> bit) & 1) + ((z >> bit) & 1)
if ct == 1:
ans = 0
elif ct == 3:
ans *= 4
print(ans)