Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Beautiful quadruples challenge

Sharing is caring!

Problem statement
We call an quadruple of positive integers, (W, X, Y, Z), beautiful if the following condition is true:

W \oplus X \oplus Y \oplus Z \ne 0

Note: \oplus is the bitwise XOR operator.

Given A, B, C and D, count the number of beautiful quadruples of the form (W, X, Y, Z) where the following constraints hold:

1 \le W \le A
1 \le X \le B
1 \le Y \le C
1 \le Z \le D

When you count the number of beautiful quadruples, you should consider two quadruples as same if the following are true:
– They contain same integers.
– Number of times each integers occur in the quadruple is same.

For example (1, 1, 1, 2) and (1, 1, 2, 1) should be considered as same.

Input Format
A single line with four space-separated integers describing the respective values of A, B, C and D.

Constraints
1 \le A, B, C, D \le 3000

Output Format
Print the number of beautiful quadruples.

Sample Input

1 2 3 4

Sample Output

11

Explanation
There are 11 beautiful quadruples for this input:
(1,1,1,2)
(1,1,1,3)
(1,1,1,4)
(1,1,2,3)
(1,1,2,4)
(1,1,3,4)
(1,2,2,2)
(1,2,2,3)
(1,2,2,4)
(1,2,3,3)
(1,2,3,4)

Thus, we print 11 as our output.
Note that (1, 1, 1, 2) is same as (1, 1, 2, 1) .

Solution
Since the order of the integers in a quadruple does not matter we can sort our input values such that A \le B \le C \le D:

int[] arr ={A,B,C,D};
Arrays.sort(arr);
A = arr[0];
B = arr[1];
C = arr[2];
D = arr[3];

We will then solve it for the first half of the quadruple (a,b,c,d). For that we define the following arrays:
total = new int[3001]: total[B] holds the number of pairs \{ a,b\} such that a \le b with 1 \le a \le A and 1 \le b \le B:

final int MAX = 3000;
int[] total = new int[MAX + 1];
for (int a = 1; a <= A; a++) {
    for (int b = a; b <= B; b++) {
        total[b] += 1;
    }
}
for (int i = 1; i <= MAX; i++) {
    total[i] += total[i - 1];
}

count = new int[3000 + 1][4096 + 1]: count[B][x] holds the number of pairs \{a,b\} such that a \le b and a \oplus b = x with 1 \le a \le A and 1 \le b \le B:

final int MAX_XOR = 4096;
int[][] count = new int[MAX + 1][MAX_XOR + 1];
for (int a = 1; a <= A; a++) {
    for (int b = a; b <= B; b++) {
        count[b][a ^ b] += 1;
    }
}
for (int i = 0; i <= MAX_XOR; i++) {
    for (int b = 1; b <= MAX; b++) {
        count[b][i] += count[b - 1][i];
    }
}

Note here that the maximum XOR value achievable is 4096 since 1 \le A, B, C, D \le 3000 (12 bits).

We can now go ahead and use total and count to find our solution. Remember we sorted our A \le B \le C \le D so that we count our quadruples (a,b,c,d) such that a \le b \le c \le d.

For the second half of (a,b,c,d) we have \{c,d\} with 1 \le c \le C and 1 \le d \le D. Let c \oplus d = y. We know that a \oplus b \oplus c \oplus d = 0 if a \oplus b = y. We know that we have a total of total[c] pairs \{a,b\} with a \le b and 1 \le b \le c. We want to exclude the pairs that have a \oplus b = y. There are count[c][y] pairs \{a,b\} that combined with \{c,d\} result to 0. So from total[c] we have to exclude count[c][y] and do this for all possible c and d:
\sum_{c=1}^{C}\sum_{d=1}^{D}total[c]-count[c][c \oplus d]

long ans = 0;
for (int c = 1; c <= C; c++) {
    for (int d = c; d <= D; d++) {
        ans += (total[c] - count[c][c ^ d]);
    }
}

The full code is listed below.

Full code

public class BeautifulQuadruples {
    private static long solve(int A, int B, int C, int D) {
        final int MAX = 3000;
        final int MAX_XOR = 4096;

        // Sort A, B, C, D in ascending order
        int[] arr = {A, B, C, D};
        Arrays.sort(arr);
        A = arr[0];
        B = arr[1];
        C = arr[2];
        D = arr[3];


        // total[b] holds the number of pairs {a,b} such that a≤b with 1≤a≤A and 1≤b≤B
        int[] total = new int[MAX + 1];
        for (int a = 1; a <= A; a++) {
            for (int b = a; b <= B; b++) {
                total[b] += 1;
            }
        }
        for (int i = 1; i <= MAX; i++) {
            total[i] += total[i - 1];
        }


        // count[B][x] holds the number of pairs {a,b} such that a≤b and a⊕b=x with 1≤a≤A, 1≤b≤B
        // Note the maximum XOR value we can get is 4096. This is because, 3000 is 12 bits, and maximum value is when all
        // 12 bits are set, which is 2^12 = 4096
        int[][] count = new int[MAX + 1][MAX_XOR + 1];
        for (int a = 1; a <= A; a++) {
            for (int b = a; b <= B; b++) {
                count[b][a ^ b] += 1;
            }
        }
        for (int i = 0; i <= MAX_XOR; i++) {
            for (int b = 1; b <= MAX; b++) {
                count[b][i] += count[b - 1][i];
            }
        }

        long ans = 0;
        for (int c = 1; c <= C; c++) {
            for (int d = c; d <= D; d++) {
                ans += (total[c] - count[c][c ^ d]);
            }
        }

        return ans;
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);


        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        int d = in.nextInt();

        System.out.println(solve(a, b, c, d));
    }
}