Resumen Ejecutivo
Teniendo en cuenta la entrada k
, encontrar una partición de números enteros 1
a n
en k
subconjuntos libre de suma para el más grande n
que pueda dentro de los 10 minutos.
Antecedentes: números de Schur
Un conjunto no A
tiene suma si su auto suma A + A = { x + y | x, y in A}
no tiene elementos en común.
Por cada número entero positivo k
hay un número entero más grande de S(k)
tal manera que el conjunto {1, 2, ..., S(k)}
se puede dividir en k
subconjuntos sin suma. Este número se denomina número k th Schur (OEIS A045652 ).
Por ejemplo, S(2) = 4
. Podemos particionar {1, 2, 3, 4}
como {1, 4}, {2, 3}
, y esa es la partición única en dos subconjuntos sin suma, pero ahora no podemos agregar 5
a ninguna de las partes.
Desafío
Escriba un programa determinista que haga lo siguiente:
- Tome un entero positivo
k
como entrada - Escribir la marca de tiempo actual de Unix en stdout
- Emite una secuencia de particiones de
1
an
enk
subconjuntos sin suma para aumentarn
, siguiendo cada secuencia con la marca de tiempo Unix actual.
El ganador será el programa que imprime una partición para el más grande n
en 10 minutos en mi computadora cuando se le da entrada 5
. Los empates se romperán por el tiempo más rápido para encontrar una partición para el mayor n
promedio de tres ejecuciones: es por eso que la salida debe incluir marcas de tiempo.
Detalles importantes:
- Tengo Ubuntu Precise, por lo que si su idioma no es compatible, no podré calificarlo.
- Tengo una CPU Intel Core2 Quad, por lo que si desea usar subprocesos múltiples, no tiene sentido usar más de 4 subprocesos.
- Si desea que use algún indicador o implementación particular del compilador, documente eso claramente en su respuesta.
- No deberá poner en mayúsculas y minúsculas su código para manejar la entrada
5
. - No es necesario que produzca todas las mejoras que encuentre. Por ejemplo, para la entrada
2
, solo puede generar la particiónn = 4
. Sin embargo, si no muestra nada en los primeros 10 minutos, lo calificaré comon = 0
.
fuente
n=59
, y ordenar por el mayor número de números permitidos menos quenextN
dan=64
. Ordenar por la longitud de la lista de números no permitidos (que puede tener repeticiones) conduce muy rápidamente a unn=30
patrón elegante .Tue Nov 10 00:44:25 2015
), pero lo vin=92
en menos de 2 segundos.ctime
mástime
porque la salida era más bonita cuandotime
era exactamente lo que debería he elegido.n=121
. oOPython 3, 121, <0.001s
La mejora heurística gracias a Martin Buttner significa que ni siquiera necesitamos aleatoriedad.
Salida:
Código:
Pitón 3, 112
Ordenar por suma de los 2 primeros elementos + sesgo
Copié la estructura de datos de El'endia Starman, que consiste en una lista de pares, donde el primer elemento del par son los elementos en ese cubo, y el segundo son las sumas de ese cubo.
Comienzo con el mismo enfoque de "realizar un seguimiento de las sumas disponibles". Mi heurística de clasificación es simplemente la suma de los dos elementos más pequeños en una lista dada. También agrego un pequeño sesgo aleatorio para probar diferentes posibilidades.
Cada iteración simplemente coloca a cada uno el nuevo número en el primer contenedor disponible, similar a la codicia aleatoria. Una vez que esto falla, simplemente se reinicia.
fuente
Java 8, n =
142144Última salida:
Realiza una búsqueda aleatoria sembrada distribuida en 4 hilos. Cuando no puede encontrar una partición para encajar
n
, intenta liberar espacio paran
una partición a la vez volcando todo lo que pueda en las otras particiones.editar: modificó el algoritmo para liberar espacio
n
, también agregó la capacidad de volver a una opción anterior y elegir nuevamente.nota: el resultado no es estrictamente determinista porque hay varios subprocesos involucrados y pueden terminar actualizando el mejor
n
encontrado hasta ahora en orden desordenado; Sin embargo, la puntuación final de 144 es determinista y se alcanza con bastante rapidez: 30 segundos en mi computadora.El código es:
fuente
C, codicioso al azar, n = 91
Solo para proporcionar una solución de referencia, esto se repite
n
, realiza un seguimiento de los contenedores y sus sumas y se agregan
a un contenedor aleatorio donde todavía no aparece como una suma. Termina una vez quen
aparece en todas lask
sumas, y si el resultadon
fue mejor que cualquier intento anterior, lo imprime en STDOUT.La entrada
k
se proporciona a través de un argumento de línea de comandos. El máximo posiblek
está actualmente codificado en 10 porque era demasiado perezoso agregar asignación de memoria dinámica, pero eso podría solucionarse fácilmente.Supongo que podría ir a buscar una semilla mejor ahora, pero esta respuesta probablemente no sea particularmente competitiva de todos modos, así que meh.
Aquí está la partición para
n = 91
:Y finalmente, aquí está el código:
fuente
n=91
, encontrado en 138 segundos. Si es necesario para el desempate, volveré a tomar el tiempo para evitar grandes errores debido a una carga de CPU diferente.C ++, 135
Agrega la siguiente n a un subconjunto elegido al azar. Si eso no es posible, elimina números aleatorios de subconjuntos y los agrega a otros con la esperanza de que eso permita agregar n en alguna parte.
Creé un prototipo de esto en awk y, como parecía prometedor, lo traduje a C ++ para acelerarlo. Usar un
std::set
incluso debería acelerarlo más.Salida para n = 135 (después de unos 230 segundos en mi máquina [antigua])
No volví a verificar la validez, pero debería estar bien.
fuente
Python 3, codicioso al azar, n = 61
Última salida:
Esto usa efectivamente el mismo algoritmo que Martin Büttner , pero lo desarrollé independientemente.
Hay
k
contenedores que tienen tanto los números hasta ahora como los números que ya no pueden entrar. En cada profundidad en la iteración (es básicamente una búsqueda de profundidad primero), el orden de los contenedores se baraja y el siguiente número (nextN
) se coloca (secuencialmente) en los contenedores que pueden llevarlo y luego va un paso más profundo. Si no hay ninguno, regresa, retrocediendo un paso.fuente
Python, n = 31
Ok, obviamente no es un ganador, pero sentí que pertenecía aquí de todos modos. Me he tomado la libertad de no incluir marcas de tiempo, ya que termina instantáneamente y no es un verdadero contendiente.
Primero, tenga en cuenta que la suma de dos números impares es par, por lo que podemos volcar todos los números impares en el primer bloque. Luego, dado que todos los números restantes son pares, podemos dividirlos por 2. Una vez más, podemos arrojar todos los números impares resultantes en el segundo bloque (después de volver a multiplicarlos por 2), dividir los números restantes por 2 (es decir, , por 4 en general), arroje los impares en el tercer bloque (después de volver a multiplicarlos por 4), y así sucesivamente ... O, para poner en palabras que ustedes entienden, ponemos todos los números cuyo conjunto menos significativo bit es el primer bit en el primer bloque, todos los números cuyo bit de conjunto menos significativo es el segundo bit en el segundo bloque, y así sucesivamente ...
Para k bloques, nos encontramos con problemas una vez que alcanzamos n = 2 k , ya que el bit de conjunto menos significativo de n es
el bit ( k + 1), que no corresponde a ningún bloque. En otras palabras, este esquema funciona hasta
que n = 2 k - 1. Por lo tanto, mientras que para k = 5 sólo tenemos un magro n = 31 , este número crece exponencialmente con k . También establece que S ( k ) ≥ 2 k - 1 (pero en realidad podemos encontrar un límite inferior mejor que eso con bastante facilidad).
Como referencia, aquí está el resultado para k = 5:
fuente
[1], [2,3], [4,5,6,7], ...
, lo que probablemente sea más simple, solo con el orden inverso de bits y bloques. Es fácil ver cómo se puede extender este.