PROBLEM LINK:
Contest
Practice
Author: Prateek Gupta
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic programming, enumeration
PROBLEM:
The amazingness of a number is defined using pseudocode. Given $L$ and $R$, find the sum of the amazingnesses of all integers from $L$ to $R$, inclusive.
QUICK EXPLANATION:
Let $\operatorname{ans}(L,R)$ be the answer. Note that $\operatorname{ans}(L,R) = \operatorname{ans}(0,R) - \operatorname{ans}(0,L-1)$, so we can focus on the case $L = 0$.
Let $\operatorname{digitXOR}(n)$ be the XOR of all digits of $n$. Thus, there are at most $16$ distinct $\operatorname{digitXOR}(n)$s.
Let $f(n)$ be the set of all $\operatorname{digitXOR}$s of all of $n$'s suffixes. There are at most $2^{16}$ distinct $f(n)$s, and this can be represented as a bitmask of $16$ bits.
The amazingness of $n$ is uniquely determined by $f(n)$. Thus, for every distinct possible $f(n)$, we count the number of integers $n \in [0,R]$ with this $f(n)$. These counts can be simultaneously computed recursively.
EXPLANATION:
Let $\operatorname{ans}(L,R)$ be the sum of all amazingnesses of all integers from $L$ to $R$. Notice that
$$\operatorname{ans}(0,R) = \operatorname{ans}(0,L-1) + \operatorname{ans}(L,R)$$
so after rearranging, we have
$$\operatorname{ans}(L,R) = \operatorname{ans}(0,R) - \operatorname{ans}(0,L-1)$$
This reduces a call to $\operatorname{ans}(L,R)$ with two calls to $\operatorname{ans}(L,R)$ with $L = 0$, which is potentially simpler. In fact, let's define $F(N) = \operatorname{ans}(0,N)$, so that $\operatorname{ans}(L,R) = F(R) - F(L-1)$, and from now on, we will focus on computing $F(N)$.
Before going further, we note that the first subtask can be solved without analyzing the "amazingness" function at all. We can just implement the given pseudocode, compute all amazingnesses from $0$ to $10^6$, and then compute cumulative sums. This way, we can get any $F(N)$ we want with just a single lookup!
Unfortunately, this doesn't pass the second subtask because $N$ can now be up to $10^9$. This time, we might need to analyze the "amazingness" function.
Amazingness
Let's analyze the amazingness(a)
function. Looking at the two loops in the code, we see that the variables i
and j
are looping in such a way that they enumerate all substrings of a
.
Now, what does val
do? Looking at how it's calculated, we see that each subsequent digit gets XOR-ed to val
as we loop j
. In fact, if you look carefully, at any time inside the inner loop val
is equal to x[i] ^ x[i+1] ^ ... ^ x[j]
, where ^
is the XOR operator! In other words, val
loops through all XORs of all substrings of digits of a
, and the following snippet of code will be run for each such val
:
if (val not present in set s before) {
ans += val;
add val to set s
}
So let's analyze this if
statement. This basically adds val
to a cumulative sum called ans
, but only if val
is not found in the set s
yet. If it's found in s
, then it's ignored. Otherwise, it's added to ans
and then added to the set s
also. In other words, after looping through all val
s, ans
becomes the sum of all distinct values of val
. Since ans
is the return value, we now have a better understanding of what amazingness(a)
is:
The amazingness of $a$ is the sum of all distinct XORs of substrings of digits of $a$.
Computing $F(N)$
Let's now try to compute $F(N)$. Recall that it's defined as the sum of the amazingnesses of all integers $\le N$. But we can use our understanding of amazingness
above to help us do this efficiently.
First, note that every decimal digit has at most four bits. This means that val
, being the XOR of digits, can only have at most four bits too! Thus, we discover that 0 <= val < 16
.
Next, notice that the amazingness of $a$ is uniquely determined by the set of all XORs of substrings of digits of $a$. Let's call this set $a$'s XOR-set, and denote it as $X(a)$. But since each XOR is $< 16$, every XOR-set must be a subset of $\{0, 1, 2, \ldots, 15\}$, which means there are only $2^{16}$ distinct XOR-sets. And if we can count how many $a$s correspond to each XOR-set that are $\le N$, we can compute $F(N)$ easily.
To understand better, see the following pseudocode. Note that $S$ is the XOR-set, and is represented as a bitmask of $16$ bits, which is just an integer from $0$ to $2^{16} - 1$.
def F(N):
result = 0
for S = 0..2^16-1:
Let C = number of a's such that a <= N and X(a) = S
// compute amazingness
amazing = 0
for val = 0..15:
if (S & (1<<val)) != 0:
amazing += val
// update result
result += C * amazing
return result
If we have the C
values already, this runs in a fixed amount of operations, so this passes the time limit as long as we can compute each required C
efficiently. So we will describe that in the following sections.
Computing C
s
For each XOR-set $S \subset \{0, 1, 2, \ldots, 15\}$, we want to count the number of $a$s such that $a \le N$ and $X(a) = S$. Let's denote this count by $C[S]$. Here, we'll try to count all $C[S]$ for all possible XOR-sets simultaneously, not one at a time.
Let's try computing the $C$ values with a dynamic programming procedure, adding one digit at the time from left to right. To do this, we must be able to "update" the XOR-set of a number when we append a digit to the right, and we also need to ensure that the numbers we're constructing doesn't exceed $N$.
There's a problem with this, though. By appending a digit, there isn't enough information to obtain the new XOR-set. Indeed, appending the same digit to two numbers with the same XOR-set may even result in different XOR-sets! Consider for example appending the digit $4$ to the numbers $21$ and $12$. $21$ have $12$ have the same XOR-set: $X(21) = X(12) = \{0, 1, 2, 3\}$. However, $X(214) = \{0, 1, 2, 3, 4, 5, 7\} \not= X(124) = \{0, 1, 2, 3, 4, 6, 7\}$. Clearly, we need to encode more information other than the XOR-set of a number.
The insight is to also store the set of all XORs of suffixes of digits of $a$. Let's call this set $a$'s suffix-XOR-set, and denote this by $Y(a)$. By having both $X(a)$ and $Y(a)$, the updated XOR-set is now uniquely determined when we append a digit to $a$.
Specifically, let $a'$ be the integer when the digit $d$ is appended to the right of $a$, i.e., $a' = 10a + d$. Then:
$$\begin{align*}
Y(a') &= \{0\} \cup \{s \oplus d : s \in Y(a)\} \\\
X(a') &= X(a) \cup Y(a')
\end{align*}$$
where $\oplus$ stands for the bitwise XOR operation.
Unfortunately, the number of distinct $(X(a), Y(a))$ pairs may be very large. To see why, notice that $Y(a)$ is also a subset of $\{0, 1, 2, \ldots, 15\}$ like $X(a)$. Hence, on the surface there seems to be $2^{16}\cdot 2^{16} = 4^{16} \approx 4.3\cdot 10^9$ pairs possible, which is too high. Fortunately, we can reduce this count by noticing that $Y(a)$ is always a subset of $X(a)$. Hence, there are only $3^{16}\approx 4.3\cdot 10^7$ pairs, which is more manageable. (To see why $3^{16}$, notice that for every $\text{val} \in \{0, 1, 2, \ldots, 15\}$, there are only three possibilities: (1) $\text{val}$ is in $X(a)$ and $Y(a)$, (2) $\text{val}$ is in $X(a)$ but not in $Y(a)$, and (3) $\text{val}$ is neither in $X(a)$ nor in $Y(a)$.)
A second complication is ensuring that the numbers we are constructing are all $\le N$. But this is simpler to remedy. Since we are adding digits from left to right, the only time that we can append a digit and then exceed $N$ is when all previously-added digits are equal to their corresponding digits in $N$! This means we simply have to separate the $(X(a), Y(a))$ pair of the number $a$ whose digits are equal to the first few digits of $N$. For everything else, adding a digit will not exceed $N$.
With that in mind, we can now implement our enumeration algorithm, using pseudocode.
def append((X, Y), d):
new_Y = union({0}, {s ^ d for all s in Y})
new_X = union(X, new_Y)
return (new_X, new_Y)
def compute_Cs(N):
(C, XY_last) = _compute_Cs(N)
C[XY_last] += 1
return C
def _compute_Cs(N):
if N == 0:
C = (empty map/dictionary)
XY_last = ({0}, {0})
return (C, XY_last)
else:
prev_C, prev_XY_last = _compute_Cs(N/10)
// compute new 'C'
C = (empty map/dictionary)
for (X, Y) in prev_C.keys():
for d = 0..9:
(new_X, new_Y) = append((X, Y), d)
C[(new_X, new_Y)] += prev_C[(X, Y)]
// try appending small digits to prev_XY_last
last_d = N%10 // last digit of N
for d = 0..last_d-1:
(new_X, new_Y) = append(prev_XY_last, d)
C[(new_X, new_Y)] += 1
// compute new 'XY_last' by appending last_d to prev_XY_last
XY_last = append(prev_XY_last, last_d)
// return the new (C, XY_last)
return (C, XY_last)
Note that {}
denotes sets, so for example {0}
denotes the set containing only the integer $0$. These sets are subsets of $\{0, 1, 2, \ldots, 15\}$, so they can be implemented as bitmasks.
Once we have compute_Cs
, we can now compute F(N)
straightforwardly.
def F(N):
C = compute_Cs(N)
result = 0
for (X, Y) in C.keys():
// compute amazingness
amazing = 0
for val = 0..15:
if X contains val:
amazing += val
// update result
result += C[(X, Y)] * amazing
return result
So what's the running time? There are approximately $\log_{10} N$ calls to _compute_Cs
, and each step requires $3^{16}\cdot 10$ steps. Thus, this might take potentially $3^{16}\cdot 10\cdot \log_{10} N$ steps which is slow for large $N$. But actually the number of keys in C
is very far from $3^{16}$ in practice, so with the right implementation, this could pass the time limit!
Computing C
s better
We can actually improve the previous algorithm by noticing that we don't need to store the whole $(X(a), Y(a))$ pair, because you can compute $X(a)$ just from $Y(a)$!
To see this, note that the XOR of any substring is just the XOR of two suffixes! For example, if you want to compute the XOR of the digits $(N_i, N_{i+1}, \ldots, N_j)$, we just need to XOR the following suffixes: $(N_i, N_{i+1}, \ldots)$ and $(N_{j+1}, N_{j+2}, \ldots)$. This is true because XOR cancels itself, i.e. $x\oplus y\oplus y = x$.
This means that the above can be simplified into the following:
def append(Y, d):
new_Y = union({0}, {s ^ d for all s in Y})
return new_Y
def compute_Cs(N):
(C, Y_last) = _compute_Cs(N)
C[Y_last] += 1
return C
def _compute_Cs(N):
if N == 0:
C = (empty map/dictionary)
Y_last = {0}
return (C, Y_last)
else:
prev_C, prev_Y_last = _compute_Cs(N/10)
// compute new 'C'
C = (empty map/dictionary)
for Y in prev_C.keys():
for d = 0..9:
new_Y = append(Y, d)
C[new_Y] += prev_C[Y]
// try appending small digits to prev_Y_last
last_d = N%10 // last digit of N
for d = 0..last_d-1:
new_Y = append(prev_Y_last, d)
C[new_Y] += 1
// compute new 'Y_last' by appending last_d to prev_Y_last
Y_last = append(prev_Y_last, last_d)
// return the new (C, Y_last)
return (C, Y_last)
def F(N):
C = compute_Cs(N)
result = 0
for Y in C.keys():
// compute X from Y
X = {} // empty set
for v = 0..15:
if Y contains v:
for w = 0..15:
if Y contains w:
X.add(v ^ w)
// compute amazingness
amazing = 0
for val = 0..15:
if X contains val:
amazing += val
// update result
result += C[Y] * amazing
return result
Computing X
from Y
can actually be precomputed so it takes $O(1)$ time during the computation of $F(N)$. Also, with this simplification, and with the fact that $X$ and $Y$ can be represented as a bitmask of $16$ bits, we can now ditch the map/dictionary and just use a regular array!
To see an implementation in C++, see the tester's solution. Note that in this solution, even the append
function has been precomputed, to further optimize.
Time Complexity:
$O(2^k d \log_d b)$ for $k = 16$ and $d = 10$
AUTHOR'S AND TESTER'S SOLUTIONS:
Setter
Tester