algorithm - guia - ¿Cómo contar enteros entre A y B grandes con una propiedad determinada?

qgis manual

Question

En los concursos de programación, el siguiente patrón ocurre en muchas tareas:

Dados los números A y B que son enormes (quizás 20 dígitos decimales o más), determine el número de enteros X con A ≤ X ≤ B que tienen cierta propiedad P

SPOJ tiene muchas tareas como estas para la práctica.

Donde ejemplos de propiedades interesantes incluyen:

• "la suma de dígitos de X es 60"
• "X consiste solo en los dígitos 4 y 7"
• "X es palindrómica", lo que significa que la representación decimal de X es igual a su inverso (por ejemplo, X = 1234321)

Sé que si definimos f (Y) como el número de tales enteros X ≤ Y, entonces la respuesta a nuestra pregunta es f (B) - f (A - 1) . El problema reducido es cómo calcular la función f de manera eficiente. En algunos casos, podemos hacer uso de ciertas propiedades matemáticas para elaborar una fórmula, pero a menudo las propiedades son más complicadas y no tenemos tiempo suficiente para eso en un concurso.

¿Existe un enfoque más general que funcione en muchos casos? ¿Y también se puede usar para enumerar los números con la propiedad dada o calcular alguna agregación en ellos?

Una variación de esto es encontrar el número k-th con una propiedad dada, que por supuesto puede resolverse utilizando la búsqueda binaria junto con una función de conteo.

Answer 1

De hecho, hay una aproximación a este patrón que resulta funcionar bastante a menudo. También se puede usar para enumerar todas las X con la propiedad dada, siempre que su número sea razonablemente pequeño. Incluso puede usarlo para agregar algún operador asociativo sobre toda la X con la propiedad dada, por ejemplo, para encontrar su suma.

Para entender la idea general, intentemos formular la condición X ≤ Y en términos de las representaciones decimales de X e Y.

Digamos que tenemos X = x ₁ x ₂ ... x _{n - 1} x _n e Y = y ₁ y ₂ ... y _{n - 1} y _n , donde x _i y y _i son los dígitos decimales de X e Y. Si los números tienen una longitud diferente, siempre podemos agregar cero dígitos al frente del más corto.

Definamos leftmost_lo como el i más pequeño con x _i <y _i . Definimos leftmost_lo como n + 1 si no existe tal i . De manera análoga, definimos leftmost_hi como el i más pequeño con x _i > y _i , o n + 1 de lo contrario.

Ahora X ≤ Y es verdadero si y exactamente si leftmost_lo <= leftmost_hi . Con esa observación, es posible aplicar un enfoque de programación dinámica al problema, que "establece" los dígitos de X uno tras otro. Demostraré esto con sus problemas de ejemplo:

Calcule el número f (Y) de los enteros X con la propiedad X ≤ Y y X tiene la suma de dígitos 60

Sea n el número de dígitos de Y e y[i] el dígito decimal número i de Y según la definición anterior. El siguiente algoritmo recursivo resuelve el problema:

count(i, sum_so_far, leftmost_lo, leftmost_hi):
    if i == n + 1:
        # base case of the recursion, we have recursed beyond the last digit
        # now we check whether the number X we built is a valid solution
        if sum_so_far == 60 and leftmost_lo <= leftmost_hi:
            return 1
        else: 
            return 0
    result = 0
    # we need to decide which digit to use for x[i]
    for d := 0 to 9
        leftmost_lo'' = leftmost_lo
        leftmost_hi'' = leftmost_hi
        if d < y[i] and i < leftmost_lo'': leftmost_lo'' = i
        if d > y[i] and i < leftmost_hi'': leftmost_hi'' = i
        result += count(i + 1, sum_so_far + d, leftmost_lo'', leftmost_hi'')
    return result

Ahora tenemos f(Y) = count(1, 0, n + 1, n + 1) y hemos resuelto el problema. Podemos agregar memoization a la función para hacerlo rápido. El tiempo de ejecución es O (n ⁴ ) para esta implementación en particular. De hecho, podemos optimizar inteligentemente la idea para convertirla en O (n) . Esto se deja como un ejercicio para el lector (Sugerencia: puede comprimir la información almacenada en leftmost_lo y leftmost_hi en un solo bit y puede podar si sum_so_far > 60 ). La solución se puede encontrar al final de este post.

Si observa atentamente, sum_so_far aquí es solo un ejemplo de una función arbitraria que calcula un valor de la secuencia de dígitos de X. Podría ser cualquier función que pueda calcularse dígito a dígito y arroje un resultado lo suficientemente pequeño. Podría ser el producto de dígitos, una máscara de bits del conjunto de dígitos que cumplen una determinada propiedad o muchas otras cosas.

También podría ser simplemente una función que devuelve 1 o 0, dependiendo de si el número está formado únicamente por los dígitos 4 y 7, que resuelve el segundo ejemplo de forma trivial. Tenemos que ser un poco cuidadosos aquí porque se nos permite tener ceros iniciales al principio, por lo que debemos llevar un bit adicional a través de las llamadas a la función recursiva que nos dicen si todavía podemos usar el cero como un dígito.

Calcule el número f (Y) de los enteros X con la propiedad X ≤ Y y X es palindrómica

Este es un poco más duro. Debemos tener cuidado con los ceros iniciales: el punto de espejo de un número palindrómico depende de la cantidad de ceros iniciales que tengamos, por lo que deberíamos hacer un seguimiento del número de ceros iniciales.

Sin embargo, hay un truco para simplificarlo un poco: si podemos contar f (Y) con la restricción adicional de que todos los números X deben tener el mismo dígito que Y, también podemos resolver el problema original, iterando sobre Todos los dígitos posibles cuentan y suman los resultados.

Así que podemos asumir que no tenemos ningún cero inicial:

count(i, leftmost_lo, leftmost_hi):
    if i == ceil(n/2) + 1: # we stop after we have placed one half of the number
        if leftmost_lo <= leftmost_hi:
            return 1
        else: 
            return 0
    result = 0
    start = (i == 1) ? 1 : 0    # no leading zero, remember?
    for d := start to 9
        leftmost_lo'' = leftmost_lo
        leftmost_hi'' = leftmost_hi
        # digit n - i + 1 is the mirrored place of index i, so we place both at 
        # the same time here
        if d < y[i]     and i     < leftmost_lo'': leftmost_lo'' = i
        if d < y[n-i+1] and n-i+1 < leftmost_lo'': leftmost_lo'' = n-i+1
        if d > y[i]     and i     < leftmost_hi'': leftmost_hi'' = i
        if d > y[n-i+1] and n-i+1 < leftmost_hi'': leftmost_hi'' = n-i+1
        result += count(i + 1, leftmost_lo'', leftmost_hi'')
    return result

El resultado será nuevamente f(Y) = count(1, n + 1, n + 1) .

ACTUALIZACIÓN: Si no solo queremos contar los números, sino que tal vez los enumeremos o calculemos a partir de ellos una función agregada que no exponga la estructura del grupo, también debemos aplicar el límite inferior en X durante la recursión. Esto añade unos cuantos parámetros más.

ACTUALIZACIÓN 2: O (n) Solución para el ejemplo de "suma de dígitos 60":

En esta aplicación colocamos los dígitos de izquierda a derecha. Ya que solo nos interesa si leftmost_lo < leftmost_hi es verdadero, agreguemos un nuevo parámetro lo . lo es verdadero iif leftmost_lo leftmost_lo < i y false en caso contrario. Si lo es verdadero, podemos usar cualquier dígito para la posición i . Si es falso, solo podemos usar los dígitos 0 a Y [i], ya que cualquier dígito más grande causaría leftmost_hi = i < leftmost_lo y por lo tanto no puede conducir a una solución. Código:

def f(i, sum_so_far, lo):
    if i == n + 1: return sum_so_far == 60
    if sum_so_far > 60: return 0
    res = 0
    for d := 0 to (lo ? 9 : y[i]):
         res += f(i + 1, sum + d, lo || d < y[i])
    return res

Podría decirse que esta forma de verlo es algo más simple, pero también un poco menos explícita que el enfoque leftmost_lo / leftmost_hi . Tampoco funciona de inmediato para escenarios algo más complicados como el problema del palíndromo (aunque también se puede usar allí).