Encontrar una prueba o un contraejemplo en un rompecabezas de programación

Question

Hace unos años me presenté a un concurso de programación y éste era uno de los problemas: Abuela binaria

Resumen : Dado un número entero positivo N encuentre 2 enteros positivos tales que $$ x + y = N $$ Sea X y Y sea el número de bits fijados en la representación de base 2 de x e y respectivamente (peso Hamming de x e y). Maximizar X + Y .

Por alguna razón tuve dificultades al principio en python(sobre todo porque estaba usando un algoritmo estúpido que era demasiado lento con N grandes) así que decidí intentar resolverlo usando Haskell. Finalmente logré resolverlo de alguna manera con muy buen rendimiento con este código Haskell:

import IO
import Control.Monad

read_number_of_cases :: IO Integer

read_number_of_cases = do
    s <- getLine
    let number_of_cases = read s :: Integer
    return number_of_cases

main :: IO ()

main = do
    hSetBuffering stdin LineBuffering
    number_of_cases <- read_number_of_cases
    forM_ [1..number_of_cases] (\i -> do
        line <- getLine
        let number = read line :: Integer
            a000120 0 = 0
            a000120 n = a000120 n' + m where (n', m) = divMod n 2
            middle = if even number
                     then truncate(toRational(number)/2)::Integer
                     else truncate(toRational(number)/2)::Integer
            max_p1 = if (a000120 middle)>=(truncate(logBase 2 (fromIntegral middle))+1)
                     then middle
                     else truncate(2**fromIntegral(truncate(logBase 2 (fromIntegral middle)))-1)
            max_p2 = if (a000120 number)>=(truncate(logBase 2 (fromIntegral number))+1)
                     then number
                     else truncate(2**fromIntegral(truncate(logBase 2 (fromIntegral number)))-1)
            result = if max_p1 > max_p2
                     then a000120(max_p1) + a000120(number - max_p1)
                     else a000120(max_p2) + a000120(number - max_p2)
        putStrLn ("Case #"++show i++": "++(show result)))`

(A000120 calcula el peso Hamming https://oeis.org/A000120 )

Lo que hace este código es: $$ middle = \left\lfloor {\frac{N}{2}} \right\rfloor\\ max_{p1}=\begin{cases} middle,& \text{if } Hamming(middle)\geq \left\lfloor log_2(middle) \right\rfloor + 1\\ \left\lfloor 2^{ \left\lfloor (log_2(middle) )\right\rfloor}-1 \right\rfloor, & \text{otherwise} \end{cases}\\ max_{p2}=\begin{cases} middle,& \text{if } Hamming(N)\geq \left\lfloor log_2(N) \right\rfloor + 1\\ \left\lfloor 2^{ \left\lfloor (log_2(N) )\right\rfloor}-1 \right\rfloor, & \text{otherwise} \end{cases}\\ result=\begin{cases} Hamming(max_{p1})+Hamming(N-max_{p1}),& \text{if } max_{p1} \gt max_{p2} \\ Hamming(max_{p2})+Hamming(N-max_{p2}), & \text{otherwise} \end{cases} $$

Eso funcionó, pero para ser honesto no tengo ni idea de por qué, o si funcionaría para todos los casos. Así que la pregunta es: ¿Hay una manera fácil de demostrar que es correcto? ¿O incorrecta si es el caso?

Answer 1

Quizá sea mejor utilizar las matemáticas en lugar de la potencia de cálculo. Si $N=2M+1$ es impar, entonces exactamente uno de $x,y$ debe ser impar y no hay carry en el bit menos significativo, es decir, la suma de pesos máxima de $x$ y $y$ para $N$ es exactamente uno más que para $M$ . Si $N =2M$ es incluso hay dos posibilidades para nuestro óptimo $x$ y $y$ : Cualquiera $x,y$ son pares y $x/2, y/2$ son óptimas para $M$ o $x,y$ son impar y $(x-1)/2$ , $(y-1)/2$ (que tienen un bit menos cada una) son óptimas para $M-1$ (ver el carry). Concluimos que $$\tag1 f(N)=\begin{cases}2&\text{if $N=2$ or $N=3$}\\f(\tfrac {N-1}2)+1&\text{if $N>3$ is odd}\\ \max\{f(\tfrac {N}2),f(\tfrac{N-2}2)+2\}&\text{if $N>3$ is even}\end{cases}$$ Esto ya es una buena forma de abordar el problema con la programación dinámica. Pero el máximo en el último caso se ve feo.

Proposición. $f(n+1)\le f(n)+1$ para todos $n\ge 2$ .

Prueba. Sea $n+1=x+y$ sea una descomposición de suma de pesos máxima de $n+1$ . Entonces wlog $x\ge 2$ (como $n+1\ge 3$ ), y el peso de $x-1$ está limitada por $\operatorname{wt}(x-1)\ge \operatorname{wt}(x)-1$ Por lo tanto $f(n)\ge\operatorname{wt}(x-1)+\operatorname{wt}(y)\ge \operatorname{wt}(x)+\operatorname{wt}(y)=f(n)$ . $_\square$

A partir de la proposición podemos simplificar $(1)$ a $$\tag2 f(N)=\begin{cases}2&\text{if $N=2$ or $N=3$}\\f(\tfrac {N-1}2)+1&\text{if $N>3$ is odd}\\ f(\tfrac{N-2}2)+2&\text{if $N>3$ is even}\end{cases}$$ Esto proporciona un método para calcular $f(N)$ en $O(\log(N))$ pasos. De hecho, se puede observar una fórmula simple que utiliza sólo la longitud de bit de $N-1$ y el peso Hamming de $N-1$ . Véase también A014701