Editorial for UTS Open '18 P6 - Subset Sum

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: PlasmaVortex

Subtask 1

The condition A \subseteq X \subseteq B is equivalent to (a \mathbin{\&} x) = a and (b \mathbin{\&} x) = x, which can be checked on \mathcal{O}(1) time (here, \& denotes the bitwise AND operation). For each type 2 query, we can loop through all 2^N subsets and add its value to the total if it satisfies this condition.

Time Complexity: \mathcal{O}(Q\cdot 2^N)

Subtask 2

If we treat the 2^N identifiers as vertices of an N-dimensional hypercube, we can create an N-dimensional prefix sum array in \mathcal{O}(N\cdot 2^N) by calculating a prefix sum in each dimension. More specifically, for each i (0 \le i < N), for all integers x with i^{th} bit 0, add arr[x] to arr[x + 2^i]. Now arr[a] will be the sum of the values of all X such that X \subseteq A.

Split the queries into \sqrt{Q} blocks of size \sqrt{Q}. At the start of each block, initialize the prefix sum array as above. Keep a list of the updates that have occurred, and when querying a set A, return arr[a] with adjustments for any set X \subseteq A whose value was updated (there are at most \sqrt{Q} of them if you reset the list of updates each block).

Time Complexity: \mathcal{O}((N\cdot 2^N+Q)\sqrt{Q})

Subtask 3

Let x[i] denote the i^{th} bit of x. For each query (A, B), we need (a \mathbin{\&} b) = a, otherwise the answer to the query would be 0. This means there are 3 possibilities for (a[i], b[i]): either (0,0), (0,1), or (1,1). Let x_1 and x_2 be the first and second halves of the binary representation of an integer x. We can 'join' the a_1 and b_1 to get a ternary number \text{join}(a_1, b_1), where the i^{th} digit of \text{join}(a_1, b_1) is 0 if (a_1[i], b_1[i]) = (0, 0), 1 if (a_1[i], b_1[i]) = (0, 1), or 2 if (a_1[i], b_1[i]) = (1, 1). Similarly, we can convert back, going from any N/2-digit ternary integer c to a corresponding pair of N/2-bit integers a and b, with (a \mathbin{\&} b) = a and \text{join}(a, b) = c.

Now, define the array arr[c][d_2] as the sum of the values of all N-bit integers d, whose second half (in binary) is d_2, and whose first half d_1 satisfies (a \mathbin{\&} d_1) = a and (b \mathbin{\&} d_1) = d_1, where a and b are the pair of integers such that (a \mathbin{\&} b) = a and \text{join}(a, b) = c. When the value of s changes by v, we can update this array in \mathcal{O}(2^{N/2}) by adding v to arr[\text{join}(a, b)][s_2], for all a, b such that (a \mathbin{\&} s_1) = a and (b \mathbin{\&} s_1) = s_1 (there are exactly 2^{N/2} such pairs a, b). To answer the query (a, b), we add up arr[\text{join}(a_1, b_1)][x_2] for all x_2 such that (a_2 \mathbin{\&} x_2) = a_2 and (b_2 \mathbin{\&} x_2) = x_2, which is also \mathcal{O}(2^{N/2}). Note that we can precalculate \text{join}(a, b) in \mathcal{O}(N\cdot 3^{N/2}), and array arr can be efficiently initialized in \mathcal{O}(6^{N/2}) (alternatively, you can initialize with all 0's and update 2^N times).

Time Complexity: \mathcal{O}(Q\cdot 2^{N/2} + 6^{N/2})


There are no comments at the moment.