APAIRS - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Foyaz Akanda
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov

DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Brute-force, probability theory, digit dp
PROBLEM:
You’re given [L,R] segment and you need to calculate \sum\limits_{x=L}^R \sum\limits_{y=L}^R score(x,y) where score(x,y) is defined in the following way (assuming x = x_0 + 10 \cdot x_1 + 10^2 \cdot x_2 + \dots):

  • Make x and y of the same length by adding leading zeroes to the smaller number,
  • Reorder digits of y in such a way that s=|x_0-y_0| + |x_1-y_1| + \dots is minimized,
  • score(x,y)=s, where s is obtained on the previous step.

QUICK EXPLANATION:
Optimal digit reordering is the greedy one. To find actual answer, reduce initial problem to the case of some prefix sums and then utilize basic probability theory.
EXPLANATION:
Digits in numbers x and y must be ordered in the same way to minimize the score. Indeed, assume that x_a \leq x_b but y_a \geq y_b. Then |x_a - y_a|+|x_b - y_b| \geq |x_a - y_b| + |x_b - y_a|, so swapping y_a and y_b will never make your answer worse and you may keep continue doing it until they’re sorted in the same order. For this case this inequality may be quickly checked via brute-force by iterating all possible quadruples if (x_a, y_a, x_b, y_b), but seems that it holds in general case as well.

Now let’s continue simplifying the problem. Let sum(A, B) = \sum\limits_{x=0}^A \sum\limits_{y=0}^B score(i,j). Via inclusion-exclusion principle we may obtain that actual answer is as follows:

ans = sum(R, R)-2 \cdot sum(L-1,R)+sum(L-1,L-1)

So, if we may calculate sum(A, B) then we may calculate our answer as well. Let x_{ij} and y_{ij} be the probabilities that digit on i-th position (after sorting) in numbers x and y drawn from [0,A] and [0,B] correspondingly will be equal to j. Then sum(A,B) may be defined as follows:

sum(A, B) = (A+1) \cdot (B+1) \cdot E

Where E is the expected value of score(x,y) for 0 \leq x \leq A and 0 \leq y \leq B, which is:

E=\sum\limits_{i=0}^l \sum\limits_{j=0}^{9} \sum\limits_{k=0}^9 x_{ij} \cdot y_{ik} \cdot |j - k|

Where l is the length of \max(A, B). Only thing left to do is to calculate x_{ij} and y_{ij} effectively. We may get rid of annoying upper bound of A on x by splitting it into some fixed prefix of leading numbers and arbitrary suffix. Let A=a_{l-1} a_{l-2} \dots a_1 a_0. We can fix first t \in [0, l] digits to be equal to a_{l-1} a_{l-2} \dots a_{l-t} and check every possible value of the (t+1)-th digit d drawn in such way that 0 \leq d <a_{l-t-1}. In this way first (t+1) digits will be fixed and remaining l-(t+1) digits will be free to choose and we may use some combinatorics to estimate them. Basically we will have to add the following value to the x_{ij} for each prefix fixed in such way:

x_{ij} \overset{+}{\leftarrow} \frac{10^{l - (t + 1)}}{A+1} \cdot \frac{j^{a} \cdot (10-j-1)^b \cdot 1^c}{10^{l-(t+1)}} \cdot \frac{[l-(t+1)]!}{a!b!c!}

Here a, b and c are chosen in such way that a+b+c=l-(t+1) and number on the i-th position after sorting is going to be equal to j. The first multiplier here stands for the fraction of numbers in [0,A] having first (t+1) digits fixed. The second one stands for the chance of drawing a numbers less than j, b numbers greater than j and c numbers equal to j. The third multiplier corresponds to the number of ways of choosing positions for these draws. One may simply brute-force every pair of a and b checking, which position number j is going to be with them and adding this number to corresponding x_{ij}. In this way this part of prute-force will work in l^2 \cdot 9 while the first one which calculates E should work in l \cdot 9^2 which is fine to get accepted on this problem.

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.