## Día 1
*En construcción*

## Día 2
*En construcción*

## Día 3
### A. Ants

<details>
<summary>Solución</summary>

Find the MEX ( **m**inimum **ex**cluded value) of given set.

One way to find the MEX, is to use a set implemented in programming languages (for example, `std::set<int>` in C++) to store all the values ${X_1, X_2, ..., X_N}$. Then, iterate from $i=0$ and check if the integer $i$ is present in set, if yes, just print it and return; otherwise, just check the next number $i+1$, and so on.

A detail in this problem is that $X_i$ might have up to $100$ digits. Note that the maximum possible answer for this problem is $N$, and $N$ can have up to 7 digits. So, we can read numbers as a string, and just insert it to the set if it has at most $7$ digits. In C++ you can use `std::stoi()` to cast a string to integer.
</details>

### B. Building Palindromes
<details>
<summary>Solución</summary>

First of all, let's see what is the maximum possible number of different palindromic substrings for a string of length $n$. For a string $S$ that has $k$ different palindromic substrings, then, if we append a character $c$ to the back of $S$, $S+c$ will have at most $k+1$ palindromes. Let's prove it by contradiction, suppose that $S+c$ has at least $k+2$ different palindromic substrings. That means that there are two new palindromes induced when we append $c$, $X$ and $Y$, which are suffix of $S+c$, let's say that $|X|<|Y|$, then $X$ is a suffix of $Y$, and as $X$ and $Y$ are palindromes, then $X$ is also a prefix of $Y$, thus $X$ occurs in $S$, that means that $X$ is not a new palindrome, contradiction! (See [the image](https://drive.google.com/file/d/1q5P_RVQKW41HrKHbS2WbyZqm3xaCSUSR/view?usp=sharing) for better understanding. Note that two occurrences of X can also overlap).

Thus, a string of length $n$ can have at most $n$ different palindromic substrings.

Now, let's see what is the minimum possible number of different palindromic substring. If $n=1$, then you can easily see that the value of $k$ is $1$. If $n=2$, without loss of generality consider string $aa$ and $ab$, you can see that in both cases, the value of $k$ is $2$. If $n=3$, w.l.o.g consider strings $aaa$, $aab$, $aba$, $abb$, $abc$ (you can obtain all string of length $3$ by substitute occurrences of $a$, $b$ or $c$ in these strings with other character), the value of $k$ is $3$.

You can think that the minimum possible value of $k$ is $n$, for all $n$, but in $n=4$, the string $abca$ has three different palindromes. Generally, you can periodically repeat $abc$, and the value of $k$ will be $3$. Thus, the minimum possible value of different palindromic substrings is $min(n, 3)$.

By the previous proof, we can get a strategy to get an answer. If $min(3, n) \leq k \leq n$, then we can construct a valid substring by appending $k-min(3, n)$ times the character $x$, and then, put the remaining characters by appending periodically $abc$.

For example, if $n=10$ and $k=5$, then $xxabcabcab$ is an answer. If $n=5$ and $k=3$, then $abcab$ is an answer. If $n=10$ and $k=10$, then $xxxxxxxabc$ is an answer.

</details>

### C. Encryption
<details>
<summary>Solución</summary>

The problem basically is asking for the length of the longest palindrome in the text and how many palindromes of said length exist in the string. Because of the low constraints many approaches were available for this problem, some of those were: DP, setting a center and then checking for palindromes, etc. Even a clever $\textbf{O}(n^{3})$ with heavy pruning could get accepted. In this editorial we would like to propose another approach, that no one submitted, that coud be helpful for you in the future.

First we will analyze some properties for palindromes of odd length. If we have a palindrome of length $N$, where N is odd, we can prove that if $N \geq 3$ we will certainly have a palindrome of length $N-2$ with its center in the same character than the longer one. For example, if we have $acbca$ with $N=5$, if we get rid of the leftmost and rightmost characters we will have $cbc$ that is indeed a palindrome of length $N-2$ with its center in the same character. We can prove the same for palindromes of even length.

By knowing these properties, we can try to look for the maximum length of the palindrome with a binary search. We can do this since, if we know we have a palindrome of length $N$, we will have other palindromes of length $N-2,N-4,\dots$. It is important to do one binary search for odd length and another for even,you can easily prove why this is needed. Then, we can look for how many palindromes of a fixed length exist in the text, and keep the max length as the answer.

There is a linear approach for this problem that involves Manacher's algorithm. We encourage you to read more about this topic.

</details>

### D. Mountaing Range
<details>
<summary>Solución</summary>

First we need to find all the points that represent the peaks for every mountain, let them be $P_i$. Start with $Q:=(0,0)$, we will be accumulating the values like this for every mountain in the input:

- Let $Q:=Q+(u_i,u_i)$ (update the up-slope)
- Set $P_i:=Q$
- Let $Q:=Q+(d_i,-d_i)$ (update the down-slope)

Now, we can proceed and, for every peak, just check all the peaks from the left that are visible. We can do this in $O(n^2)$ time:

- Obviously if we are at $P_1$, we can't see anything to the left.
- If we are at $P_i$ where $i>1$, at least we can always see the previous peak $P_{i-1}$.
- Let $slope_j:=\overrightarrow{P_i P_{j}}$ the segment that joins the current peak with the peak $P_j$ ($j < i$). Let $current:=slope_{i-1}$. Then we will be checking the other peaks to the left iterating from $j=i-1$ to $j=1$ and if the segment $slope_j$ is orientated to the left or is collinear with $current$, means that we can see peak $P_j$ because nothing blocks our vision. If that happens, save the index $j$ as valid and set $current:=slope_j$. Finally just print all the valid indices.

</details>

### E. Finding Flights
<details>
<summary>Solución</summary>

**Prerequisites:** Dijkstra

Let's model this problem as a graph.

You can't have a single node for each airport, because it's matter what time you are at the aiport. So, let's create $1440$ (minutes a day) nodes for each airport. We will have $1440 * n$ nodes in our graph. Each node is identified by a pair of integers $(u,t)$ $-$ $u$ is the number of the airport and $t$ is the time.

Now, for the $i$-th flight, let's draw an edge from node $(u_i, h_i)$ to node $(v_i, (h_i + d_i + w_{v_i}))$ with cost $c_i$. $h_i + d_i$ is the arriving time, but students have to wait $w_{v_i}$ to take another flight, for that reason we add $w_{v_i}$ to $h_i + d_i$.

Students can with in the airports to take another flight, so we add an edge between node $(u,t)$ and $(u, (t + 1))$ with cost $0$ for all $1 \leq u \leq N$ and $00:00 \leq t \leq 23:59$. But there is an special case, that is when students have to stay in a hotel during the night. So, the edge between nodes $(u, 07:59)$ and $(u, 08:00)$ will have cost $k_u$, because if students waits until $07:59$, that means that they had to stay in a hotel.

Finally, let's add two more nodes $S$ and $T$. Add edges between $S$ and $(1,t)$ with cost $0$ and between nodes $(N, t)$ and $T$ with cost $0$, for all $00:00 \leq t \leq 23:59$. Find the shortest path between $S$ and $T$, with Dijkstra algorithm for example, that is the final answer.

To simplify implementation, instead of store times in $HH:MM$ format, you can save it as an integer equal to $60 * HH + MM$ (cast time to minutes). Also, remember that $(h_i + d_i + w_{v_i})$ might be greater than $1440$, so just take $(h_i + d_i + w_{v_i}) \% 1440$.

</details>

### F. Pashmak and Parmida's problem
<details>
<summary>Solución</summary>

**Prerequisites:** Fenwick Tree, Mapping numbers

First of all, we can map the given numbers to integers of range $[1, 10^6]$. Let $l_i$ be $f(1, i, a_i)$ and let $r_i$ be $f(i, n, a_i)$, we want to find the number of pairs $(i, j)$ such that $i < j$ and $l_i > r_j$. For computing $l_i$s, we can store an array named $cnt$ to show the number of occurence of any $i$ with $cnt[i]$. To do this, we can iterate from left to right and update $cnt[i]$s; also, $l_i$ would be equal to $cnt[a_i]$ at position $i$ ($r_i$ s can be computed in a similar way).

Beside that, we get help from binary-indexed trees. We use a Fenwick tree and iterate from right to left. In each state, we add the number of elements less than $l_i$ to answer and add $r_i$ to the Fenwick tree.

Total complexity : $O(n * logn)$

</details>

### G. Check the string
<details>
<summary>Solución</summary>

Traverse the string once and check if the ASCII value of all characters is greater than or equal or the ASCII value of the previous character. This ensures that the string does not have $a$,$b$,$c$ in wrong order.

Also, while traversing the string, keep three separate counters for the number of $a$, $b$ and $c$ along.

Now, do a simple check on the condition for the count of $c$.

The hack case for many solutions was to check that the count of $a$ is atleast $1$ and the count of $b$ is atleast $1$.

</details>

### H. Easy Fibonacci
<details>
<summary>Solución</summary>

**Prerrequsitos:** DP

Programar una función recursiva para hallar la solución y memorizar la respuesta.

**Sugerencia:** Utilizar entrada y salida rápida de datos.

</details>

### I. Abraham's Kingdom
<details>
<summary>Solución</summary>

**Prerrequisitos:** Disjoint Set Union (DSU), también conocido como Union-Find

[DSU](https://cp-algorithms.com/data_structures/disjoint_set_union.html) es una estructura que permite realizar las siguientes operaciones en un grafo con n nodos:
* Agregar una arista entre dos nodos $u$ y $v$.
* Obtener a qué componente pertenece el nodo $u$.

Adicionalmente, un DSU puede mantener el tamaño de todas las componentes conexas en el grafo.

En este problema se realizan $m$ actualizaciones en el grafo, donde cada operación consiste en eliminar una arista. Un DSU no soporta eliminar aristas, pero se puede utilizar una técnica llamada [Dynamic Connectivity](https://cp-algorithms.com/data_structures/deleting_in_log_n.html) para extender el DSU para que soporte eliminarlas. En la solución oficial no se utiliza Dynamic Connectivity (aunque es posible resolverlo así), en su lugar se usa una solución más simple.

Podemos mirar las $m$ actualizaciones al revés: empezando desde el grafo que resulta cuando eliminamos todas las aristas, después agregando la última arista que se eliminó, después agregando la penúltima arista que se eliminó y así. De esta forma obtenemos todos los estados por los que pasó el grafo pero en orden contrario.

Las queries de a cuántas otras ciudades puede llegar una ciudad $t$ después de eliminar la $x$-ésima arista se pueden responder de forma **offline**, agrupando todas las queries que tienen la misma $x$ y contestandolas antes de que agreguemos la arista $x$. Para contestar hay que utilizar la función del DSU para buscar en qué componente estar y contestar con el tamaño de la componente.

</details>

### J. Kefa and First Steps
<details>
<summary>Solución</summary>

Note, that if the array has two intersecting continuous non-decreasing subsequence, they can be combined into one. Therefore, you can just pass the array from left to right. If the current subsequence can be continued using the i-th element, then we do it, otherwise we start a new one. The answer is the maximum subsequence of all the found ones.

Asymptotics — $O(n)$.

</details>

### K. Weirdmageddon
<details>
<summary>Solución</summary>

**Prerrequisitos:** Interpolación de Lagrange

First let's state what Lagrange Interpolation tells us: if we have $m$ distinct points $(x_1, y_1)$, $(x_2, y_2)$, $\ldots$, $(x_m, y_m)$, there is exactly one polynomial $P(x)$ of degree less than or equal to $m-1$ which passes through all points, i.e., we have $P(x_i)=y_i$ for all $i$ between $1$ and $m$. And we also have a nice formula to find it:

$$ \displaystyle P(x) = \sum_{i=1}^{m} y_i \prod_{i=1 , i \neq j}^{m} \dfrac{x - x_j}{x_i - x_j}$$

Hence, in this task first we would like to find the original polynomial $P(x)$ in order to find the key $a_0$. But we don't need all the coefficients because $a_0=P(0)$, so if we have some key-pairs, we can find the key by plugging $x=0$ in the Lagrange formula.

We are given that the degree of $P(x)$ was $k-1$ and that $n \geq k$, hence if we use all the $n$ key-pairs given in the input, we can always find the correct key $a_0$. Unfortunately, the complexity of the formula is $O(n^2)$, too slow, but notice that we are also given that we need at most $10^3$ key-pairs to find the correct key, so let $m=\min(10^3,n)$ and just take any $m$ key-pairs to find the key (for simplicity, you can take the first $m$ key-pairs).

Now, note that the minimum key-pairs needed is just the value of $k$ of the original polynomial $P(x)$. To find it, notice that if we use more than $m$ key-pairs to find the key, we will always obtain the same correct key. If we use less than $m$, we will always obtain an incorrect value. This tells us that we must use a binary search to find the minimum value of $k$ such that if we interpolate $k$ key-pairs, we obtain the correct $a_0$.

The proposed complexity is then $O(m^2 \log m)$, although you can also solve it in $O(m \log m)$ if you take the first $m$ key-pairs from the input and do the interpolation in $O(m)$ (left as an exercise, the formula simplifies very nicely).

Don't forget to do all the arithmetic modulo $M$. That means that the divisions in the formula have to be replaced with the modular inverse, be careful with overflowing and printing negative values.

Cultural fact: this encryption scheme really exists and it's called *Shamir secret sharing*.

</details>

### L. Beautiful Paintings
<details>
<summary>Solución</summary>

Lets look at the optimal answer. It will contain several segment of increasing beauty and between them there will be drops in the beautifulness. Solution is greedy. Lets sort all paintings and lets select which of them will be in the first increasing segment. We just go from left to right and select only one painting from each group of several paintings with the fixed beauty value. We continue this operation while there is at least one painting left.

With the careful implementation we will get $O(nlogn)$ solution.

But this solution gives us the whole sequence, but the problem was a little bit easier — to determine number of such segments. From the way we construct answer it is easy to see that the number of segments always equal to the maximal number of copies of one value. Obviously we can't get less segments than that and our algorithm gives us exactly this number. This solution is $O(n)$.

</details>

### K. Kids at the Party
<details>
<summary>Solución</summary>

[Consultar solución usando este enlace](https://drive.google.com/file/d/1uqfCSApjntYTG28aLgfWbPKMbhBMNkGM/view).

</details>

## Día 4
### A. Bachgold Problem
<details>
<summary>Solución</summary>

We need represent integer number $N$ $(1 < N)$ as a sum of maximum possible number of prime numbers, they don’t have to be different.

If $N$ is even number, we can represent it as sum of only $2$ &mdash; minimal prime number. It is minimal prime number, so number of primes in sum is maximal in this case.

If $N$ is odd number, we can use representing of $N$ - $1$ as sum with only $2$ and replace last summand from $2$ to $3$.

Using of any prime $P > 3$ as summand is not optimal, because it can be replaced by more than one $2$ and $3$.

</details>

### B. Daily Training
<details>
<summary>Solución</summary>

**Prerrequisitos: DP de corte**

Given an array $A=[a_1, a_2, ..., a_N]$, find the maximum value obtainable by cutting up the array in at most $K$ subarrays. The value of a subarray $[a_i,...,a_j]$ is determined by $x_{i...j}-y_{i...j}$, where $x_{i...j}$ is the most frequent element in the subarray (if there are multiple such values, $x_{i...j}$ is the maximum among them) and $y_{i...j}$ is the least frequent element in the subarray (if there are multiple such values, $y_{i...j}$ is the minimum among them).

We can solve this problem by dynamic programming. Let $dp(i,k)$ be the maximum value obtainable by cutting the subarray $[a_i, a_{i+1},..., a_{n-1}, a_N]$ in at most $k$ parts. The base cases are $dp(n+1,k)=0$ and $dp(i, 1)=x_{i...N}-y_{i...N}$. Otherwise, you can cut a prefix of the subarray and solve the same problem for the reaming subarray. So, the value of $dp(i,k)$ is the maximum value among $(x_{i...j} - y_{i...j}) + dp(j + 1, k - 1)$ for all $i \leq j \leq N$.

To calculate $x_{i...j}$ and $y_{i...j}$, you can iterate from $j=i$ to $j=N$ and store the frequency of numbers in a bucket, vectors or map. Also, mantain a BST (`std::set` in C++ for example) of pairs $(frequency,number)$ and update it each iteration, so you can easily get the value of $x_{i...j}$ and $y_{i...j}$.

Total complexity: $O(n^2*k*log(n))$. You can also solve this problem in $O(n^3*k)$ carefully implementing a solution to avoid a **TLE**.

</details>

### C. Maximum of Maximums of Minimums
<details>
<summary>Solución</summary>

$k ≥ 3$:  then let $posmax$ be the position of the element with the maximum value, then it is always possible to divide the array into subsegments so that one subsegment contains only this number, so the answer to the problem is $a_{posmax}$.

$k = 2$:  then all possible partitions are some prefix of nonzero length and corresponding suffix of nonzero length. You can iterate through all positions of the prefix end, and сalculate the answer for this fixed partition, that equals to maximum of minima on the prefix and on the suffix. Minimum value for all suffixes and prefixes can be counted in advance. The answer is the maximum of the answers for all possible partitions.

*Also it can be proved that for $k = 2$ the answer is the maximum of the first and last element.

$k = 1$:  then the only possible partition is one segment equal to the whole array. So the answer is the minimum value on the whole array.

</details>

### D. Game on Trees
<details>
<summary>Solución</summary>

**Prerequisites:** Impartial games, Grundy numbers and Sprague–Grundy theorem

Note that this is a finite impartial game, so you can assign a Grundy number to each state of the game.

First, let's see how to assign Grundy numbers to a single tree. You can iterate from branch $u=1$ to branch $b_i$, the Grundy number of the $u$-th branch is the MEX of Grundy numbers of all branches $v$ connected to $u$ by a rope, such that $v<u$.

Each of the trees are independent games, so, by Sprague–Grundy theorem, you can know apply nimber addition to the Grundy numbers of the initial branches to know the answer: if it is $0$, then Bob wins, otherwise, Alice wins. Formally, let $G_i(j)$ be the Grundy number of the $j$-th branch of the $i$-th tree, Bob wins the $i$-th game if $G_1(a_{i,1}) \oplus G_2(a_{i,2}) \oplus ... \oplus G_N(a_{i,N}) = 0$; otherwise, Alice wins.

</details>

### E. Game Shopping
<details>
<summary>Solución</summary>

Let's keep the variable $pos$ which will represent the number of games Maxim buy. Initially $pos=0$. Assume that arrays $a$ and $c$ are $0$-indexed. Then let's iterate over all $i=0...n−1$ and if $pos<m$ and $a[pos]≥c[i]$ make $pos:=pos+1$. So $pos$ will be the answer after this cycle.

</details>

### F. Conquering GCD Tree
<details>
<summary>Solución</summary>

If the greatest common divisor of a set of numbers is not 1, it means that there exists some prime $p$ that divides the greatest common divisor.
So we can construct a graph for each prime number $p$, city u belongs to this graph if and only if p divides $h_{u}$. For each graph, we can get the maximum number of nodes in each component with a dfs/bfs.

</details>

### G. Biathlon
<details>
<summary>Solución</summary>

First we will sort the circles ascendently by their center coordinates. Then, for every point we will do a binary search to find the first circle to the left of this point and the first one to the right. This binary search will only compare the x coordinates. We can prove that we do not have to compare each point to any other circles that the two we find with the binary search, since the distances to any other would be greater.

Then we will just get the distance from the center of each circle to the point. If the distance is less than or equal to the radius of the corresponding circle, then we can say that the point is in the circle. We can find the distance with the Pythagorean theorem. Just take in mind the case where two circles touch each other and the point is exactly in the intersection.

</details>

### H. Odd sum
<details>

The answer to this problem can be constructed this way:

1. Sum up all positive numbers
2. Find maximum $max_{odd}$ of negative odd numbers
3. Find minimum $min_{odd}$ of positive odd numbers
4. If sum was even then subtract $min(min_{odd},  -max_{odd})$

Overall complexity: $O(n)$.

This problem can also be solved by DP, with states $idx$ and the parity of current sum.

</details>

### I. Alternating signs
<details>
<summary>Solución</summary>

Consider the following dynamic programming: $dp(idx,lastsign)$, that returns the maximum sum of the elements that appears in or after position $idx$. If $a[idx]$ has the same sign that $lastsign$, the value of $dp(idx,lastsign)$ is $dp(idx+1,lastsign)$. Otherwise, $dp(idx,lastsign)=max(dp(idx+1,lastsign), dp(idx+1,-lastsign) + -lastsign * a[idx])$. Final answer will be $max(dp(1,+), dp(1,-))$.

Complexity: $O(n)$.

</details>

### J. Huron Sorting
<details>
<summary>Solución</summary>

Este es el problema H en la siguiente editorial: https://drive.google.com/file/d/1WtsuMweOW0MRDXNkzL46DdpGjJuO_oo8/view

La solución requiere tener familiaridad con la descomposición en ciclos disjuntos de una permutación. La descompocisión en ciclos disjuntos de una permutación permite resolver varios problemas con permutaciones. Se recomienda el siguiente blog para estudiarlo: https://codeforces.com/blog/entry/111187
</details>

### K. Souvenirs
<details>

**Prerequisites:** Meet in the Middle, Bitmasks

Description of problem: Distribute each of the $n$ souvenirs in two sets: $S$ and $V$. Minimize the absolute difference between the sum of all the $s_i$ such that $i$ is in $S$, and the sum of all the $v_j$ such that $j$ is in $V$.

Solution: Note that there are $2^n$ possible distributions of souvenirs. Thus, if $n \leq 20$, then you can simulate all possible distributions. Use bitmasks of $n$ bits to simulate distributions, if the $i$-th bit is set in bitmask, then put souvenir $i$ in $S$, otherwise put it in $V$. Consider all bitmasks in range $[0, 2^n)$ and store the bitmask that gives the minimum absolute difference between the happines of friends.

What if $n>20$? Let's use meet in the middle technique. You can divide the souvenirs in two subarrays $A$ and $B$. $A$ will have the first $floor(n/2)$ and $B$ will have the last $ceil(n/2)$ elements. Subarrays $A$ and $B$ have at most $20$ elements, so you can simulate all possible distributions in $A$ and all possible distributions in $B$.

Now, let's see how to combine information of two subarrays to get the final answer. Store all possible signed differences that you can get in a distribution of subarray $A$ and the bitmask that gives that difference. Then, for all distributions in subarray $B$, let $d$ be the signed difference of that distribution of $B$, if there is a distribution that gives a difference equal to $-d$ in the map of $A$, then you can combine these distributions of $A$ and $B$ to get a final distribution with absolute difference equeal to $0$. But, if there is no such then find the difference in the map that is closest to $-d$, because this minimize total absolute difference, you can find that by lower_bound in map. Note that you have to consider least value that is greater than $-d$ and the greatest value that is less than $-d$.

Complecity: $O(n*2^n)$.

</details>

### L. Weird Rounding
<details>
<summary>Solución</summary>

To solve this problem we need to make $k$ zeroes in the end of number $n$. Let's look on the given number as on the string and iterate through it beginning from the end (i.e. from the low order digit). Let $cnt$ equals to the number of digits which we reviewed. If the current digit does not equal to zero we need to increase the answer on one. If $cnt$ became equal to $k$ and we reviewed not all digits we need to print the answer.

In the other case we need to remove from the string all digits except one, which equals to zero (if there are more than one such digit we left only one of them). Such digit always exists because the problem statement guaranteed that the answer exists.

</details>

### M. Palindrome Pairs
<details>
<summary>Solución</summary>

For each string we need to remember the parity of the occurrences of each letter. If permutation of the concatenation of two strings makes a palindrome, this means that only one letter appears an odd number of times.

To have a permutation of the concatenation of two strings that make a palindrome, the parity of the occurrence of each letter in both strings can be distinguished only in one position.

It is necessary to find foreach string how many strings there are, so that their series of parity differ in only one position.

Make a mask where the $i$-th position signifies the parity of the $i$-th letter in the alphabet. Memorize each mask as many times as it appears. We will use a map.

Iterate through all the strings, add the number of masks that differ in only one position from the current mask of string to the solution. As each two strings have evolved twice, the solution will be divided by $2$. Time complexity: $O(NlogN)$.

</details>

## Día 5

### A. Ultimate Huron Sorting
<details>
<summary>Solución</summary>

Ver en: https://hackmd.io/@rapc-ipn/HJFezxJbK

</details>

### B. Mass Growing
<details>
<summary>Solución</summary>

Ver en: https://hackmd.io/@rapc-ipn/HJFezxJbK

</details>

### C. Max mod min
<details>
<summary>Solución</summary>

Ver en: https://atcoder.jp/contests/arc147/editorial/4762

</details>

### D. Sightseeing with Friends
<details>
<summary>Solución</summary>

Ver en: https://hackmd.io/@rapc-ipn/HJFezxJbK

</details>

### E. Huron Jam
<details>
<summary>Solución</summary>

Ver en: https://hackmd.io/@rapc-ipn/HJFezxJbK

</details>

### F. Noonerized Spumbers
<details>
<summary>Solución</summary>

Ver en: https://hyabc.github.io/ecna21/ (posiblemente extienda la solución más adelante).

</details>

### G. Good pairs
<details>
<summary>Solución</summary>

Ver en: https://discuss.codechef.com/t/maxor-ediorial/15798

</details>

### H. Submask
<details>
<summary>Solución</summary>

Ver en: https://atcoder.jp/contests/abc269/editorial/4899

</details>

### I. Thanos Nim
<details>
<summary>Solución</summary>

Ver en: https://codeforces.com/blog/entry/66878

</details>

### J. Coffe Bar
<details>
<summary>Solución</summary>

Ver en: https://hackmd.io/@rapc-ipn/HJFezxJbK

</details>

### K. In case of failure
<details>
<summary>Solución</summary>

El problema es una aplicación directa de la estructura de datos KD-Tree, la cual se puede consultar en el siguiente enlace: https://codeforces.com/blog/entry/54080

En resumen, KD tree es una estructura de datos que almacena un conjunto $S$ de puntos, y permite contestar queries de cuál es el punto más cercano de un punto dado a algún punto de $S$.

</details>

### L. Monotonically Increasing
<details>
<summary>Solución</summary>

Ver en: https://atcoder.jp/contests/abc263/editorial/4557

</details>

### M. A hard problem
<details>
<summary>Solución</summary>

La solución es:
$$\left \lceil{\frac{n}{2}}\right \rceil + 1$$.

</details>

## Día 6

### A. Alan's Birthday
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://drive.google.com/file/d/1enLHISnztrdT9OamdXngqGEZ063R4Mh3/view?fbclid=IwAR3tlTTWkS2AiUnXhS9WNG5RIMPSlci7SnnwH6HXX5KQn-lVChR5M__BPaE)

</details>

### B. Buying Piles of Stones
<details>
<summary>Solución</summary>

**Prerrequisitos:** Juego de NIM, Fast Walsh–Hadamard Transform.

[Ver en este enlace.](https://drive.google.com/file/d/1enLHISnztrdT9OamdXngqGEZ063R4Mh3/view?fbclid=IwAR3tlTTWkS2AiUnXhS9WNG5RIMPSlci7SnnwH6HXX5KQn-lVChR5M__BPaE)

</details>

### C. Coloring Matrix
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://atcoder.jp/contests/abc298/editorial/6223)

</details>

### D. Dynamic Network
<details>
<summary>Solución</summary>

**Prerequisitos:** LCA (Lowest Common Ancester).

[Ver en este enlace.](https://drive.google.com/file/d/1enLHISnztrdT9OamdXngqGEZ063R4Mh3/view?fbclid=IwAR3tlTTWkS2AiUnXhS9WNG5RIMPSlci7SnnwH6HXX5KQn-lVChR5M__BPaE)

</details>

### E. Environmental Contingency
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://drive.google.com/file/d/1enLHISnztrdT9OamdXngqGEZ063R4Mh3/view?fbclid=IwAR3tlTTWkS2AiUnXhS9WNG5RIMPSlci7SnnwH6HXX5KQn-lVChR5M__BPaE)

</details>

### F. Freddy and the Chocolate Factory
<details>
<summary>Solución</summary>

**Prerrequisitos:** Segment Tree.

[Ver en este enlace.](https://drive.google.com/file/d/1enLHISnztrdT9OamdXngqGEZ063R4Mh3/view?fbclid=IwAR3tlTTWkS2AiUnXhS9WNG5RIMPSlci7SnnwH6HXX5KQn-lVChR5M__BPaE)

</details>

### G. Late-Night Hunger
<details>
<summary>Solución</summary>

**Prerrequisitos:** Producto Cruz.

Seleccionar el triángulo con el área máxima que se puede obtener con un sólo corte en el polígono.

Hay que notar un triángulo que cumpla con estas condiciones estará compuesto por dos aristas adyacentes del polígono original y una arista adicional que será el corte. En otras palabras, será un triángulo formado por tres vértices adyacentes $\triangle P_{i} P_{i+1} P_{i+2}$ (donde $P_{n+1}=P_{1}$ y $P_{n+2}=P_{2}$). Como vimos en la presentación de geometría, el área de dicho triángulo se puede calcular con producto cruz.

</details>

### H. Hog Fencing
<details>
<summary>Solución</summary>

Hallar el rectángulo con perímetro igual o menor a $N$ que tenga la mayor área.

Los límites del perímetro van hasta $1000$, por lo tanto podemos iterar sobre todos los pares de altura $a$ y base $b$, tal que $1 \leq 2 * (a + b) \leq N$ para buscar el de mayor área $b*a$.

</details>

### I. A Simple Task
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/blog/entry/19212)

</details>

### J. Just an easy task
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://drive.google.com/file/d/1enLHISnztrdT9OamdXngqGEZ063R4Mh3/view?fbclid=IwAR3tlTTWkS2AiUnXhS9WNG5RIMPSlci7SnnwH6HXX5KQn-lVChR5M__BPaE)

</details>

### K. K-th Missing Digit
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://drive.google.com/file/d/1enLHISnztrdT9OamdXngqGEZ063R4Mh3/view?fbclid=IwAR3tlTTWkS2AiUnXhS9WNG5RIMPSlci7SnnwH6HXX5KQn-lVChR5M__BPaE)

</details>

### L. Lucky Tickets
<details>
<summary>Solución</summary>

**Prerrequisitos:** FTT y NTT

[Ver en este enlace.](https://codeforces.com/blog/entry/64156)

</details>

### M. Minimal Rotations
<details>
<summary>Solución</summary>

Prerrequisitos: Lyndon Factorization o Suffix Array

El problema se puede resover al menos de dos formas.

**Solución con Lyndon Factorization**
La rotación mínima es una aplicación de la factorización de Lyndon. [Ver en este enlace](https://cp-algorithms.com/string/lyndon_factorization.html#finding-the-smallest-cyclic-shift).

**Solución con Suffix Array**
Suffix Array es un arreglo que contiene todos los sufijos de una cadenas ordenados de forma lexicográfica. [La rotación mínima es la primera aplicación del suffix array explicado en este blog](https://cp-algorithms.com/string/suffix-array.html).

</details>

## Día 7

### A. The Same Multiset
<details>
<summary>Solución</summary>

**Prerequisites:** String hashing and hash for anagrams.

Let's solve the following problem first: given two strings $A$ and $B$, answer if $A$ is an anagram of $B$. This is equivalent to say that they have the same multiset of elements.

We can solve this by hashing. To find if two strings $A$ and $B$ are the same, usually we use hash function $H(A)=A[0] + A[1]x^1 + A[2]x^2 + \dots + A[n-1]x^{n-1}$, where $x$ is the base. In that hash, the order of the elements is important, because $A[i]$ is the coefficient of $x^i$, but to find out if A is anagram of $B$, the order of element doesn't matter. So, we need to find a hash function that considers only the elements in $A$, regardless of the order.

There are some hash functions that can be used with anagrams. Two of them are $H_1(A)=x^{A[0]}+x^{A[1]}+x^{A[2]}+ \dots +x^{A[i-1]}$ and $H_2(A)=(x-A[0])(x-A[1])(x-A[2])\dots(x-A[n-1])$.

You can use $H_1$ and $H_2$ to solve the original problem. Here, we explain the full solution with $H_1$. To find the hash of a contiguous subsequence, we can use prefix sums. Let $sum(i)$ be equal to $H_1(A[1...i])$, that is, the hash of the first $i$ elements in $A$. Note that $sum(i)=sum(i-1)+x^{A[i]}$, so, you can compute values of $sum(i)$ in $O(n)$. Now, to find the hash value of the contiguous subsequence $A[i...j]$ (i.e. $H_1(A[i...j])$), you can simply take $sum(j)-sum(i-1)$.

To answer queries, just precompute hashes of $A$ and $B$ using some prime modulo, and compare $H_1(A[x_q...(x_q+l_q-1)])$ and $H_1(B[y_q...(y_q+l_q-1)])$.

Complexity: $O(n+q)$.

You can also solve this problem with $H_2$ using a similar idea.

</details>

### B. Basic Encryption
<details>
<summary>Solución</summary>

To encrypt words, you need to sum $S$ to values of all letters, thus to decrypt words, you need to subtract $S$ to values of letters.

You can read a line with spaces with `getline(cin,s)` in `C++`. Now, for the lowercase letter, you can rest the ascii value of 'a' to get the value of the letter, take the sum of that value and $S$ modulo $26$, and finally sum the ascii value of 'a'. In other words, the decrypted character $s[i]$ is $((s[i] - `a` - S) \% 26 + 26) \% 26 + `a`$. Uppercase letters can be decrypted by a similar way.

</details>

### C. Who Says a Pun?
<details>
<summary>Solución</summary>

**Prerrequisitos:** Z-function

[Ver en este enlace.](https://atcoder.jp/contests/abc141/tasks/abc141_e/editorial)

</details>

### D. Exam Period
<details>
<summary>Solución</summary>

**Prerequisitos:** Algebra de Boole y 2-SAT.

La solución consiste en obtener un sistema de expresiones booleanas equivalente y resolverlo con [2-SAT](https://cp-algorithms.com/graph/2SAT.html).

Se puede observar que se pueden obtener las siguientes expresiones booleanas dependiendo del valor de $▢_i$ y $c_i$:

$x + y = 0$: $¬x \& ¬y$
$x + y = 1$: $x \neq y$
$x + y = 2$: $x \& y$
$x + y \neq 0$: $x | y$
$x + y \neq 1$: $x = y$
$x + y \neq 2$: $¬x | ¬y$
$x + y < 1$: $¬x \& ¬y$
$x + y < 2$: $¬x | ¬y$
$x + y > 0$: $x | y$
$x + y > 1$: $x \& y$
$x + y \leq 0$: $¬x \& ¬y$
$x + y \leq 1$: $x | ¬y$
$x + y \geq 1$: $x | y$
$x + y \geq 2$: $x \& y$

Observar que si tenemos las expresiones $x + y < 0$ o $x + y > 2$ entonces la respuesta es `No` También observemos que las expresiones $x + y \geq 0$ y $x + y \leq 2$ siempre son ciertas, así que podemos ignorarlas.

Una vez que obtenemos las expresiones booleanas equivalentes, podemos usar 2-SAT para hallar si existen valores para $a_0, ..., a_{n-1}$ que satisfagan todas las expresiones.

Complejidad: $O(n+m)$.

* Nota: En algunas implementaciones de 2-SAT, sólo se soporta insertar expresiones que sean disyunciones o con implicaciones. En esos casos, se deben convertir las conjunciones, igualdades y desigualdades a expresiones equivalentes a las disyunciones o implicaciones según sea el caso.

</details>

### E. Tufurama

<details>
<summary>Solución</summary>

**Prerrequisitos:** Fenwick Tree (conocido también como BIT), Segment Tree o Wavelet Tree.

First we can notice that for every season we only care for the first $n$ episodes, so we can change the intial values to $a_{i} = min(a_{i},n)$. Then, for each season lets find with how many other seasons can it match. Since we do not want to double count the matches, we will start backwards: from the $n$-th seasont to the first.

For the $i$-th season with $a_{i}$ episodes, we want to find another season with index $j$ and value $a_{j}$ so that the following conditions are met.

- $j \leq a_{i}$
- $i \leq a_{j}$
- $i < j$

If we start checking the elements from the $n$-th season to the first, we will have to find how many seasons to our right have a value $a_{j}$ greater than or equal to the index $i$ we are currently on. And from these, we will only have to take the ones with an index $j$ that is less than or equal to our value $a_{i}$. To solve this we can figure out that if we are standing at the $i$-th position, we will have to look for an $a_{j} \geq i$ only in the positions $j$ from $[i+1,a_{i}]$. Clearly, if $a_{i} < i+1$ then the answer for this index is zero.

After setting our valid range, the operation of finding a value greater than or equal than a $X$ can easily be done with a Fenwick Tree or Wavelet Tree. Since for every position in the array we will do a query, the final complexity will be $O(Nlg(MAX))$ where $MAX$ is the value of the maximum element in the initial array.

</details>

### F. President and Roads
<details>
<summary>Solución</summary>

**Prerrequisitos:** Dijkstra.

[Ver en este enlace.](https://codeforces.com/blog/entry/19604)

</details>

### G. A * B * C
<details>
<summary>Solución</summary>

**Prerrequisitos:** Suma de la serie armónica.

[Ver en este enlace.](https://atcoder.jp/contests/arc113/editorial/783)

</details>

### H. New Max
<details>
<summary>Solución</summary>

If there are values greater that $M$, then you need to make them equal to $M$. So, if the number of elements greater than $M$ is greater than $K$, then answer is 'NO'. But there is a special case. If there is no element equal to $M$ and $K=0$, then answer is 'NO', because the maximum element is different that $M$. In another case, you can have a maximum of $M$.

</details>

### I. Dungeon Explore
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://atcoder.jp/contests/abc305/editorial/6554)

</details>

### J. K-th divisor
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/blog/entry/50010)

</details>

### K. Inflation
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/blog/entry/87356)

</details>

### L. The Volcano Eruption
<details>
<summary>Solución</summary>

**Prerrequisitos:** Intersección de Círculos.

Let's join the pairs of intersecting holes in a single connected component of lava. Saeed have to use a suit to swim a component, if the leftmost coordinate in this component is less or equal than $0$ and the rightmost coordinate is greater or equal than $L$, since Saeed can't get to the other side of the component without swimming. Two holes $i$ and $j$ intersect if $(x_i-x_j)^2+(y_i-y_j)^2 \leq (r_i+r_j)^2$.

Build a graph, where a node is a hole, and a edge is the union of two intersecting holes. Transverse each component in this graph. In each node of the component, calculate the leftmost coordinate of the hole ($x_i-r_i$) and the rightmost coordinate of the hole ($x_i+r_i$), in order to calculate the leftmost and rightmost coordinates in the component. If Saeed need to use a suit, add $1$ to the answer.

</details>

### M. CGCDSSQ
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/blog/entry/14168)

</details>

## Día 8

### A. Counting Stars
<details>
<summary>Solución</summary>

**Prerrequisitos:** Trie

La solución consiste en fijar cada estrella como la estrella central ($C$ de ahora en adelante) y contar las constelaciones centradas en $C$. La respuesta será la suma de la cantidad de las constelaciones centradas en $C$, para toda $C$ entre $1$ y $n$.

Cuando fijamos una estrella como $C$, dividamos las demás estrellas en *rayos*. Dos estrellas $U$ y $V$ pertenecerán al mismo rayo desde $C$ si la pendiente de los segmentos $CU$ y $CV$ es la misma.

Si las estrellas $U_1$, $U_2$, $\dots$, $U_l$ pertenecen forman un mismo rayo tal que $d_{U_1} < d_{U_2} < \dots < d_{U_l}$ (recordar que $d_u$ es la distancia de la distancia $u$ a $C$, es decir, ordenamos las estrellas en un rayo por su distancia a $C$), entonces crearemos un arreglo $[ d_{U_1}, d_{U_2}, \dots, d_{U_l}]$. Creamos un arreglo para cada rayo.

Las formas de seleccionar un subconjunto de $m$ arreglos y un prefijo de tamaño $k$ en cada uno de esos arreglos tal que los todos los prefijos son iguales, es igual a contar la cantidad de constelaciones válidas centradas en $C$. Notar que todas las condiciones que deben cumplir las constelaciones descritas en el problema se cumplen al seleccionar las estrellas de esta forma.

Ahora el problema se traduce a un problema de cadenas: de un conjunto de cadenas, contar las formas de seleccionar algún subconjunto de estas cadenas y un prefijo en ellas, tal que el prefijo seleccionado es igual en todas las cadenas seleccionadas.

Este problema se puede resolver con un Trie. En cada nodo almacenamos la cantidad $cn$ de cadenas que pasan por ese nodo. Todas las palabras contadas en $cn$ tienen un prefijo en común que termina en ese nodo. La respuesta es la suma $2^{cn}-1$ para cada nodo del Trie.

Complejidad: $O(n^2log(n))$

</details>

### B. Cypher Decypher
<details>
<summary>Solución</summary>

**Prerrequisitos:** Criba de Erastótenes

[Ver en este enlace.](https://drive.google.com/file/d/1uqfCSApjntYTG28aLgfWbPKMbhBMNkGM/view)

</details>

### C. Bacteria Experiment
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://lscct.com/challenge/2017solution.pdf)

</details>

### D. Cheering
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://lscct.com/challenge/2017solution.pdf)

</details>

### E. k-Factorization

<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/blog/entry/51588)

</details>

### F. Hit!
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://lscct.com/challenge/2017solution.pdf)

</details>

### G. Inverted Signs
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://lscct.com/challenge/2017solution.pdf)

</details>

### H. Knights
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://lscct.com/challenge/2017solution.pdf)

</details>

### I. The Child and Sequence
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/blog/entry/12513)

</details>

### J. Co-prime Array
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/blog/entry/44259)

</details>

### K. Pocket Book
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/blog/entry/3926)

</details>

### L. Coffee Cup Combo
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/gym/104030/attachments/download/17787/ncpc22slides.pdf)

</details>

### M. Disc District
<details>
<summary>Solución</summary>

[Ver en este enlace.](https://codeforces.com/gym/104030/attachments/download/17787/ncpc22slides.pdf)

</details>