Blogaritmo natural

Voy a explicar mi solución al problema 562 - Dividing coins del juez de Valladolid.

El problema: Hay varias monedas sobre una mesa. Queremos repartir este dinero entre dos personas. ¿Cuál es la mínima diferencia posible que se puede formar al dividir las monedas en dos grupos? O en otras palabras, ¿Con cuánto más va a quedar la persona que tenga más plata si repartimos las monedas de la manera más justa posible?

La solución: La solución final utiliza programación dinámica. El código en C++ está al final.

En lo primero que pensé fue un algoritmo greedy que en cada paso intentara agregar la moneda más pequeña al grupo con menos acumulado. ¡Pero no funciona! Por ejemplo, con el conjunto de monedas {200, 200, 500} el algoritmo intentaría agregar primero una moneda de 200 a un grupo. Después agregaría la otra de 200 al otro grupo y finalmente la de 500 a cualquiera de los grupos, dejando una diferencia de 500. Sin embargo, es mejor agregar las 2 de 200 a un grupo y la de 500 a otro, dejando una diferencia de 100.

Después pensé en intentar construir la solución basándome en subproblemas más pequeños. ¿Si conozco la mejor manera de repartir las primeras i monedas, puedo conocer a cuál de los dos grupos agregar la móneda (i+1)-ésima para encontrar la mejor manera de dividir las primeras i+1 monedas? Y la verdad… ¡tampoco funciona! Con el mismo ejemplo anterior, la mejor manera de repartir las primeras 2 monedas es darle una de 200 a cada grupo. Sin embargo, al intentar agregar la de 500, no voy a encontrar la solución óptima. Hmm…

El problema es que en las ideas anteriores no estaba considerando el caso en que sea mejor agregar una moneda a un grupo aumentando la diferencia que ya se tiene para que después se agregue una más grande al otro grupo y se iguale la diferencia. Así que de algún modo necesitaba llevar el control de todas las posibles decisiones. Pero, por cada moneda tengo dos opciones, y son máximo 100 monedas… en el peor de los casos hay formas de repartirlas. Un número un tanto grande: 1267650600228229401496703205376. Es tan grande que si pudiera ensayar cien millones de maneras de repartirlas en un segundo me tomaría aproximadamente 401969368413314 años ensayar todas las posibilidades. Así que fuerza bruta tampoco iba a funcionar…

Después pensé en hacer una tabla de booleanos, llamémosla dp, que tuviera tres parámetros: i, a, b. Entonces dp[i][a][b] sería verdadero si puedo repartir las primeras i monedas tal que un grupo tenga a pesos y el otro tenga b. Pero son máximo 100 monedas que pueden valer máximo 500, osea que la tabla tendría que tener espacio para todos los posibles a y b, que pueden llegar a ser tan grandes como 100 * 500 = 50000, o sea que la tabla tendría que ser algo así como:

(El 50001 es porque también tenemos que reservar espacio para cuando a ó b vale 0). Usando sizeof me doy cuenta que un booleano ocupa un byte, así que la tabla completa ocupa aproximadamente 100 * 50001 * 50001 bytes = 250010000100 bytes = 244150390 kilobytes = 238428 megabytes = 232 gigabytes. ¡Y mi computador sólo tiene una!

Pero por ahí iba la cosa… La solución se me ocurrió mientras me estaba bañando: No se necesita cargar a a y b. Lo único que importaba es la diferencia entre los dos grupos, llamémosla d. Y está diferencia puede ser máximo 50000, en el caso en que le demos todas las monedas al mismo tipito. Así que nuestra tabla queda:

Que ocupa mas o menos 4 megas de memoria… cosa de niños. Y si son menos monedas y en total suman menos, entonces será más pequeña todavía, y podemos declararla del tamaño que necesitemos en tiempo de ejecución.

Ahora tenemos un estado que se ve bastante prometedor. Sólo falta idear la manera de llenar la tabla. Recordemos su significado: dp[i][d] es verdadero si puedo repartir las primeras i monedas en dos grupos tales que la diferencia entre ellos sea exactamente d.

Como caso base tenemos que dp[0][m[0]] es verdadero, donde m[0] es el valor de la primera moneda. Esto equivale a decir que utilizando solo la primera moneda podemos formar dos grupos: uno con cero pesos, y otro con m[0] pesos.

Para agregar la moneda i-ésima con una diferencia d tenemos la siguiente definición recursiva:

Esto equivale a lo siguiente:
Podemos agregar la moneda i-ésima de valor m[i] si ocurre una de dos (o ambas) cosas:

1. Utilizando las i-1 primeras monedas podíamos formar una diferencia d + m[i]. Esto equivale a decir que de los dos grupos que teníamos, uno tenía d + m[i] más que el otro. Si agregamos m[i] al grupo con menos, la diferencia formada es exactamente d.
2. Utilizando las i-1 primeras monedas podíamos formar una diferencia de abs(d - m[i]). Esto representa la otra posibilidad: En vez de agregarla al grupo que tenía menos monedas, se la agregamos al grupo que tenía más; tenía d - m[i] más que el otro, y le sumamos m[i], formando una diferencia mayor de exactamente d. El valor absoluto se necesita para evitar diferencias negativas (Si el grupo X tiene -2 más que el grupo Y, es como decir que el grupo Y tiene 2 más que el grupo X, así que tomamos el valor positivo porque no nos interesa cuál grupo tiene más, sólo nos interesa la diferencia entre ellos).

Finalmente basta llenar la tabla de manera que cada que necesitemos un resultado esté ya disponible. Cada fila depende únicamente de la fila anterior, así que basta con evaluar las filas en orden creciente, y todas las posibles diferencias que puede haber por fila:

La variable s es la suma de todas las monedas, y el if adicional es para asegurarnos de no intentar leer una posición inexistente de la tabla.

Finalmente, la respuesta es el d más pequeño tal que dp[todas las monedas][d] sea verdadero:

La variable c es la cantidad de monedas.

El código: El algoritmo es O(n^2). Acá está el código completo. Una posible idea para optimizarlo: En la relación recursiva, una fila depende únicamente de la fila anterior. Es innecesario que la tabla tenga 100 filas, podría tener sólo 2.

Escuchen Led Zeppelin.