# Editorial - XIII Concurso Anual de Programación "Donald Knuth"

## Coffee bar
*Autor: marckess*

Este es un ejercicio de entrada y salida estándar. Se puede resolver leyendo la cantidad $n$ de elementos en la lista y los elementos de la misma. Al final, se puede imprimir cualquier elemento de la lista, por ejemplo, el primer elemento.

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125885667)

## Huron Jam
*Autor: marckess*

Intuitivamente podemos observar que la mejor estrategia para formar los equipos es emparejar a los estudiantes que se encuentren en posiciones adyacentes del arreglo ordenado, ya que así se minimiza la diferencia entre las habilidades de los estudiantes. Es decir, emparejar al estudiante con menor habilidad con el segundo, al tercero con el cuarto, y así. El arreglo de habilidades ya está ordenado en la entrada, por lo que la respuesta es simplemente $|a_1-a_2|+|a_3-a_4|+\dots+|a_{n-1}-a_n|$.

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125885679)

## Ultimate Huron Sorting
*Autor: marckess*

Se puede demostrar que todos los arreglos se pueden ordenar por medio de una secuencia de intercambios entre pares de elementos (y en consecuencia también las permutaciones). ¿Pero qué ocurre con las permutaciones cuando tenemos la restricción de no poder mover el elemento $x$?

Una permutación ordenada será de la forma $[1,2,\dots,n]$, donde el elemento $i$ debe estar en la posición $i$, para toda $1 \leq i \leq n$. Es por ello que no podemos elegir una $x$ tal que el elemento $x$ no está en la posición $x$. Dicho de otra forma, sólo podemos elegir elementos $x$ que inicialmente estén en su posición, de esta forma se pueden ordenar los elementos restantes por medio de intercambios.

En resumen, la solución es contar la cantidad de posiciones de la permutación que cumplan que $p_x=x$.

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125885687)

## Sightseeing with Friends
*Autor: DOOM*

Una primera propuesta de solución que varios participantes intentaron fue que para hallar la respuesta de cada una de las $Q$ parejas de amigos, buscaban entre todas las $N$ fotos si en alguna de ellas aparecía. Primero veamos por qué esta solución no es aceptada.

La complejidad de dicha solución es $O(N*Q)$, es decir que en el peor de los casos tendríamos que hacer $N*Q=10^6*10^6=10^{12}$ comparaciones dados los límites de $N$ y $Q$. Una aproximación que solemos utilizar en concursos para saber cuánto tiempo se tardaría nuestro programa dada la cantidad de operaciones, es considerar que en un segundo la computadora puede realizar alrededor de $10^8$ operaciones. Tomando esto en cuenta, podemos ver que nuestro programa necesitaría hasta $10000$ segundos en terminar en el peor caso (más de $2$ horas y media), mientras que el límite de tiempo en el problema era 3 segundos.

Necesitamos pensar en una solución más eficiente para hallar la respuesta de cada pareja. Supongamos que $u < v$ (si nos dan la pareja al revés, simplemente intercambiamos $u$ y $v$). Solo nos interesan las fotos $p$, tal que el rango de la foto empieza antes o en $u$ (formalmente, las fotos $p$ tal que $l_p \leq u$), ya que en las otras fotos podemos estar seguros de que $u$ no aparecerá.

Iterar sobre dichas fotos aún no es suficiente para hallar la respuesta, ya que la complejidad sigue siendo la misma, ¿pero qué pasaría si tuviéramos una forma de hallar eficientemente cuál es la foto $p$ que empieza antes o en $u$ y que termina más a la derecha? Es decir, la foto $p$ tal que $l_p \leq u$ y que $r_p$ es la máxima entre estas fotos. Si encontramos dicha foto, podemos asegurar que la respuesta es **Yes** si $v \leq r_p$ (ya que $l_u \leq u < v \leq r_p$), y **No** en caso contrario, ya que cualquier otra foto que empiece antes de $u$ tendrá un final $r_p$ menor y no contendrá a $v$.

Tenemos varias opciones para hallar este valor de $r_p$, como por ejemplo Segment Tree, BIT o un barrido acumulativo (o prefix-sum en inglés). Veamos la solución con este último.

Sea $a$ un arreglo auxiliar con todos sus elementos inicializados en $-1$. Para cada foto $p$, asignemos $a[l_p]=\max(a[l_p], r_p)$. Al final de este proceso, el elemento $a[i]$ contendrá cuál es el mayor final para una foto que empieza en la posición $i$, o $-1$ si ninguna foto empieza en el índice $i$. Finalmente iteremos para $i$ desde $i=2$ hasta $i=n$ y asignemos $a[i]=\max(a[i-1],a[i])$. Después de este proceso, el elemento $a[i]$ contendrá cuál es el mayor final $r_p$ para una foto $p$ que empieza antes o en $i$, que es justo lo que buscábamos.

Una vez teniendo el arreglo $a$ podemos contestar fácilmente la consulta de cada pareja de amigos. La complejidad final de la solución es $O(N+Q)$.

<details>
<summary>
Notas sobre la solución con BIT (Fenwick Tree)
</summary>
Posiblemente cuando algunos aprendieron BIT, leyeron o escucharon que no se podía utilizar para encontrar el mayor o menor elemento en un rango. Esto es cierto en el caso general, sin embargo, el BIT sí se puede utilizar para encontrar el mayor o menor elemento en un prefijo o un sufijo. En este problema nos interesa encontrar el mayor final de las fotos que empiezan entre 1 y u, es decir el mayor en un prefijo, por lo que se puede utilizar el BIT para esto.
</details>

<br />

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125885698)

## Coins game (easy version)
*Autor: alaneos777*

El hecho de que la cantidad de pasos para finalizar el juego sea finita, y que de cada configuración de monedas podamos llegar a exactamente otra configuración (o a ninguna si ya se terminó el juego), nos dice que podemos crear un grafo dirigido acíclico, cuyos $2^n$ nodos representan a las diferentes configuraciones, y las aristas las transiciones del juego.

De forma conveniente, podemos representar una configuración con un número binario (máscara) de $n$ bits, donde Águila es $0$ y Sol es $1$. Sea $steps(mask)$ el número de pasos que le toma a la configuración dada por $mask$ para terminar. Tenemos la siguiente recurrencia:
$$
steps(mask) =
\begin{cases}
0 &\mbox{si $mask = \underbrace{1 \ldots 1}_{n \text{ unos}} = 2^n-1$} \\
1 + steps(mask \oplus 2^{k-1}) &\mbox{donde $k \geq 1$ es el número de ceros en $mask$}
\end{cases}
$$

Es decir:
- El caso base es cuando ya llegamos a puros unos (Soles) y ahí ya no hay movimiento qué hacer.
- Si hay al menos un cero (Águila) en $mask$, volteamos la $k$-ésima moneda, o sea, si hay un 0 lo cambiamos a 1 y viceversa. Esto se puede realizar con la operación lógica ``xor``: hacemos ``xor`` de $mask$ con otro número binario que tenga un 1 en la $k$-ésima posición y ceros en los demás lugares, dicho número es $2^{k-1}$ (le restamos $1$ a $k$ ya que los bits se indexan en cero).

Usando la recurrencia anterior, la respuesta está dada por sumar para cada máscara su número de pasos y dividir entre $2^n$:

$$
ans(n) = \dfrac{1}{2^n} \sum_{mask=0}^{2^n-1} steps(mask)
$$

Tenemos que usar programación dinámica para memoizar todos los estados posibles, logrando así una complejidad temporal y espacial de $O(2^n)$.

Otra posible solución es simular el juego para cada máscara, lo cual toma $O(n^2 2^n)$ en tiempo y memoria $O(1)$.

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125889896)

## Coins game (hard version)
*Autor: alaneos777*

Para resolver el problema con $n \leq 10^9$ tenemos que analizar el grafo dirigido que se forma más a detalle.

Sea $ans(n)$ la respuesta para $n$ monedas. Sea $G_n$ el grafo que se forma con $n$ monedas, veamos cómo construirlo recursivamente con $G_{n-1}$:
- $G_0$ solo tiene un nodo que representa a la cadena vacía.
- Si $n \geq 1$, tomemos dos copias de $G_{n-1}$, llamémoslas $X$ y $Y$:
- En el grafo $X$, tomamos cada cadena de $n-1$ monedas y les concatenamos un $1$ al final.
- En el grafo $Y$, tomamos cada cadena de $n-1$ monedas, las reverseamos, las volteamos y les concatenamos un $0$ al final.
- Añadimos una arista de $Y$ a $X$, la que representa la transición $\underbrace{0 \ldots 0}_{n-1\text{ ceros}}0 \to \underbrace{0\ldots 0}_{n-1\text{ ceros}}1$.

Demostración de que la construcción anterior es correcta:
- Vemos que el grafo original $X$ tenía como respuesta $ans(n-1)$, y luego de agregarles el $1$ al final, el número de pasos promedio se mantendrá igual, pues el número de Águilas no cambió.
- También vemos que si una cadena en el grafo original $Y$ tenía $k$ ceros, entonces luego de haberlas reverseado, volteado y agregarles un $0$ al final, las cadenas tendrán $(n-1-k)+1=n-k$ ceros. Luego, las monedas en $Y$ toman primero en promedio $ans(n-1)$ pasos en llegar a $\underbrace{0 \ldots 0}_{n\text{ ceros}}$ y luego $n$ pasos adicionales para llegar a $\underbrace{1 \ldots 1}_{n\text{ unos}}$ y terminar el juego.
- La transición de $Y$ a $X$ es correcta, pues hay $n$ ceros y hay que voltear la última moneda de cero a uno.

Por lo tanto, tenemos la siguiente recurrencia, que es el promedio de los dos casos anteriores:
$$
ans(n) = \dfrac{1}{2} [\underbrace{ans(n-1)}_{\text{grafo }X} + \underbrace{ans(n-1)+n}_{\text{grafo }Y}] = ans(n-1) + \dfrac{n}{2}
$$

El caso base es $ans(0)=0$, y como en en $n$-ésimo paso estamos sumando $\frac{n}{2}$ al acumulado, tenemos que:
$$
ans(n) = \dfrac{1}{2}(1+2+\cdots+n) = \dfrac{n(n+1)}{4}
$$

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125889920)

## Moss Growing
*Autor: marckess*

El problema nos pide encontrar cuántos días deben pasar hasta que todas las celdas estén llenas. Una vez que todas las celdas estén ocupadas, los días siguientes se seguirá cumpliendo esta condición, por lo que se puede realizar una búsqueda binaria para hallar la respuesta. Nuestro espacio de búsqueda puede ser en el rango $[0,M]$, ahora sólo nos falta ver si se cumple la condición en un determinado día $k$.

Primero notemos que podemos representar las regiones ocupadas por musgo como una unión de $N$ rectángulos. En el día $k$, la $i$-ésima mancha de musgo aportará el rectángulo que ocupa las casillas entre las filas $\max(x_i-k, 1)$ y $\min(x_i+k,M)$, y entre las columnas $\max(y_i-k,1)$ y $\min(y_i+k,M)$.

Esta unión de rectángulos se puede hallar con un algoritmo basado en *sweep line*. El área de la unión de los rectángulos es igual a $M^2$ si y sólo si todas las casillas están ocupadas por el musgo. Sin embargo, los límites en la cantidad de rectángulos ($N \leq 1000$) permitía una solución alternativa en caso de no estar familiarizado con el algoritmo para hallar el área de la unión.

Notemos que si existe una región de celdas vacías, entonces esta región colinda con al menos uno de los rectángulos. Esto implica que si existe un espacio vacío, entonces al menos uno de los rectángulos toca una celda vacía. Busquemos si existe dicha celda vacía. Consideremos $2N$ filas candidatas: $x_i-k-1$ y $x_i+k+1$ para cada $i$ válida y busquemos si existe un espacio vacío en estas filas (y de forma similar en las columnas). Ignoremos las filas menores a $1$ o mayores a $M$.

Para hallar si existe un espacio vacío en la $j$-ésima fila, primero encontremos todos los rangos en esta fila ocupada por los rectángulos. El rectángulo $i$ ocupa el rango $[\max(y_i-k,1), \min(y_i+k,M)]$ si y sólo si $\max(x_i-k, 1) \leq j \leq \min(x_i+k,M)$. Una vez que obtengamos todos los rangos, ordenémoslos por su inicio y procesémoslos en ese orden. Sea $mx$ la máxima casilla ocupada que hemos encontrado hasta el momento (inicialmente $mx=0$). Si al procesar el rango $[a,b]$ se cumple que $mx+1<a$, entonces encontramos un espacio vacío ($mx+1$). En caso contrario, asignamos $mx := \max(mx, b)$. Si al después de procesar los rangos $mx<M$ entonces hay un espacio en blanco al final.

La complejidad final es $O(N^2\log^2(N))$ o $O(N^2\log(N))$. También se puede observar que por las condiciones del problema, es suficiente con considerar las filas candidatas sin necesidad de considerar columnas candidatas.

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125885739)

## Special bracelets
*Autor: alaneos777, special thanks to my wife [Tafnes](https://codeforces.com/profile/tafneemon)*

Para contar el número de pares distintos de brazaletes $(B_A, B_T)$, donde $B_A$ tiene tamaño $m$ y $B_T$ tiene tamaño $n$, tomemos cualquier permutación $\pi(s)$ de la cadena original $s$ con las $m+n$ cuentas, luego tomemos las primeras $m$ letras para formar $B_A$ y luego las últimas $n$ letras para formar $B_T$.

Sea $k$ el número de letras distintas en las cuentas, y sean $c_1, c_2, \ldots, c_k$ las frecuencias de cada una. Entonces tenemos que $c_1 + c_2 + \cdots + c_k = m+n$.

Sin la condición de que los brazaletes sean únicos bajo rotaciones, este problema se convierte en uno muy conocido de combinatoria, y la respuesta solo sería el número distinto de permutaciones de la cadena $s$, es decir, el coeficiente multinomial $\displaystyle \binom{m+n}{c_1, c_2, \ldots, c_k} = \dfrac{(m+n)!}{c_1! c_2! \cdots c_k!}$.

Para resolver el problema tomando en cuenta las rotaciones, puede que haya muchas maneras (y más fáciles) de resolverlo, pero veamos una forma muy general y poderosa usando el teorema de enumeración de Pólya. Tenemos dos grupos actuando sobre todas las permutaciones de $s$: el grupo cíclico $C_m$ actuando en las primeras $m$ letras, y el grupo cíclico $C_n$ actuando en las $n$ letras restantes. Sabemos que el cycle index polynomial del grupo cíclico $C_m$ es $Z(C_m) = \dfrac{1}{m} \sum_{d | m} \varphi(d) {z_d}^{m/d}$, pero como $m$ y $n$ son números primos, tenemos que: $Z(C_m) = \dfrac{1}{m} ({z_1}^m + (m-1)z_m)$ y $Z(C_n) = \dfrac{1}{n} ({z_1}^n + (n-1)z_n)$.

Pero ahora, ¿cómo encontramos el cycle index polynomial de la acción combinada de ambos grupos? Resulta que la forma de hacerlo es muy intuitiva: es solo el producto de ambos cycle index polynomials. Sea $G$ el grupo actuando en la cadena completa, entonces $Z(G) = Z(C_m) Z(C_n) = \dfrac{1}{mn} ({z_1}^{m+n} + (m-1){z_m}{z_1}^n + (n-1){z_1}^m{z_n} + (m-1)(n-1){z_m}{z_n})$.

Luego, tenemos que aplicar el teorema de enumeración de Pólya. Asignemos las etiquetas $x_1, x_2, \ldots, x_k$ a cada letra distinta $s$. Ahora, para obtener la función generadora o el "inventario" de todas las posibles permutaciones, necesitamos evaluar el polinomio $Z(G)$ sustituyendo $z_i = {x_1}^i + {x_2}^i + \cdots + {x_k}^i$ para cada $i \in \{1,m,n\}$. Entonces, la función generadora es:

$$
\begin{align}
F =& \frac{1}{mn} [(x_1 + x_2 + \cdots + x_k)^{m+n} \\
&+ (m-1)({x_1}^m + {x_2}^m + \cdots + {x_k}^m)(x_1 + x_2 + \cdots + x_k)^n \\
&+ (n-1)(x_1 + x_2 + \cdots + x_k)^m({x_1}^n + {x_2}^n + \cdots + {x_k}^n) \\
&+ (m-1)(n-1)({x_1}^m + {x_2}^m + \cdots + {x_k}^m)({x_1}^n + {x_2}^n + \cdots + {x_k}^n)]
\end{align}
$$

Finalmente, para obtener el número de permutaciones de $s$ que contienen las cuentas distribuidas de acorde a las frecuencias $c_1, c_2, \ldots, c_k$, necesitamos encontrar el coeficiente de ${x_1}^{c_1} {x_2}^{c_2} \cdots {x_k}^{c_k}$ en la función generadora $F$. Hagámoslo por partes y con ayuda del teorema multinomial:

- El coeficiente buscado en $(x_1 + x_2 + \cdots + x_k)^{m+n}$ es $\displaystyle \binom{m+n}{c_1, c_2, \ldots, c_k} = \dfrac{(m+n)!}{c_1! c_2! \cdots c_k!}$, de nuevo por el teorema multinomial.
- Para obtener el coeficiente buscado en $({x_1}^m + {x_2}^m + \cdots + {x_k}^m)(x_1 + x_2 + \cdots + x_k)^n$, para cada $1 \leq i \leq k$ obtenemos el coeficiente de ${x_1}^{c_1} \cdots {x_i}^{c_i - m} \cdots {x_k}^{c_k}$ en $(x_1 + x_2 + \cdots + x_k)^n$ de nuevo con el teorema multinomial.
- Para obtener el coeficiente buscado en $(x_1 + x_2 + \cdots + x_k)^m({x_1}^n + {x_2}^n + \cdots + {x_k}^n)$ y en $({x_1}^m + {x_2}^m + \cdots + {x_k}^m)({x_1}^n + {x_2}^n + \cdots + {x_k}^n)$ seguimos de forma muy similar los pasos anteriores.

El último paso solo es sumar los cuatro valores anteriores y dividir entre $mn$. La complejidad es $O(m+n+\lvert\Sigma\rvert^2)$, donde $\lvert\Sigma\rvert$ es el tamaño del alfabeto ($26$ en este caso).

**Ejemplo 1**: supongamos que $s=\texttt{holi}$, $m=2$ y $n=2$. Las frecuencias son $[1,1,1,1]$, por lo que $k=4$. Entonces:
$$
Z=\dfrac{1}{4}(z_1^4 + 2z_2z_1^2 +z_2^2)
$$

Luego, sustituyendo $z_i=a^i+b^i+c^i+d^i$ para $i=1,2$ tenemos que:

$$
F=\dfrac{1}{4}((a+b+c+d)^4 + 2(a^2+b^2+c^2+d^2)(a+b+c+d)^2+(a^2+b^2+c^2+d^2)^2)
$$

Expandiendo y hallando el coeficiente de $abcd$, vemos que es 6.

**Ejemplo 2:** $s=\texttt{aabeinottt}$, $m=3$ y $n=7$. Las frecuencias son $[2,1,1,1,1,1,3]$, por lo que $k=7$. Entonces:
$$
Z = \dfrac{1}{21}(z_1^{10} + 2z_3z_1^7 + 6z_1^3z_7 + 12z_3z_7)
$$

Luego, sustituyendo $z_i=x_1^i + \cdots + x_7^i$ para $i=1,3,7$ tenemos que:
$$
\begin{align}
F = &\dfrac{1}{21}[(x_1+\cdots+x_7)^{10}\\
&+ 2(x_1^3+\cdots+x_7^3)(x_1+\cdots+x_7)^7\\
&+ 6(x_1+\cdots+x_7)^3(x_1^7+\cdots+x_7^7)\\
&+ 12(x_1^3+\cdots+x_7^3)(x_1^7+\cdots+x_7^7)]
\end{align}
$$

- El coeficiente de $x_1^2 x_2 x_3 x_4 x_5 x_6 x_7^3$ en $(x_1+\cdots+x_7)^{10}$ es $\displaystyle \binom{10}{2,1,1,1,1,1,3}=302400$.
- El coeficiente de $x_1^2 x_2 x_3 x_4 x_5 x_6 x_7^3$ en $(x_1^3+\cdots+x_7^3)(x_1+\cdots+x_7)^7$ es $\displaystyle \binom{7}{2,1,1,1,1,1,0} = 2520$.
- El coeficiente de $x_1^2 x_2 x_3 x_4 x_5 x_6 x_7^3$ en $(x_1+\cdots+x_7)^3(x_1^7+\cdots+x_7^7)$ es $0$.
- El coeficiente de $x_1^2 x_2 x_3 x_4 x_5 x_6 x_7^3$ en $(x_1^3+\cdots+x_7^3)(x_1^7+\cdots+x_7^7)$ es $0$.

Por lo que la respuesta es $\dfrac{1}{21}[320400 + 2(2520) + 6(0) + 12(0)] = 14640$.

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125889887)

## Truth table
*Autor: alaneos777*

Hay varias formas de resolver el problema, incluyendo el algoritmo de Shunting Yard o usando un parser por descenso recursivo. Analicemos la segunda.

Construyamos una gramática libre de contexto para tomar en cuenta la jerarquía de los operadores que nos dan y la asociatividad por la izquierda. Por ejemplo, suponiendo que tenemos 6 operadores y su jerarquía es:

2. ``and``
3. ``xor``
4. ``or``, ``nand``
5.
6. ``xnor``, ``nor``
7.

Entonces la gramática queda como (usando la notación extendida Backus-Naur):
$$
\begin{align}
E_7 &\to E_6 \\
E_6 &\to E_5 (\texttt{xnor} E_5 \hspace{0.1cm} | \hspace{0.1cm} \texttt{nor} E_5)^* \\
E_5 &\to E_4 \\
E_4 &\to E_3 (\texttt{or} E_3 \hspace{0.1cm} | \hspace{0.1cm} \texttt{nand} E_3)^* \\
E_3 &\to E_2 (\texttt{xor} E_2)^* \\
E_2 &\to E_1 (\texttt{and} E_1)^* \\
E_1 &\to \texttt{not} E_1 \hspace{0.1cm} | \hspace{0.1cm} E_0 \\
E_0 &\to \texttt{open_paren} \hspace{0.1cm} E_7 \hspace{0.1cm} \texttt{close_paren} \hspace{0.1cm} | \hspace{0.1cm} \texttt{char}
\end{align}
$$

Es decir, el no terminal $E_n$ para $n \geq 2$ representa a todos los $t$ operadores con jerarquía $n$, y tiene la forma $E_n \to E_{n-1}(\texttt{op}_1 E_{n-1} \hspace{0.1cm} | \hspace{0.1cm} \texttt{op}_2 E_{n-1} \hspace{0.1cm} | \hspace{0.1cm} \ldots \hspace{0.1cm} | \hspace{0.1cm} \texttt{op}_t E_{n-1})^*$. Esta regla no es más que una lista de expresiones del tipo $E_{n-1}$, todas concatenadas usando los operadores de jerarquía $n$. Como tenemos asociatividad por la izquierda, hay que ir aplicando el operador al acumulado conforme nos vayan llegando las expresiones.

De igual modo, $E_1$ representa al $\texttt{not}$ unario, y $E_0$ a los paréntesis y a los caracteres individuales.

La intuición de por qué esta gramática funciona es ver que los operadores que tienen menor precedencia (mayor $n$) están hasta la raíz del árbol sintáctico, por lo que se realizan hasta el final; mientras que los que tienen mayor precedencia (menor $n$) están más cerca de las hojas, por lo que se evaluarán antes.

Cada no terminal $E_n$ será una función que devolverá la evaluación de su correspondiente expresión, por lo que $E_7$ nos devolverá la respuesta final. La gramática anterior es $LL(1)$, lo que en pocas palabras significa que una cadena $s$ que pertenezca a dicha gramática puede ser procesada con un parser por descenso recursivo usando solo un token de look-ahead con una complejidad de $O(\lvert s \rvert)$.

Finalmente, tenemos que iterar por todas las $2^m$ combinaciones de valores para las variables de $s$, evaluar la expresión y hallar el hash correspondiente.

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125889962)

## HuronForces
*Autor: marckess*

Primero resolvamos una versión más simple del problema donde sólo nos interesa hallar el mejor plan. Podemos resolver esta versión con la siguiente DP de corte:

$$
dp(i,k) = \max_{i \leq j \leq n}(dp(j + 1, k - 1) + x(i,j) - y(i,j))
$$

Donde $x(i,j)$ es el mayor elemento más frecuente en la secuencia $a_i, a_{i+1}, \dots a_j$ e $y(i,j)$ es el menor elemento menos frecuente en la secuencia $a_i, a_{i+1} \dots a_j$. Estos dos valores se pueden hallar en $O(n*log(n))$ con un BST (un `std::map` en C++ por ejemplo).

Este problema de DP se puede convertir en un problema de grafos equivalente. Construyamos un grafo dirigido con pesos en las aristas. El grafo tendrá $O(N*K)$ nodos y cada nodo estará etiquetado con un par de enteros $(i,k)$. Del nodo $(i,k)$ dibuja una arista al nodo $(j+1,k-1)$ con peso $x(i,j)-y(i,j)$ para cada $i \leq j \leq n$.

También creemos un par de nodos especiales: $S$ y $T$. Dibujemos una arista de $S$ a $(1,K)$ con peso $0$. También dibujemos aristas entre los casos base $(n+1,k)$ a $T$ con peso igual a $0$, para cada $0 \leq k < K$. Ahora el problema se traduce a hallar el camino más largo de $S$ a $T$.

Volviendo a nuestro problema original donde hay que hallar los mejores $X$ planes, consideremos el grafo que acabamos de crear. Hay que hallar los $X$ caminos más largos entre $S$ y $T$. Existen algoritmos conocidos para hallar los $X$ caminos más largos entre un par de nodos, como por ejemplo el Algoritmo de Eppstein o el Algoritmo de Yan. También notemos que el grafo sobre el que estamos trabajando es un DAG, por lo que se puede utilizar una versión simplificada de éstos.

[Solución oficial](https://codeforces.com/group/in7H7a0QIx/contest/340485/submission/125885771)