Creación de un algoritmo eficaz para "eliminar el juego"

Aug 17 2020

Estaba resolviendo este problema de Elimination Game .

Primero, lo intenté por fuerza bruta;

  • números eliminados desde el principio con distancia $2$ (es decir, elemento después del siguiente)
  • invirtió la lista
  • números eliminados desde el principio con distancia $2$
  • invirtió la lista ...

Finalmente, devolvió el último elemento restante. Sin embargo, no es sorprendente que esto planteara "Límite de tiempo excedido".

Aquí está el código de Python para esto:

def lastRemaining(n: int) -> int:
        nums = [i for i in range(1, n + 1)]
        l = len(nums)
        while l != 1:
            for i in range(0, len(nums), 1):
                if i < len(nums): 
                    nums.remove(nums[i])
                    l -= 1
            nums.reverse()
        return nums[0]

Luego, busqué una mejor solución y encontré lo siguiente:

def lastRemaining(n: int) -> int:
        if n == 1: return 1
        return (n//2 - lastRemaining(n//2) + 1) * 2

y funciona. Esto está matemáticamente escrito como$$ f(n) = \begin{cases} 1, \text{ if } n=1, \\ 2\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor - f\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor\right) + 1\right), \text{ otherwise } \end{cases} $$ He verificado esto para algunos valores de $n$. No obstante, necesito ayuda para demostrar que este algoritmo funciona en todos los casos.

Se agradece cualquier ayuda.

Respuestas

1 Ekin Aug 17 2020 at 03:21

El primer caso $n=1$es obvio. Para el segundo caso, tenga en cuenta que lo que está haciendo es básicamente ejecutar la primera iteración y resolver el problema en el resto (que es$2, 4, 6, ... 2⌊n/2⌋$) - bueno, casi. Lo haces en orden inverso, por eso tienes$⌊n/2⌋-f(⌊n/2⌋)+1$ en vez de $f(⌊n/2⌋)$Aquí, tenga en cuenta que en realidad está devolviendo el orden del "último número" y no su valor, que sería equivalente en el problema original. Por lo tanto, multiplicamos por$2$ al final para obtener el valor del "último número" cuyo orden conocemos.