Meet in the Middle

Algunos problemas tienen un N cercano a 40, y probar los 2^N subconjuntos es inviable. Meet in the middle permite resolver estos casos de tamaño intermedio. 🤝

Divida la entrada en dos mitades. Resuelva cada mitad mediante fuerza bruta y después combine ingeniosamente los dos resultados parciales.

Dos mitades de tamaño N/2 cuestan 2^(N/2) cada una, en lugar de 2^N en total. Esta reducción a la raíz cuadrada convierte 2^40 en unos asequibles 2^20.

Determine si algún subconjunto suma un objetivo T. La suma de subconjuntos con N cercano a 40 es el problema clásico para aplicar meet in the middle.

Enumere todas las sumas de subconjuntos de la mitad izquierda y almacénelas. Con N/2 elementos, son solo 2^(N/2) sumas.

Haga lo mismo con la mitad derecha y construya su lista completa de sumas de subconjuntos. Ahora tiene dos listas manejables.

Para cada suma derecha r, necesita una suma izquierda igual a T menos r. Un conjunto o una lista ordenada permite comprobarlo rápidamente.

Para objetivos exactos, use un conjunto hash. Para contar o encontrar sumas cercanas, ordene una mitad y haga una búsqueda binaria en ella.

El trabajo total es aproximadamente 2^(N/2) multiplicado por un factor logarítmico debido a la búsqueda o la ordenación. Esa complejidad es lo que hace viable un N cercano a 40.

Almacena una mitad completa, por lo que la memoria crece hasta 2^(N/2). Conserve solo lo imprescindible para mantenerse dentro del límite.

Además de la suma de subconjuntos, úselo para hallar el subconjunto máximo bajo un límite, contar pares y resolver problemas al estilo del logaritmo discreto. Se beneficia de una buena división.

Divida en dos mitades, aplique fuerza bruta a cada una y después haga coincidir las sumas izquierda y derecha. Ha cambiado un poco de memoria por una enorme mejora de velocidad. 🚀