KOL1501 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Devendra Agarwal
Tester: Kevin Atienza
Editorialist: Kevin Atienza

PREREQUISITES:

Dynamic programming, long multiplication

PROBLEM:

In an alien world using the base 10 number system, the long multiplication algorithm is the same as Earth’s, except that digit-by-digit multiplication may be different. The results of all 100 digit multiplications are given, and it’s also guaranteed that any digit multiplied by 0 is 0, and multiplication of digits is commutative.

Given A < 10^{100000}, compute the “alien product” of i and j for all pairs (i,j) of integers between 1 and A, inclusive. Output this value modulo M (given as input).

QUICK EXPLANATION:

Let \text{count}(i,x) be the number of numbers between 0 and A whose i th least significant digit is x. Let

F(x) = \sum_{i=0}^{l(A)-1} 10^i \text{count}(x,i)

Then the answer is:

\sum_{x=0}^9 \sum_{y=0}^9 (x\circ y) F(x) F(y)

Where x\circ y denotes alien digit multiplication. \text{count}(x,i) can be computed using the following: (where A_i is the i th least significant digit of A)

\text{count}(x,i) = \begin{cases} \lfloor A / 10^{i+1} \rfloor\cdot 10^i & \text{if $x > A_i$} \\\ \lfloor A / 10^{i+1} \rfloor\cdot 10^i + 10^i & \text{if $x < A_i$} \\\ \lfloor A / 10^{i+1} \rfloor\cdot 10^i + (A \bmod 10^i) + 1 & \text{if $x = A_i$} \end{cases}

Define

A_{\text{div}}(i) = \lfloor A / 10^i \rfloor \bmod M
A_{\text{mod}}(i) = (A \bmod 10^i) \bmod M

The A_{\text{div}}(i) and A_{\text{mod}}(i) values can be precomputed modulo M using the following recurrences:

A_{\text{div}}(i) = (A_{\text{div}}(i+1)\cdot 10 + A_i) \bmod M
A_{\text{mod}}(i) = (A_{\text{mod}}(i-1) + 10^{i-1}A_{i-1}) \bmod M

with base cases A_{\text{div}}(\text{length}(A)) = 0 and A_{\text{mod}}(0) = 0.

EXPLANATION:

In order to distinguish normal multiplication from alien multiplication, we need to use a different notation. Let’s use x \circ y as the notation for “alien multiplication”, while the usual multiplication notations (\times, \cdot, and juxtaposition) will denote normal Earthling multiplication. Thus, the answer is:

\sum_{a=1}^A \sum_{b=1}^A (a \circ b)

Earthling multiplication has a lot of nice properties that alien multiplication doesn’t have, such as:

  • x \cdot (y \cdot z) = (x \cdot y) \cdot z (Associativity)
  • x \cdot (y + z) = (x \cdot z) + (y \cdot z) (Distributivity)
  • x \cdot 1 = x (Identity)

Thus, it seems hard to compute the answer because we can’t seem to do anything sensible. But there are still a few nice properties left:

  • x\circ y = y\circ x (Commutativity)
  • x\circ 0 = 0\circ x = 0

These are properties that hold for all numbers x and y, not just digits.

In addition, the alien “long multiplication” method is very similar to Earthling “long multiplication”. In fact, they are similar enough that we can formulate the following description of the alien product a\circ b of two numbers: (where we denote by l(a) the number of digits of a number a)

  • Let a = (a_{l(a)-1}, a_{l(a)-2}, \ldots, a_1, a_0) be the digits of a in base 10.
  • Let b = (b_{l(b)-1}, b_{l(b)-2}, \ldots, b_1, b_0) be the digits of b in base 10.

Then:

a\circ b = \sum_{i=0}^{l(a)-1} \sum_{j=0}^{l(b)-1} (a_i \circ b_j)\cdot 10^{i+j}

We can rearrange this by looping through all values of a_i and b_j (from 0 to 9):

\begin{aligned} \sum_{i=0}^{l(a)-1} \sum_{j=0}^{l(b)-1} (a_i \circ b_j)10^{i+j} &= \sum_{x=0}^9 \sum_{y=0}^9 \sum_{\substack{i=0 \\\ a_i=x}}^{l(a)-1} \sum_{\substack{j=0 \\\ b_j=y}}^{l(b)-1} (x\circ y)\cdot 10^{i+j} \\\ &= \sum_{x=0}^9 \sum_{y=0}^9 (x\circ y) \sum_{\substack{i=0 \\\ a_i=x}}^{l(a)-1} \sum_{\substack{j=0 \\\ b_j=y}}^{l(b)-1} 10^{i+j} \\\ &= \sum_{x=0}^9 \sum_{y=0}^9 (x\circ y) \sum_{\substack{i=0 \\\ a_i=x}}^{l(a)-1} \sum_{\substack{j=0 \\\ b_j=y}}^{l(b)-1} 10^i 10^j \\\ &= \sum_{x=0}^9 \sum_{y=0}^9 (x\circ y) \left(\sum_{\substack{i=0 \\\ a_i=x}}^{l(a)-1} 10^i \right)\cdot \left(\sum_{\substack{j=0 \\\ b_j=y}}^{l(b)-1} 10^j\right) \end{aligned}

This is the result of a single alien multiplication. But we want to sum all such results among all pairs. Thankfully, the alient product (x\circ y) has been moved away from the inner sum, so the problem looks much easier now.

Let’s define S(x,y) as the inner sum, summed across all possible values a and b:

S(x,y) = \sum_{a=0}^A \sum_{b=0}^A \left(\sum_{\substack{i=0 \\\ a_i=x}}^{l(a)-1} 10^i \right)\cdot \left(\sum_{\substack{j=0 \\\ b_j=y}}^{l(b)-1} 10^j\right)

We included the cases a = 0 and b = 0. This is okay because the alien product of 0 with anything is 0 anyway. But this will help us later on.

Thus, the final answer is now:

\sum_{x=0}^9 \sum_{y=0}^9 (x\circ y) S(x,y)

Our goal now is to compute S(x,y) for all digits x and y. Let’s fix x and y. Notice that:

\begin{aligned} S(x,y) &= \sum_{a=0}^A \sum_{b=0}^A \left(\sum_{\substack{i=0 \\\ a_i=x}}^{l(a)-1} 10^i \right)\cdot \left(\sum_{\substack{j=0 \\\ b_j=y}}^{l(b)-1} 10^j\right) \\\ &= \left(\sum_{a=0}^A \sum_{\substack{i=0 \\\ a_i=x}}^{l(a)-1} 10^i \right)\cdot \left(\sum_{b=0}^A \sum_{\substack{j=0 \\\ b_j=y}}^{l(b)-1} 10^j\right) \end{aligned}

If we define F(x) as the following:

F(x) = \sum_{a=0}^A \sum_{\substack{i=0 \\\ a_i=x}}^{l(a)-1} 10^i

Then we can substitute this above to get:

S(x,y) = F(x)F(y)

Thus, all we have to do now is compute F(x) for all digits x. Now it really seems we’re getting somewhere!

Let’s swap the summation for F(x):

\begin{aligned} F(x) &= \sum_{a=0}^A \sum_{\substack{i=0 \\\ a_i=x}}^{l(a)-1} 10^i \\\ &= \sum_{i=0}^{l(A)-1} \sum_{\substack{a=0 \\\ a_i=x}}^A 10^i \\\ &= \sum_{i=0}^{l(A)-1} 10^i \sum_{\substack{a=0 \\\ a_i=x}}^A 1 \end{aligned}

The inner sum is just the number of numbers between 0 and A whose i th least significant digit is x. Let’s define \text{count}(x,i) to be this number, so that:

F(x) = \sum_{i=0}^{l(A)-1} 10^i \text{count}(x,i)

and we now want to compute \text{count}(x,i) for each digit x and each position i. How many ways can you construct a number a between 0 and A such that the i th digit from the last is x?

Let’s count the number of ways to choose the other digits of a (since we know that a_i must be x). One necessary condition is that the number represented by the digits (a_{l(A)-1}, a_{l(A)-2}, \ldots, a_{i+1}) must not be greater than (A_{l(A)-1}, A_{l(A)-2}, \ldots, A_{i+1}). There are two remaining cases:

  • In the first case, (a_{l(A)-1}, a_{l(A)-2}, \ldots, a_{i+1}) is less than (A_{l(A)-1}, A_{l(A)-2}, \ldots, A_{i+1}). In this case, it doesn’t matter what the remaining digits are, because a is already less than A. Thus, there are 10^i ways to choose the digits less significant than a_i, and there are \lfloor A / 10^{i+1} \rfloor ways to choose the digits more significant than a_i. Thus, there are \lfloor A / 10^{i+1} \rfloor\cdot 10^i numbers in this case.

  • In the second case, (a_{l(A)-1}, a_{l(A)-2}, \ldots, a_{i+1}) is equal (A_{l(A)-1}, A_{l(A)-2}, \ldots, A_{i+1}). Here we can essentially ignore the digits more significant than a_i. Now, if x > A_i, then a already becomes > A regardless of the choice of other digits, so it must be the case that x \le A_i. There are two sub-cases:

    • If x < A_i, then a is already < A, so we can choose the lower-order digits anyway we want. There are 10^i choices for those digits.
    • If x = A_i, then the digits (a_{i-1}, a_{i-2}, \ldots a_0) must be at most (A_{i-1}, A_{i-2}, \ldots A_0). There are at most (A \bmod 10^i) + 1 ways to choose these digits.

Thus, by combining all cases together, we now have a formula for \text{count}(x,i):

\text{count}(x,i) = \begin{cases} \lfloor A / 10^{i+1} \rfloor\cdot 10^i & \text{if $x > A_i$} \\\ \lfloor A / 10^{i+1} \rfloor\cdot 10^i + 10^i & \text{if $x < A_i$} \\\ \lfloor A / 10^{i+1} \rfloor\cdot 10^i + (A \bmod 10^i) + 1 & \text{if $x = A_i$} \end{cases}

Finally, these numbers are very large so we need to compute them modulo M. For 0 \le i < l(A), let’s define:

A_{\text{div}}(i) = \lfloor A / 10^i \rfloor \bmod M
A_{\text{mod}}(i) = (A \bmod 10^i) \bmod M

Substituting these to the formula for \text{count}(x,i), we get:

\text{count}(x,i) = \begin{cases} A_{\text{div}}(i+1) \cdot 10^i & \text{if $x > A_i$} \\\ A_{\text{div}}(i+1) \cdot 10^i + 10^i & \text{if $x < A_i$} \\\ A_{\text{div}}(i+1) \cdot 10^i + A_{\text{mod}}(i) + 1 & \text{if $x = A_i$} \end{cases}

But the $A_{\text{div}}(i)$s and $A_{\text{mod}}(i)$s can be computed with dynamic programming using the following recurrences (straightforward to prove):

A_{\text{div}}(i) = (A_{\text{div}}(i+1)\cdot 10 + A_i) \bmod M
A_{\text{mod}}(i) = (A_{\text{mod}}(i-1) + 10^{i-1}A_{i-1}) \bmod M

with base cases A_{\text{div}}(l(A)) = 0 and A_{\text{mod}}(0) = 0.

This gives us a linear-time algorithm to compute the answer!

  • Compute the $A_{\text{div}}(i)$s and $A_{\text{mod}}(i)$s.
  • Compute the $\text{count}(x,i)$s, modulo M.
  • Compute the $F(x)$s, modulo M.
  • Compute the $S(x,y)$s, modulo M.
  • Finally, compute the final answer using the S(x,y) values.

Time Complexity:

O(\log A) (note that A has approximately \log_{10} A + 1 digits)

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

1 Like