Esta pregunta tiene una configuración similar para encontrar una matriz que se ajuste a un conjunto de sumas, aunque es bastante diferente en sus objetivos.
Considere una variedad A
de longitud n
. La matriz contiene solo enteros positivos. Por ejemplo A = (1,1,2,2)
. Definamos f(A)
como el conjunto de sumas de todos los subconjuntos contiguos no vacíos de A
. En este caso f(A) = {1,2,3,4,5,6}
. Los pasos para producir f(A)
son los siguientes:
Las submatrices de A
son (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2)
. Sus sumas respectivas son 1,1,2,2,2,3,4,4,5,6
. El conjunto que obtienes de esta lista es por lo tanto {1,2,3,4,5,6}
.
Llamamos a una matriz A
única si no hay otra matriz B
de la misma longitud que f(A) = f(B)
, a excepción de la matriz A
invertida. Como ejemplo, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6}
pero no hay otra matriz de longitud 3
que produzca el mismo conjunto de sumas.
Solo consideraremos matrices donde los elementos son un entero dado s
o s+1
. Por ejemplo, si s=1
las matrices solo contendrían 1
y 2
.
Tarea
La tarea, para un dado n
y s
es contar el número de matrices únicas de esa longitud. Puede suponer que s
está entre 1
y 9
.
No debe contar el reverso de una matriz ni la matriz misma.
Ejemplos
s = 1
, la respuesta es siempre n+1
.
s = 2
, las respuestas que cuentan desde n = 1
arriba son:
2,3,6,10,20,32,52,86
s = 8
, las respuestas que cuentan desde n = 1
arriba son:
2,3,6,10,20,36,68,130
Puntuación
Para un determinado n
, su código debe generar la respuesta para todos los valores de s
from 1
a 9
. Su puntaje es el valor más alto n
para el cual esto se completa en un minuto.
Pruebas
Necesitaré ejecutar su código en mi máquina ubuntu, así que incluya las instrucciones más detalladas posibles sobre cómo compilar y ejecutar su código.
Tabla de clasificación
- n = 24 por Anders Kaseorg en Rust (34 segundos)
- n = 16 por Ourous en Clean (36 segundos)
- n = 14 por JRowan en Common Lisp (49 segundos)
fuente
Respuestas:
Óxido , n ≈ 24
Requiere óxido nocturno para la
reverse_bits
característica conveniente . Compilarrustc -O unique.rs
y ejecutar con (por ejemplo)./unique 24
.fuente
s
ys+1
en ellas?s
ys + 1
(dado que usted dijo que esas son las únicas matrices que consideraremos), aunque no es inmediatamente obvio si eso marcaría la diferencia.SBCL común de Lisp, N = 14
función de llamada (goahead ns)
aquí están los tiempos de ejecución
fuente
sbcl
alguna manera?Limpiar
Ciertamente no es el enfoque más eficiente, pero estoy interesado en ver qué tan bien funciona un ingenuo filtro de valor.
Dicho esto, todavía hay un poco de mejora por hacer con este método.
Coloque en un archivo llamado
main.icl
o cambie la línea superior amodule <your_file_name_here>
.Compilar con
clm -h 1500m -s 50m -fusion -t -IL Dynamics -IL StdEnv -IL Platform main
.Puede obtener la versión que TIO (y yo) usamos desde el enlace en el encabezado, o una más reciente desde aquí .
fuente
s
? En la pregunta que dice " Para un n dado , su código debe generar la respuesta para todos los valores de s del 1 al 9".