PROBLEM LINK:
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
so after rearranging, we have
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 vals, 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 Cs
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:
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 Cs 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
