Editorial for Números Balanceados.

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: aniervs

Programación dinámica

Si $f(n)$ ~f(n)~ es la respuesta para al rango $[1, n]$ ~[1, n]~, entonces la respuesta para el rango $[a, b]$ ~[a, b]~ es $f(b) - f(a-1)$ ~f(b) - f(a-1)~, así que concentrémonos en computar $f(n)$ ~f(n)~.

En lugar de contar los números menores o iguales a $n$ ~n~, tratemos de contar los números de longitud $t$ ~t~. Este es un problema relativamente más fácil. Si tenemos un número de longitud $t$ ~t~, podemos agregar algún otro dígito al final, y volverlo de longitud $t + 1$ ~t + 1~. Es posible que al agregar un dígito, el número formado deje de ser balanceado, pero se puede corregir más adelante agregando más dígitos. Entonces, como para construir números balanceados de longitud $t$ ~t~, necesitamos números no balanceados de longitud menor que $t$ ~t~, requerimos más información que solamente la cantidad de cifras. Necesitamos saber para cada dígito del 0 al 9, si:

se repite 0 veces,
se repite una cantidad par de veces, o
se repite una cantidad impar de veces

Esto se puede representar con números en el sistema ternario. Digamos que $mask$ ~mask~ representa cierto número $x$ ~x~. Analicemos el dígito $i$ ~i~ de $mask$ ~mask~ en ternario, para cada $i \in [0, 9]$ ~i \in [0, 9]~. Si el dígito $i$ ~i~ es $2$ ~2~ entonces podemos considerar de que $i$ ~i~ aparece $0$ ~0~ veces en $x$ ~x~. Si es $1$ ~1~ podemos considerar de que $i$ ~i~ aparece una cantidad impar de veces en $x$ ~x~, y si es $0$ ~0~ podemos considerar que aparece una cantidad par de veces.

Entonces, podemos usar programación dinámica sobre los estados $(t, mask)$ ~(t, mask)~. Sea $dp(t, mask)$ ~dp(t, mask)~ la cantidad de números de $t$ ~t~ cifras, y que son descritos por $mask$ ~mask~ en ternario. Del estado $(t, mask)$ ~(t, mask)~ se puede ir directamente al estado $(t + 1, mask')$ ~(t + 1, mask')~ donde $mask'$ ~mask'~ es cualquiera de las máscaras resultantes de agregar un dígito al final de un número descrito por $mask$ ~mask~.

Eficiencia:

$t \le 20$ ~t \le 20~
$mask < 3^{10}$ ~mask < 3^{10}~
de cada $mask$ ~mask~, hay a lo más 10 posibles $mask'$ ~mask'~ resultantes al agregar un nuevo dígito, porque por cada dígito $i \in [0, 9]$ ~i \in [0, 9]~, hay una única opción (de 2 pasa a 1, de 1 pasa a 0, y de 0 pasa a 1).
Entonces, hay alrededor de $200 \cdot 3^{10}$ ~200 \cdot 3^{10}~ transiciones, lo cual es eficiente.

Digit-DP:

¿Cómo usamos $dp(t, mask)$ ~dp(t, mask)~ para computar $f(n)$ ~f(n)~? Bueno, para cada $mask$ ~mask~ que corresponda a números balanceados, podemos añadir a la solución $dp(t, mask)$ ~dp(t, mask)~, para cada $t$ ~t~ estrictamente menor que la cantida de cifras de $n$ ~n~. Para computar la cantidad de números balanceados con la misma cantidad de cifras de $n$ ~n~, usaremos el siguiente algoritmo:

s := decimal representation of n from the most significant digit to the least significant digit
t = length(s)
for i in [0, t-1]:
    for j in [0, s[i] - 1]:
        mask_1 := mask describing the number formed by the prefix [0, i-1] on s
        for each mask_2 such that mask_2 united to mask_1 describe a balanced number: 
            ans += dp[t - i - 1][mask_2]

if n is balanced:
    ans += 1

Comments

There are no comments at the moment.