Construindo um algoritmo eficiente para “Eliminar o Jogo”

Question

Eu estava resolvendo esse problema do Jogo de Eliminação .

Primeiro, tentei por força bruta;

• eliminou números do início com distância $2$ (ou seja, elemento após o próximo)
• inverteu a lista
• eliminou números do início com distância $2$
• inverteu a lista ...

Finalmente, retornou o último elemento restante. No entanto, não surpreendentemente, isso aumentou "Limite de tempo excedido".

Aqui está o código Python para isso:

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]

Então, procurei uma solução melhor e encontrei o seguinte:

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

e funciona. Isto é matematicamente 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} $$ Eu verifiquei isso para alguns valores de $n$. No entanto, preciso de ajuda para provar que esse algoritmo funciona para todos os casos.

Qualquer ajuda é apreciada.

Answer 1

O primeiro caso $n=1$é obvio. Para o segundo caso, observe que o que você está fazendo é basicamente executar a primeira iteração e resolver o problema no restante (que é$2, 4, 6, ... 2⌊n/2⌋$) - bem, quase. Você faz isso na ordem inversa, é por isso que você tem$⌊n/2⌋-f(⌊n/2⌋)+1$ em vez de $f(⌊n/2⌋)$Aqui, observe que você está realmente retornando a ordem do "último número" e não seu valor, o que seria equivalente no problema original. Portanto, nós multiplicamos por$2$ no final para obter o valor do "último número" do qual sabemos a ordem.