CHEFNUM - Editorial

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 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:

\begin{aligned} Y(a') &= \{0\} \cup \{s \oplus d : s \in Y(a)\} \\\ X(a') &= X(a) \cup Y(a') \end{aligned}

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

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

4 Likes

Hi kevinsogo,

You wrote ans(L,R)=ans(0,R)+ans(0,L−1).

I believe it should be: ans(L,R)=ans(0,R)-ans(0,L−1)

Great editorial :slight_smile:

1 Like

You are right. Fixed. Thank you!

1 Like

Can someone explain this:

A second complication is ensuring that
the numbers we are constructing are
all ≤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.

Suppose N is 2000 and we have 999. When we add 1 at the right it becomes 9991( > N). So why are we only checking for 200(in this case)?
Or I am misunderstanding it entirely?

BTW Nice editorial :slight_smile:

1 Like

In this case, leading zeroes are important. You can look at 999 as 0999. So “0???”, “09??”, “099?” and “0999” are all “<= 2000”.

1 Like

Oh i got it now. I was misunderstanding the recursion. It only computes for values less than N/10. So we will not get cases like 999. we will only values in range[0…200].(in this particular example).

1 Like

I implemented digit-DP in a different fashion: for query [l,r], compute the count of numbers a \in [l,r] such that the amazingness(a) contains a contribution of x \in [0,15] which necessarily enumerates all possible values that can add up to amazingness(\cdot). But I’m getting WA verdict for each one of the test-cases.

Please help: my code | submission. Thanks in advance!