Skip to Content
CTRL K

Frog

Binary lifting con memoria lineal

Aunque no es necesario para este problema, se puede usar binary lifting con memoria lineal  para responder las consultas online.

Explicación

Para calcular la kk-ésima roca más cercana desde una ubicación dada, mantenemos una ventana deslizante de tamaño k+1k+1. Esencialmente, barremos de izquierda a derecha y seguimos moviendo la ventana hacia la derecha hasta que ocurra una de estas dos cosas:

  1. La ventana no se puede mover más a la derecha.
  2. Mover la ventana hacia la derecha aumentaría la distancia máxima desde la ubicación actual.

Después, podemos aplicar binary lifting para obtener la respuesta. Sin embargo, calcular los binary lifts de la forma tradicional ocuparía demasiada memoria. A partir de aquí, hay dos formas de proceder:

Implementación 1

Iteramos sobre la potencia de dos en la que estamos elevando, en orden creciente. De forma similar a la exponenciación binaria, calculamos la 2i2^{i}-ésima siguiente ubicación en cada paso, y comprobamos si necesitamos usar este lift actual.

Complejidad temporal: O(Nlog⁡M)\mathcal{O}(N\log M)

Complejidad espacial: O(N)\mathcal{O}(N)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	ll m;
	cin >> n >> k >> m;
	vector<ll> rocks(n);
	for (ll &i : rocks) { cin >> i; }
 
	vector<int> next_stone(n);
	// Maintain a sliding window of size k + 1 to
	// calculate the next stone the frog will jump to.
	int l = 0;
	int r = k;
	for (int i = 0; i < n; i++) {
		while (r + 1 < n && rocks[r + 1] - rocks[i] < rocks[i] - rocks[l]) { l++, r++; }
		next_stone[i] = (rocks[i] - rocks[l] >= rocks[r] - rocks[i]) ? l : r;
	}
 
	vector<int> res(n);
	iota(begin(res), end(res), 0);
	// Calculate the 2^i-th bit at every step,
	// and check if we need to make this "lift".
	for (int i = 0; i <= (int)log2l(m); i++) {
		if ((m >> i) & 1) {
			for (int j = 0; j < n; j++) { res[j] = next_stone[res[j]]; }
		}
		vector<int> nxt_t(n);
		for (int j = 0; j < n; j++) { nxt_t[j] = next_stone[next_stone[j]]; }
		next_stone = nxt_t;
	}
 
	for (int i = 0; i < n; i++) { cout << res[i] + 1 << " \n"[i == n - 1]; }
}

Implementación 2

Observamos que con estos saltos se construye un grafo funcional. Después de nn saltos, cualquier nodo desde el que empecemos terminará dentro de un ciclo. Así, podemos calcular los binary lifts de forma normal, y calcular el número de saltos, módulo el tamaño del ciclo.

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N\log N)

Complejidad espacial: O(Nlog⁡N)\mathcal{O}(N\log N)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	ll m;
	cin >> n >> k >> m;
	vector<ll> rocks(n);
	for (ll &i : rocks) { cin >> i; }
	const int LOG = (int)log2(n) + 1;
	vector<vector<int>> lift(n, vector<int>(LOG));
 
	// Maintain a sliding window of size k + 1 to
	// calculate the next stone the frog will jump to.
	int l = 0;
	int r = k;
	for (int i = 0; i < n; i++) {
		while (r + 1 < n && rocks[r + 1] - rocks[i] < rocks[i] - rocks[l]) { l++, r++; }
		lift[i][0] = (rocks[i] - rocks[l] >= rocks[r] - rocks[i]) ? l : r;
	}
	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j < n; j++) { lift[j][i] = lift[lift[j][i - 1]][i - 1]; }
	}
 
	// Calculate the sizes of the cycles formed.
	vector<int> cycle_size(n);
	vector<int> prev_node(n, -1);
	for (int i = 0; i < n; i++) {
		int ptr = i;
		while (prev_node[ptr] == -1) {
			prev_node[ptr] = i;
			ptr = lift[ptr][0];
		}
		if (prev_node[ptr] != i) { continue; }
		int cur_size = 0;
		while (prev_node[ptr] == i) {
			cur_size++;
			prev_node[ptr] += n;
			ptr = lift[ptr][0];
		}
		while (prev_node[ptr] == i + n) {
			cycle_size[ptr] = cur_size;
			prev_node[ptr] += n;
			ptr = lift[ptr][0];
		}
	}
 
	auto jump = [&](int idx, int dist) -> int {
		for (int i = LOG - 1; i >= 0; i--) {
			if ((dist >> i) & 1) idx = lift[idx][i];
		}
		return idx;
	};
 
	/*
	 * If m <= n, then we can just binary lift on our answer.
	 * Otherwise, observe that after n jumps, the current location
	 * will be inside some cycle. Thus, we can calculate the binary lift,
	 * modulo the cycle's size.
	 */
	for (int i = 0; i < n; i++) {
		int res = -1;
		if (m <= n) {
			res = jump(i, m);
		} else {
			int cycle_node = jump(i, n);
			int jumps = (m - n) % cycle_size[cycle_node];
			res = jump(cycle_node, jumps);
		}
		cout << res + 1 << " \n"[i == n - 1];
	}
}
Fundamentos