0
210
ViewsReversión de listas Empalmes Optimización de Python (USACO febrero de 2020 Pregunta de bronce 3 "Swapity Swap")
Estoy tratando de resolver un problema que involucra la inversión de empalmes de listas y tengo problemas con el límite de tiempo para un caso de prueba, que es de 4 segundos. La pregunta:
Las vacas N del granjero John (1≤N≤100) están paradas en una fila. La i-ésima vaca de la izquierda tiene la etiqueta i, por cada 1≤i≤N. Farmer John ha ideado una nueva rutina de ejercicios matutinos para las vacas. Les dice que repitan el siguiente proceso de dos pasos exactamente K (1≤K≤1000000000) veces:
La secuencia de vacas actualmente en las posiciones A1…A2 desde la izquierda invierte su orden (1≤A1<A2≤N). Luego, la secuencia de vacas actualmente en las posiciones B1…B2 desde la izquierda invierte su orden (1≤B1<B2≤N). Después de que las vacas hayan repetido este proceso exactamente K veces, imprima la etiqueta de la i-ésima vaca de la izquierda para cada 1≤i≤N.
PUNTUACIÓN : Los casos de prueba 2-3 satisfacen K≤100. Los casos de prueba 4-13 no satisfacen restricciones adicionales.
FORMATO DE ENTRADA (archivo swap.in): La primera línea de entrada contiene N y K. La segunda línea contiene A1 y A2, y la tercera contiene B1 y B2.
FORMATO DE SALIDA (archivo swap.out): En la i-ésima línea de salida, imprima la etiqueta de la i-ésima vaca de la izquierda al final de la rutina de ejercicios.
ENTRADA DE MUESTRA :
7 2 2 5 3 7SALIDA DE MUESTRA :
1 2 4 3 5 7 6Inicialmente, el orden de las vacas es [1,2,3,4,5,6,7] de izquierda a derecha. Después del primer paso del proceso, el orden es [1,5,4,3,2,6,7]. Después del segundo paso del proceso, el orden es [1,5,7,6,2,3,4]. La repetición de ambos pasos por segunda vez produce el resultado de la muestra.
Teóricamente, podría resolver este problema encontrando el punto donde el programa se repite y luego simulando el k % frequency inverso veces, donde la frequency es la cantidad de veces que la simulación es única. Pero mi problema es que cuando la entrada es:
100 1000000000 1 94 2 98 mi programa tarda más de 100 segundos en ejecutarse. Esta entrada consume mucho tiempo porque ejecuta el número máximo de iteraciones y frequency es muy alta.
Código actual:
fin = open("swap.in", 'r') line = fin.readline().strip().split() n = int(line[0]) k = int(line[1]) nums = [[int(x)-1 for x in fin.readline().strip().split()]for i in range(2)] fin.close() repeated = [] cows = [i for i in range(1, n+1)] repeat = False while not repeat: for i in nums: cows[i[0]:i[1]+1] = reversed(cows[i[0]:i[1]+1]) if cows[i[0]:i[1]+1] in repeated : frequency = len(repeated)-1 repeat = True repeated.append(cows[i[0]:i[1]+1]) cows = [i for i in range(1, n+1)] for _ in range(k%frequency): for i in nums: cows[i[0]:i[1]+1] = reversed(cows[i[0]:i[1]+1]) fout = open("swap.out", 'w') for i in cows: fout.write(str(i) + "\n") fout.close()Si alguien sabe una manera de resolver este problema, por favor publique una respuesta. Comenta si algo no está claro.
5 answers
Answer question0
El principal problema con el rendimiento de su código es que está utilizando una lista para mantener un historial de las posiciones de las vacas en cada iteración para detectar un ciclo, lo que requiere O(n) para cada búsqueda de miembros con el operador in .
En su lugar, puede usar un conjunto para el propósito, que cuesta O (1) en las búsquedas de membresía. Pero dado que aún necesita iterar k % i veces, donde i es la duración del ciclo, para llegar a esa posición específica en el ciclo, sería mejor si el conjunto está ordenado para que pueda simplemente obtener el (k % i) -entrada indexada en el conjunto en lugar de tener que realizar tantas inversiones. Pero dado que el conjunto no está ordenado en Python, en su lugar puede usar un dict, donde las teclas están ordenadas desde Python 3.6:
from itertools import islice n, k, a1, a2, b1, b2 = map(int, '''100 1000000000 1 94 2 98'''.split()) cows = list(range(1, n + 1)) history = {} for i in range(k): key = tuple(cows) if key in history: cows = next(islice(history, k % i, None)) break history[key] = 1 for bound in map(slice, (a1 - 1, b1 - 1), (a2, b2)): cows[bound] = reversed(cows[bound]) print(*cows, sep='\n')Esto da como resultado:
71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 100Demostración: https://replit.com/@blhsing/CultivatedPointedArchitect
0
Puedes deshacerte de la mirada hacia arriba. Esto calcula los intercambios 5680 necesarios dos veces, pero ahorra espacio adicional para el diccionario. En una instancia de Google Colab, esta solución se ejecuta un 33 % más rápido que la solución @blhsing para este ejemplo en particular.
n, k, a1, a2, b1, b2 = [int(x) for x in ''' 100 1000000000 1 94 2 98 '''.split()] a1 -= 1 b1 -= 1 cows = list(range(1, n+1)) rot = cows[:] s = k while k: rot[a1:a2] = reversed(rot[a1:a2]) rot[b1:b2] = reversed(rot[b1:b2]) k -= 1 if rot == cows: print(f'found frequency {sk}') k %= sk print(*rot)Producción
found frequency 29640 71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 100El enfoque de @btilly
Codifiqué su enfoque y obtuve un tiempo de ejecución 4 veces más rápido para la primera solución de @dillondavis (320 µs / 78,9 µs)
n, k, a1, a2, b1, b2 = [int(x) for x in ''' 100 1000000000 1 94 2 98 '''.split()] a1 -= 1 b1 -= 1 cows = list(range(n)) cows[a1:a2] = reversed(cows[a1:a2]) cows[b1:b2] = reversed(cows[b1:b2]) visited = set() runs = [] for i in cows: if i not in visited: run = [i] nex = cows[i] while nex != i: run.append(nex) nex = cows[nex] visited.add(nex) runs.append(run) for i in runs: r = k % len(i) for x,y in zip(i, i[r:]+i[:r]): cows[x] = y+1 print(*cows)Producción
71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 1000
Aquí hay un enfoque que es trabajo O(N) sin importar lo que K pueda ser.
Explicación condensada: reescribe la permutación en notación de ciclo. Utilice la notación de ciclo para generar la respuesta. (Excepto que no necesitamos la notación de ciclo completo.
Para ilustrar, usaré tu ejemplo, pero encontraré la permutación después de 999 pasos.
Como observa, [1,5,7,6,2,3,4] es el resultado de una iteración de A y luego de B. Calcular eso, de esta forma, claramente requiere trabajo O(N) . Es un poco más conveniente escribir eso como:
{ 1: 1, 2: 5, 3: 6, 4: 7, 5: 2, 6: 4, 7: 3 } De nuevo, esta traducción requiere trabajo O(N) .
Ahora calculemos una respuesta parcial. Empezamos con [0,0,0,0,0,0,0]' where 0` significa "desconocido".
Primer paso, encontramos 1 -> 1 por lo que el primer ciclo es solo (1) . Recorrer este ciclo 999 veces nos da (1) nuevamente, por lo que ahora tenemos [1,0,0,0,0,0,0] .
Segundo paso, encontramos que 2 -> 5 -> 2 (nota, solo estamos buscando estos en la búsqueda, por lo que cada uno es O(1) trabajo) por lo que el segundo ciclo es (2, 5) . Recorrer este ciclo 999 pasos significa que podemos completar 2 valores. Ahora tenemos [1,5,0,0,2,0,0] .
Tercer paso, encontramos que 3 -> 6 -> 4 -> 7 -> 3 . Entonces el tercer ciclo es (3, 6, 4, 7) . Dar la vuelta 999 veces es como caminar 3 pasos hacia adelante, así que ahora podemos completar: [1,5,7,6,2,3,4] .
A medida que revisamos el resto de los números, encontramos que todos están completos. Entonces, nuestra respuesta es [1,5,7,6,2,3,4] .
En general, cada número es parte de un ciclo de longitud j . Cuando encontramos un ciclo, tomamos trabajo O(j) para encontrar el ciclo, y luego para otro trabajo O(j) completamos la respuesta de lo que sucede con ese ciclo. Luego, golpearemos los elementos j-1 que se completan y los omitiremos. Entonces obtenemos n elementos para el trabajo O(n) , para el trabajo O(1) amortizado por elemento.
El resultado es trabajo O(N) para encontrar la respuesta final.
0
Aquí hay otra versión de lo que entiendo como el enfoque del ciclo de btilly . Código Python de trabajo enviado a USACO :
import collections def f(n, k, ai, aj, bi, bj): # A cycle necessarily has even parity as both A and B # must be run. We know a cycle is complete when the # element returns to the start and the parity is even. cycles = collections.defaultdict(list) # Get cycles for i in range(1, n + 1): j = i parity = 0 first_cycle = 1 while first_cycle or j != i or parity: # A if not parity: j = j if (j < ai or j > aj) else aj - j + ai # B else: j = j if (j < bi or j > bj) else bj - j + bi first_cycle = 0 if parity: cycles[i].append(j) parity ^= 1 new_list = [None] * n for i in range(1, n + 1): idx = cycles[i][(k - 1) % len(cycles[i])] new_list[idx-1] = str(i) file = open("swap.out", "w") file.write("\n".join(new_list)) file.close() file = open("swap.in","r") data = file.readlines() [n, k] = map(int, data[0].split()) [ai, aj] = map(int, data[1].split()) [bi, bj] = map(int, data[2].split()) f(n, k, ai, aj, bi, bj) """ ai = 2 aj = 5 bi = 3 bj = 7 n = 7 k = 2 """ """ 1 2 4 3 5 7 6 """ 
0
Otra implementación del algoritmo de @btilly según tengo entendido, escrita antes de darme cuenta de que @MichaelSzczesny ha publicado la suya:
n, k, a1, a2, b1, b2 = map(int, '''100 1000000000 1 94 2 98'''.split()) *positions, = *mapped, = range(n) for bound in map(slice, (a1 - 1, b1 - 1), (a2, b2)): mapped[bound] = reversed(mapped[bound]) mapping = dict(zip(mapped, positions)) cycles = [] pool = set(positions) while pool: current = pool.pop() cycle = [current] while True: current = mapping[current] if current == cycle[0]: break pool.remove(current) cycle.append(current) cycles.append(cycle) result = [0] * n for cycle in cycles: for i, position in enumerate(cycle): result[cycle[(k + i) % len(cycle)]] = position + 1 print(*result)Esto da como resultado:
71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 100Las estadísticas de tiempo muestran que esto es un poco más rápido que la implementación de @MichaelSzczesny: https://replit.com/@blhsing/EquatorialRemorsefulMath