# Beautiful quadruples challenge

**Problem statement**

We call an quadruple of positive integers, , beautiful if the following condition is true:

Note: is the bitwise XOR operator.

Given and , count the number of beautiful quadruples of the form where the following constraints hold:

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 and should be considered as same.

**Input Format**

A single line with four space-separated integers describing the respective values of and .

**Constraints**

**Output Format**

Print the number of beautiful quadruples.

**Sample Input**

1 |
1 2 3 4 |

**Sample Output**

1 |
11 |

**Explanation**

There are beautiful quadruples for this input:

Thus, we print as our output.

Note that is same as .

**Solution**

Since the order of the integers in a quadruple does not matter we can sort our input values such that :

1 2 3 4 5 6 |
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 . For that we define the following arrays:

`total = new int[3001]`

: `total[B]`

holds the number of pairs such that with and :

1 2 3 4 5 6 7 8 9 10 |
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 such that and with and :

1 2 3 4 5 6 7 8 9 10 11 12 |
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 since (12 bits).

We can now go ahead and use `total`

and `count`

to find our solution. Remember we sorted our so that we count our quadruples such that .

For the second half of we have with and . Let . We know that if . We know that we have a total of `total[c]`

pairs with and . We want to exclude the pairs that have . There are `count[c][y]`

pairs that combined with result to . So from `total[c]`

we have to exclude `count[c][y]`

and do this for all possible and :

1 2 3 4 5 6 |
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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
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)); } } |