Swapity Swap

Solución en video

Por David Li

Código de la solución en video

C++Java


#include <iostream>
 
using namespace std;
 
void setIO(string s) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
 
int N, K, A1, A2, B1, B2, res[101];  // res guarda el resultado
 
int nex(int x) {
	if (A1 <= x && x <= A2)  // simulamos el paso 1
		x = A1 + A2 - x;
	if (B1 <= x && x <= B2)  // simulamos el paso 2
		x = B1 + B2 - x;
	return x;
}
 
int main() {
	setIO("swap");
 
	// leemos la entrada
	cin >> N >> K >> A1 >> A2 >> B1 >> B2;
 
	// resolvemos para cada vaca
	for (int i = 1; i <= N; ++i) {
		// p = ¿cuántos turnos llevamos?
		// cur = ¿dónde estamos después de p turnos?
		int p = 1, cur = nex(i);
		while (cur != i) {  // seguimos hasta haber encontrado un ciclo
			p++;
			cur = nex(cur);  // simulamos otro turno
		}
		int k = K % p;  // reducimos k
		for (int j = 0; j < k; ++j) cur = nex(cur);
		res[cur] = i;  // la posición de la vaca i después de k pasos es cur
	}
	// imprimimos la respuesta
	for (int i = 1; i <= N; ++i) cout << res[i] << "\n";
}


import java.io.*;
import java.util.*;
 
public class swap {
	static int A1, A2, B1, B2;
	public static void main(String[] args) throws IOException {
		// leemos la entrada
		BufferedReader br = new BufferedReader(new FileReader(new File("swap.in")));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		A1 = Integer.parseInt(st.nextToken());
		A2 = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		B1 = Integer.parseInt(st.nextToken());
		B2 = Integer.parseInt(st.nextToken());
		int[] res = new int[N + 1];
 
		// resolvemos para cada vaca
		for (int i = 1; i <= N; ++i) {
			// p = ¿cuántos turnos llevamos?
			// cur = ¿dónde estamos después de p turnos?
			int p = 1, cur = nex(i);
			while (cur != i) {  // seguimos hasta haber encontrado un ciclo
				p++;
				cur = nex(cur);  // simulamos otro turno
			}
			int k = K % p;  // reducimos k
			for (int j = 0; j < k; ++j) cur = nex(cur);
			res[cur] = i;  // la posición de la vaca i después de k pasos es cur
		}
 
		PrintWriter out = new PrintWriter("swap.out");
		for (int i = 1; i <= N; i++) { out.println(res[i]); }
		out.close();
	}
	public static int nex(int x) {  // simula un turno, o dos pasos
		if (A1 <= x && x <= A2) x = A1 + A2 - x;
		if (B1 <= x && x <= B2) x = B1 + B2 - x;
		return x;
	}
}

Pista 1

Intentemos simular los intercambios nosotros mismos sobre la entrada de ejemplo. ¿Qué se observa sobre el desplazamiento de ciertas vacas?

Respuesta a la pista 1

¡Después de un cierto número de ciclos, las vacas terminan justo donde empezaron!

Pista 2

Dado que las vacas solo dan vueltas en ciclos a lo largo de todos estos intercambios, ¿se puede pensar en una forma más eficiente de simularlos?

Solución

Análisis oficial (C++ y Java)

Explicación

Para obtener el puntaje completo, necesitamos hacer algo mejor que simular los $K$ procesos uno tras otro.

Notamos que, después de repetir el proceso un cierto número de veces, las vacas terminan todas justo donde empezaron. Nótese que cada vaca solo puede intercambiarse a un número finito de nuevas posiciones después de cada proceso, así que debe volver a su posición original para $N$ arbitrariamente grande. Esto nos da la idea de simular el proceso de intercambio hasta que todas las vacas vuelvan a sus posiciones originales.

Sea $X$ el número mínimo de veces que debemos repetir el proceso para que esto ocurra. Para hallar $X$ , podemos llevar la cuenta del ordenamiento de las vacas, y si alguna vez encontramos un ordenamiento guardado previamente, usamos el número de ordenamientos guardados para determinar $X$ .

Ahora solo tenemos que considerar el resto de $K$ al dividirlo por $X$ en lugar de $K$ mismo. Se puede verificar por búsqueda exhaustiva que el valor máximo posible de $X$ para $N \leq 100$ es $29640$ . Así, las cotas son lo bastante pequeñas como para que podamos simular el proceso $K \bmod X$ veces y aun así pasar el problema a tiempo.

Implementación

Complejidad temporal: $\mathcal{O}(NX)$

C++JavaPython


#include <fstream>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
/** Invierte [start, end] en el vector dado in-place. */
template <typename T> void reverse_segment(vector<T> &vec, int start, int end) {
	while (start < end) {
		T temp = vec[start];
		vec[start] = vec[end];
		vec[end] = temp;
 
		start++;
		end--;
	}
}
 
int main() {
	std::ifstream read("swap.in");
	int n, k;
	read >> n >> k;
	int a1, a2;
	int b1, b2;
	read >> a1 >> a2 >> b1 >> b2;
 
	vector<int> cows(n);
	// Asignamos los valores 1, 2, 3... al vector de vacas
	iota(cows.begin(), cows.end(), 1);
 
	// Aplicamos intercambios hasta que las vacas se repitan
	std::set<vector<int>> visited{cows};
	while (true) {
		reverse_segment(cows, a1 - 1, a2 - 1);
		reverse_segment(cows, b1 - 1, b2 - 1);
		if (visited.count(cows)) { break; }
		visited.insert(cows);
	}
 
	int cycle_len = visited.size();
	int swaps_left = k % cycle_len;
	for (int s = 0; s < swaps_left; s++) {
		reverse_segment(cows, a1 - 1, a2 - 1);
		reverse_segment(cows, b1 - 1, b2 - 1);
	}
 
	std::ofstream written("swap.out");
	for (int c : cows) { written << c << '\n'; }
}


import java.io.*;
import java.util.*;
 
public class Swap {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("swap.in"));
		StringTokenizer st = new StringTokenizer(read.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
 
		st = new StringTokenizer(read.readLine());
		int a1 = Integer.parseInt(st.nextToken()) - 1;
		int a2 = Integer.parseInt(st.nextToken()) - 1;
 
		st = new StringTokenizer(read.readLine());
		int b1 = Integer.parseInt(st.nextToken()) - 1;
		int b2 = Integer.parseInt(st.nextToken()) - 1;
		read.close();
 
		List<Integer> cows = new ArrayList<>();
		for (int c = 1; c <= n; c++) { cows.add(c); }
 
		// Aplicamos intercambios hasta que las vacas se repitan
		Set<List<Integer>> visited = new HashSet<>();
		visited.add(new ArrayList<>(cows));
		while (true) {
			reverseSegment(cows, a1, a2);
			reverseSegment(cows, b1, b2);
			if (visited.contains(cows)) { break; }
			visited.add(new ArrayList<>(cows));
		}
 
		int cycleLen = visited.size();
		int swapsLeft = k % cycleLen;
		for (int s = 0; s < swapsLeft; s++) {
			reverseSegment(cows, a1, a2);
			reverseSegment(cows, b1, b2);
		}
 
		PrintWriter written = new PrintWriter("swap.out");
		for (int c : cows) { written.println(c); }
		written.close();
	}
 
	/** Invierte [start, end] en la lista dada in-place. */
	static <T> void reverseSegment(List<T> lst, int start, int end) {
		while (start < end) {
			T temp = lst.get(start);
			lst.set(start, lst.get(end));
			lst.set(end, temp);
 
			start++;
			end--;
		}
	}
}


from typing import List
 
 
def reverse_segment(lst: List[int], start: int, end: int):
	"""Invierte [start, end] en la lista dada in-place."""
	while start < end:
		lst[start], lst[end] = lst[end], lst[start]
		start += 1
		end -= 1
 
 
with open("swap.in") as read:
	n, k = map(int, read.readline().split())
	a1, a2 = map(int, read.readline().split())
	b1, b2 = map(int, read.readline().split())
 
cows = list(range(1, n + 1))
 
# Aplicamos intercambios hasta que las vacas se repitan
visited = set()
visited.add(tuple(cows))
while True:
	reverse_segment(cows, a1 - 1, a2 - 1)
	reverse_segment(cows, b1 - 1, b2 - 1)
	if tuple(cows) in visited:
		break
	visited.add(tuple(cows))
 
cycle_len = len(visited)
swaps_left = k % cycle_len
for _ in range(swaps_left):
	reverse_segment(cows, a1 - 1, a2 - 1)
	reverse_segment(cows, b1 - 1, b2 - 1)
 
print(*cows, sep="\n", file=open("swap.out", "w"))