Editorial for Ifri y la string.

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.

Subtarea $1$ ~1~ ( $N \leq 21$ ~N \leq 21~)

Ya que $N$ ~N~ es pequeño, es posible realizar una búsqueda exhaustiva en las posiciones restantes. Dado que ir por todos los subconjuntos toma $O(2^N)$ ~O(2^N)~ y la cantidad de veces que se realiza la operacion 3 puede calcularse en $O(N)$ ~O(N)~, la complejidad total es de $O(2^N * N)$ ~O(2^N * N)~.

Subtarea $2$ ~2~ ( $N \leq 3000$ ~N \leq 3000~)

Ahora que $N$ ~N~ es mayor, la búsqueda exhaustiva no es viable, por lo que reduciremos el problema a encontrar la longitud mínima de una subcadena que contiene una cadena $JOI$ ~JOI~ de nivel $K$ ~K~ como subsecuencia. Para ello fijaremos el extremo izquierdo, lo cual nos permite hacer este cáculo en $O(N)$ ~O(N)~. Teniendo en cuenta que solo hay $N$ ~N~ opciones para el extremo izquierdo, la complejidad total es de $O(N^2)$ ~O(N^2)~.

Subtarea $3$ ~3~ ( $N \leq 200 000$ ~N \leq 200 000~)

Sin restricciones adicionales nuestra solucion en $O(N^2)$ ~O(N^2)~ se queda corta. ¿Podemos aprovechar las características de una cadena $JOI$ ~JOI~ de nivel $K$ ~K~ para acelerar el cálculo del extremo derecho? Resulta que si. Primero fijaremos el extremo izquierdo y, a partir de ahi, utilizaremos el metodo de dos punteros para calcular las posiciones del $K$ ~K~-ésimo caracter a partir de él en $O(N)$ ~O(N)~. Haremos esto para cada letra. Teniendo esto, podemos calcular el extremo derecho en $O(1)$ ~O(1)~, con lo cual la complejidad final termina siendo $O(N)$ ~O(N)~.

Comments

There are no comments at the moment.