Editorial for El Conejo Saltarín

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: aniervs

Subtarea 1

$a_i = i$ ~a_i = i~

En esta subtarea, $a_r - a_l = r - l$ ~a_r - a_l = r - l~, por lo que siempre es posible ir de $i$ ~i~ a cualquier $j \in [i+1, i + k]$ ~j \in [i+1, i + k]~ en 1 salto. Por tanto, la respuesta para una pregunta $(l, r)$ ~(l, r)~ es $\left\lceil\frac{r - l}{k}\right\rceil$ .

Subtarea 2

$a_i - a_{i-1} = c$ ~a_i - a_{i-1} = c~, para alguna constassnte $c$ ~c~.

La idea es similar. En esta subtarea, $a_r - a_l = (r - l) \cdot c$ ~a_r - a_l = (r - l) \cdot c~.

Entonces, si queremos ir de $i$ ~i~ a $j$ ~j~ en un salto, se tiene que cumplir que

$(j - i)\cdot c \le k \iff (j - i) \le \left\lfloor\frac{k}{c}\right\rfloor$ . Por tanto, podemos dar saltos de longitud $\left\lfloor\frac{k}{c}\right\rfloor$ ~\left\lfloor\frac{k}{c}\right\rfloor~.

Entonces, la respuesta para una pregunta $(l, r)$ ~(l, r)~ es $\left\lceil\frac{r - l}{\left\lfloor\frac{k}{c}\right\rfloor}\right\rceil$ .

Subtarea 3

$n\cdot q \le 10^6$ ~n\cdot q \le 10^6~.

Podemos resolver cada pregunta en tiempo lineal. Podemos usar dos punteros para dar los saltos óptimos, manteniendo para cada $l$ ~l~, el mayor $r$ ~r~ tal que $a_r - a_l \le k$ ~a_r - a_l \le k~.

Complejidad temporal: $\mathcal{O}(n\cdot q)$ ~\mathcal{O}(n\cdot q)~.

Subtarea 4

Notemos que $k \ge \frac{a_n}{20}$ ~k \ge \frac{a_n}{20}~, por lo que $\frac{a_n}{k} \le 20$ ~\frac{a_n}{k} \le 20~. Eso quiere decir que la cantidad mínima de pasos para ir desde cualquier punto a otro es menor que o igual a 20. Por tanto, podemos usar la solución de la subtarea anterior.

Subtarea 5

Digamos que $f(l)$ ~f(l)~ es el mayor $r \ge l$ ~r \ge l~ tal que $f(r) - f(l) \le k$ ~f(r) - f(l) \le k~. Si no existe tal $r$ ~r~, digamos que $f(r) = -1$ ~f(r) = -1~.

$f()$ ~f()~ se puede computar en tiempo lineal usando dos punteros, de derecha a izquierda.

Podemos considerar esto como un grafo dirigido, donde cada nodo tiene grado de salida 1. De hecho, si consideramos los $x: f(x) = -1$ ~x: f(x) = -1~ como raíces, este grafo es realmente un bosque con las aristas orientadas desde las hojas hacia la raíz.

Podemos usar la técnica binary lifting, que consiste en mantener para cada nodo, la lista de ancestros a distancia $2^0, 2^1, 2^2, 2^3, \dots$ ~2^0, 2^1, 2^2, 2^3, \dots~.

Si tenemos una pregunta $(l, r)$ ~(l, r)~, usando esta lista de ancestros, podemos vorazmente buscar el primer ancestro de $l$ ~l~ que sea mayor o igual que $r$ ~r~, y la respuesta sería la diferencia entre las profundidades de $l$ ~l~ y el ancestro encontrado en el grafo.

Comments

There are no comments at the moment.