Soluciones en haskell
Comprobando todos los números anteriores a cada uno dentro de la lista
A una serie de la que sólo se dan algunos elementos puede añadirse cualesquiera otros elementos de forma arbitraria. Y todas son correctas. De entre las infinitas funciones generadoras que pueden definirse, las "habituales" son los polinomios (por ser fáciles de resolver).
En un vetusto ordenador se pueden procesar millones de filas de registro en unos pocos segundos.
Se puede aproximar con coste logarítmico si reducimos de N a 1 y de 1 a M. La solución suele estar entorno al 123% de la mejor solución pero permite obtener rutas entre números absurdamente grandes.
Lo he intentado pero no consigo mejorar el algoritmo básico de búsqueda, no se si se puede o, como la conjetura de Collatz, no se sabe aún. Tampoco he podido obtener una buena cota superior. Sin embargo, en lugar de bajar el árbol en anchura, podemos ir reduciendo la altura a la vez que vamos de un lado al otro con sólo analizar primero las reducciones exponenciales (dividir por 2 el destino). No es determinista, pero la heurística funciona bien.
Mi misma solución anterior pero "oneliner". Misma complejidad pero peor constante. Se generaliza la expansión.
Si se ignoran completamente las propiedades numéricas del problema (lo cual puede ser mucho ignorar) el problema es completamente isomorfo a una búsqueda del camino más corto entre dos nodos en un grafo y bastaría usar cualquier algoritmo genérico. Aquí no obstante se implementa usando un heap. Se pone otro ejemplo que resuelve el mismo tipo de problemas pero con cadenas de caracteres.
Una generalización del problema, permite cualquier tipo y número de productos y aplicar cualquier tipo de regla para aplicar descuento (ej. que dos productos sean de la misma marca), también genera el mejor ticket posible aplicando todos los descuentos posibles y mostrando el ticket de la mejor forma posible (agrupando siempre que se pueda).
Los números primos son aquellos números naturales sólo divisibles por la unidad y por ellos mismos o, de forma equivalente, aquellos que no son divisibles por ningún número mayor que 1 y menos que él mismo.
Se da la solución para cualquier tipo de criatura y criterio de selección de los salones. Se dice que los Ángeles y Demonios fueron creados hace unos 6.000 años y que montaron su propio salón Celestial...
Es muy sencillo definir un pequeño motor de geometría sólida.
Para cualquier nº de autobuses y trayectos, permitiendo diversos parámetros y calculando el reparto óptimo entre autobuses y trayectos para minimizar el precio total, por persona, ...
Parece que lo más apropiado es usar Floyd-Warshall y buscar el máximo peso.
En la solución anterior, se realizaban tantas ordenaciones de listas de coordenadas X como coordenadas Y hubiera. Un speedup importante es mantener ya ordenada una única lista de coordenadas X.
Si como parece por el enunciado las coordenadas son enteras y acotadas (ej. 1000x1000) una solución práctica óptima pasaría por usar la GPU y renderizar las cajas sobre un buffer acumulador. Mi solución es más general y admite cualquier rango de coordenadas (ej. 10e40x10e40) y coordenadas reales (no enteras).
El método indicado tiene un montón de bifurcaciones que deben codificarse, el propio paper no da una forma más directa, por lo que aunque el resultado es genial, codificarlo es un ladrillo. Aquí una forma con coste lineal (exponencial en el número de dígitos).
No conozco ninguna propiedad que permita relacionar los capicúas en base 2 y base 10 por lo que no veo otra que tomar los de base 10 (hay mucho menos) y checar si lo es en base 2. Así, todos los speepup serían de la constante multiplicativa y el algoritmo exponencial en el número de dígitos (lineal en el máx N a revisar).
