Editorial for UTS Open '18 P6 - Subset Sum
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
The condition is equivalent to
and
, which can be checked on
time (here,
denotes the bitwise AND operation). For each type
query, we can loop through all
subsets and add its value to the total if it satisfies this condition.
Time Complexity:
Subtask 2
If we treat the identifiers as vertices of an
-dimensional hypercube, we can create an
-dimensional prefix sum array in
by calculating a prefix sum in each dimension. More specifically, for each
, for all integers
with
bit
, add arr
to arr
. Now arr
will be the sum of the values of all
such that
.
Split the queries into blocks of size
. 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
, return arr
with adjustments for any set
whose value was updated (there are at most
of them if you reset the list of updates each block).
Time Complexity:
Subtask 3
Let denote the
bit of
. For each query
, we need
, otherwise the answer to the query would be
. This means there are
possibilities for
: either
,
, or
. Let
and
be the first and second halves of the binary representation of an integer
. We can 'join' the
and
to get a ternary number
, where the
digit of
is
if
,
if
, or
if
. Similarly, we can convert back, going from any
-digit ternary integer
to a corresponding pair of
-bit integers
and
, with
and
.
Now, define the array arr as the sum of the values of all
-bit integers
, whose second half (in binary) is
, and whose first half
satisfies
and
, where
and
are the pair of integers such that
and
. When the value of
changes by
, we can update this array in
by adding
to arr
, for all
such that
and
(there are exactly
such pairs
). To answer the query
, we add up arr
for all
such that
and
, which is also
. Note that we can precalculate
in
, and array arr can be efficiently initialized in
(alternatively, you can initialize with all
's and update
times).
Time Complexity:
Comments