El reto
Hay N ciudades alineadas en línea recta. La i-ésima ciudad se encuentra a A[i]
kilómetros a la derecha del origen. No habrá dos ciudades en el mismo lugar.
Vas a construir una red eléctrica con algunas centrales eléctricas. Las centrales eléctricas deben construirse dentro de una ciudad. Sin embargo, solo se le permite construir K
(<N) plantas de energía, por lo que habrá algunas ciudades sin plantas de energía en ellas. Para cada ciudad sin plantas de energía, debes construir un cable entre ella y la ciudad más cercana que tenga una planta de energía .
Por ejemplo, si hay tres ciudades ubicadas en 0, 1, 2
, y solo la ciudad 0
tiene una planta de energía, debe construir dos cables, uno de 2
a 0
(2 km) y el otro de 1
a0
(1 km), la cual tiene una longitud total de 3 kilometros .
Dado K
posiciones de las ciudades ( A
), debes calcular los kilómetros mínimos de cable que necesitas para construir la red.
Ejemplos de casos de prueba
K = 1, A = [0, 2, 4, 6, 8] : 12
# build power plant in the city at position 4, total length = 4 + 2 + 0 + 2 + 4 = 12
K = 3, A = [0, 1, 10, 11, 20, 21, 22, 30, 32] : 23
# build power plants in cities at positions 0, 10 and 22
K = 5, A = [0, 1, 3, 6, 8, 11, 14] : 3
# build power plants in all cities except those at positions 0, 3
K = 6, A = [0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84] : 49
Presupuesto
Debe implementar una función o un programa, que toma un entero positivo
K
y una lista de enterosA
en cualquier forma, y genera / devuelve un entero que representa la respuesta.A
se ordena en orden ascendente y todos los elementos son enteros no negativos.A[0] = 0
, yA[N-1]
no será más de 1000N.Tenga en cuenta que la salida tendrá una magnitud de 1000N 2 , por lo que en casos más grandes, es posible que necesite enteros de 64 bits en algunos idiomas.
El subprocesamiento múltiple no está permitido (estableceré la afinidad de su programa en solo 1 núcleo cuando juzgue).
-O2
Se permiten optimizaciones del compilador (como en C).
Tanteo
Voy a cronometrar su código en mi computadora (Ubuntu 16.04 con procesador Intel i7-3770S) con diferentes tamaños de casos de prueba. Específicamente, generaré algunos casos de prueba con N = piso (2 x / 5 ) donde x es un número entero positivo.
Su puntaje será el valor x del caso de prueba más pequeño en el que su programa usa más de 10 segundos o 1 GiB de memoria, o no da una respuesta correcta.- La respuesta con la puntuación más alta gana. Si dos respuestas obtienen el mismo puntaje, gana la respuesta anterior.
Todos los programas serán juzgados por el mismo conjunto de casos de prueba.
Siéntase libre de publicar sus propios puntajes. Se alientan las explicaciones de su algoritmo.
Prima
Este es mi programa C ++, puntúa 108 . Puede verificar el resumen SHA-256 9a87fa183bad1e3a83d2df326682598796a216b3a4262c32f71dfb06df12935d
por todo el segmento de código (sin pie de página) en el enlace.
El algoritmo combina la búsqueda binaria y la optimización de Knuth para encontrar la penalización correcta de cada planta para obtener el número deseado. La complejidad es O (N log N log A [N-1]). Me sorprendió que el programa obtuviera una puntuación más alta que la solución O (N log A [N − 1]) de Anders Kaseorg . Probablemente se deba al hecho de que el caso de registro en la optimización de Knuth generalmente no ocurrirá.
Tenga en cuenta que este desafío es el mismo que IOI 2000 Post Office . Sin embargo, las restricciones originales son N <= 300 y K <= 30.
fuente
2^^(x/5)
: Cuál es el significado ? ¿puedes proporcionar un límite superior para N?N=21( = floor(2^(22/5)) )
en 10 segundos, pero no puede manejarloN=24( = floor(2^(23/5)) )
, entonces 23 será el puntaje. No utilicé un límite superior, ya que las diferencias entre los diferentes algoritmos son demasiado grandes. Por ejemplo, si configuro N <= 40, habrá poca diferencia entreO(KN^2)
yO(KN^3)
, sin embargoO(2^N)
, ni siquiera terminará en un tiempo razonable.Respuestas:
Óxido , puntaje = 104
Esta es una implementación del algoritmo señalado por Grønlund et al. (2017) al final del §3.3.1, aunque tuve que seguir una larga cadena de citas y completar algunos detalles faltantes. Se ejecuta en O ( N log A [ N - 1]).
Compilar con
rustc -O
. El formato de entrada estáK
en la primera línea, seguido de las entradas deA
, una entrada por línea, todas en stdin.(Nota: estoy enviando esto una hora después de la fecha límite de recompensa, pero espero que la última versión que envié antes de la fecha límite de recompensa , que se ejecutó en O ( N log N log A [ N - 1]), tenga una puntuación de 94 .)
Pruébalo en línea!
Moho , puntaje pretest = 73
Compilar con
rustc -O
. El formato de entrada estáK
en la primera línea, seguido de las entradas deA
, una entrada por línea, todas en stdin.Pruébalo en línea!
fuente
61
, pero eso se debe a un desbordamiento deu32
. ¿Tal vez pueda cambiar al tipo entero de 64 bits?type Cost = u32
atype Cost = u64
?73
.C, puntaje = 56
contenido de
a.c
:script de shell para compilar y probar lo anterior:
n = 776 toma 6.2s, n = 891 toma 12sn = 1176 toma 5.9s, n = 1351 toma un poco más de 10sn = 1351 toma 8.7s, n = 1552 toma más de 10s (con k = 2 * n / 3) en mi
Intel(R) Core(TM) i3-2375M CPU @ 1.50GHz
fuente
syntax/c.vim
.C ++, puntaje = 53
La solución que había dicho en el comentario.
O(n²×k)
. (ahora lo eliminé porque ya no es necesario) Probablemente se puede reducir aO(n×k)
.La entrada es bastante flexible, en la primera línea, el primer número es
k
, los otros números son elementos de la matriza
, pero si encuentra paréntesis, deja de leer la entrada. EntoncesK = 1, A = [0, 2, 4, 6, 8] : 12
se acepta la entrada como .Pruébalo en línea!
Generar casos de prueba aleatorios. (entrada
N
y, opcionalmente, rango de ciudad,1000×N
por defecto)fuente
int
s aint64_t
s necesarios .C #, puntaje = 23
Estoy seguro de que esto no va a ganar este desafío, solo quería publicar una primera respuesta (y muy básica) para alentar a otras personas a publicar sus algoritmos y mejorar los míos. Este código debe compilarse como un proyecto de consola que utiliza el paquete Combinatorics de NuGet. El método principal contiene algunas llamadas al
Build
método para probar los casos propuestos.Explicación realmente simple: para cada combinación
c
dek
elementos desdea
, calcule la suma de las distancias desde cada elementoa
hasta el elemento más cercanoc
y devuelva la combinación con la menor distancia total.Versión de una línea del
Build
método (probablemente más lenta que la versión original expandida; esto necesita agregar una referencia aSystem.Linq
):fuente
C ++, puntuación = 48
Entrada de uso: NKA [1] A [2] ... A [N]
fuente
step
70, su puntaje de prueba previa es 60.Rubí , puntaje = 23
Pruébalo en línea!
No creo que vaya a ganar, pero quería intentarlo.
fuente
JavaScript (ES6) (Node.js) , puntuación = 10
Nuevo algoritmo, explicará si realmente funciona esta vez.
Pruébalo en línea!
Corre de la misma manera que el otro.
JavaScript (ES6) (Node.js) , puntaje pretest = 12
Esquema del algoritmo:
El programa primero asigna los datos a la clase de ciudad, que asigna algunos puntos de datos:
la matriz se arroja a la clase Grupo, que tiene lo siguiente:
Ahora el algoritmo procede a dividir los grupos siempre que tenga 2 o más plantas de energía para colocar.
Finalmente, asigna los grupos a sus centros y los resume a todos.
Como correr:
Ejecutar usando Node.js (v9.2.0 es lo que se usó para la creación)
ejecutar el programa utilizando casos de prueba generados para la puntuación 70:
ejecutar el programa usando 1 planta de energía y ciudades [0,3,5]:
Código:
Pruébalo en línea!
Limpiaré el código comentado en los próximos días, ya que todavía estoy trabajando en esto, solo quería ver si esto pasaba más que los pequeños casos.
fuente
K = 2, A = [0, 21, 31, 45, 49, 54]
. La respuesta correcta es 40, pero su programa genera 51.K = 2, A = [0, 4, 7, 9, 10]
. Correcto: 7, su respuesta: 8.K = 2, A = [0, 1, 3, 4, 9]
. Correcto: 6, su respuesta: 7.C (no competidor, puntaje pretest = 76)
Este es un intento de traducir la segunda solución Rust de @ AndersKaseorg a C.
Compilar con:
fuente
Limpiar , puntuación = 65
Compilar con:
clm -h 1024M -gci 32M -gcf 32 -s 32M -t -nci -ou -fusion -dynamics -IL Platform main
Toma
K
, y luego cada elemento deA
, como argumentos de línea de comandos.fuente