ORTUPLES - Editorial

editorial
,
1

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)
2

Well, I was getting TLE for O(21 * 8) solution in Python, submission got accepted in C++ though

3

Unfortunately Python is quite slow with computations, which is recommended to submit in PyPy most of the time (If I recall correctly, PyPy actually has slightly slower default input but that doesn’t matter any more when you use sys.stdin.readline).

Here is your code submitted in PyPy3, as you can see it passes comfortably (and sees a speedup of at least 10x).

1 Like
4

You don’t neccessarily need to do casework. You can even brute force all possibilities, per bit, and check if it is satisfies, avodiing any extra casework or anything
https://www.codechef.com/viewsolution/73433796

5

Why we haven’t consider 0 and 2 count cases?

7

Can anyone explain what is meant by this statement ?

8

If cnt = 0 or cnt = 2, There will be only 1 case so ans*1 = ans, No need of writing that case.

10

Actually, in this problem, I am using 1<<(2count) to get 4^count.
where count is no of times ones come in p,q,r at some bit position.
But I am getting WA for two test cases.
While when I use pow(4,count) , I am getting write answer.
Is 1<<(2count) is wrong approach.