[682A — Alyona and Numbers](http://codeforces.net/contest/682/problem/A) ↵
↵
Let's iterate over the first number of the pair, let it be $x$. Then we need to count numbers from $ 1 $ to $ m $ with the remainder of dividing $ 5 $ equal to $ (5 - x mod 5) mod $ 5. For example, you can precalc how many numbers from $ 1 $ to $ m $ with every remainder between $ 0 $ and $ 4 $.↵
↵
[682B — Alyona and Mex](http://codeforces.net/contest/682/problem/B)↵
↵
Let's sort the array. Let $ cur = $ 1. Then walk through the array. Let's look at current number. If it is greater or equal to $cur$, then let's increase $cur$ by $1$. Answer is $ cur $.↵
↵
[682C — Alyona and the Tree](http://codeforces.net/contest/682/problem/C)↵
↵
Let's do dfs. Suppose that we now stand at the vertex $u$. Let $v$ be some ancestor of vertex $u$. Then $ dist (v, u) = dist (1, u) - dist (1, v) $. If $ dist (v, u)> a_u $, then the vertex $ u $ makes $v$ sad. So you must remove the whole subtree of vertex $ u $. Accordingly, it is possible to maintain a minimum among $ dist (1, v) $ in dfs, where $ v $ is ancestor of $ u $ (vertex, in which we now stand). And if the difference between the $ dist (1, u) $ and that minimum is greater than $ a_u $, then remove $ a_u $ with the whole subtree.↵
↵
[682D — Алёна и строки](http://codeforces.net/contest/682/problem/D)↵
↵
Если s[i] = t[j], то, если end = 1, то можно обновить d[i + 1][j + 1][k][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k][1]). Поскольку end = 1, при добавлении элемента к ответной подпоследовательности, количество подстрок, из которых она состоит, останется таким же. Если end = 0, то можно обновить d[i + 1][j + 1][k + 1][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k + 1][1]). В этом случае новые символы, которые мы пытаемся добавить к ответной подпоследовательности, будут образовывать уже новую подстроку, поэтому в этом случае переход из состояния с k в состояние с k + 1. ↵
↵
Ответом будет являться наибольшее число среди состояний вида d[n][m][k][end], где значения k и end принимают всевозможные значения.↵
↵
Let's use the method of dynamic programming. Let d[i][j][cnt][end] be answer to the problem for the prefix of string $s$ of length $i$ and for the prefix of string $t$ of length $j$, we have chosen $cnt$ substrings. $end = 1$, if both last characters of the prefixes are included in the maximum subsequence and $end = 0$ otherwise.↵
↵
When the state is d[i][j][cnt][end], you can add the following letters in the string s or t, though it will not be included in the response subsequence. Then d[i + 1][j][cnt][0] = max(d[i + 1][j][cnt][0], d[i][j][cnt][end]), d[i][j + 1][cnt][0] = max(d[i][j + 1][cnt][0], d[i][j][cnt][end]). So the new value of end is 0, because the new letter is not included in the response subsequence.↵
↵
If s[i] = t[j], then if $end = 1$, we can update the d[i + 1][j + 1][k][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k][1]). When we add an element to the response subsequence, the number of substring, which it is composed, will remain the same, because $end = 1$. If $end = 0$, we can updatethe d d[i + 1] [j + 1] [k + 1] [1] = max (d [i] [j] [k] [end] + 1, d [i + 1] [j + 1] [k + 1] [1]). In this case, the new codeharacters, which we try to add the subsequence response will have too the response subsequence, will form a new substring, so in this case we do the transition from athe state k$k$ to the state $k + 1 a$.↵
↵
The answer will be the largest number among the states of the d [n] [m] [k] [end], where the values of k and end take all possible values.↵
↵
[682E — Alyona and Triangles](http://codeforces.net/contest/682/problem/E)↵
↵
Let's find the triangle with maximum area among all triangles whose vertices belong to the set of points. (For $ N ^ 2 $ with the convex hull and the two pointers). We can prove that if we take the triangle, whose vertices are the midpoints of the sides of the triangle with maximum area, the area of such a triangle is not greater than $ 4S $, and it contains all the points of the set. Let us assume that there is a point lying outside the triangle-response. Then we can get longer height to some side of triangle, so we have chosen a triangle with not maximum area(contradiction).
↵
Let's iterate over the first number of the pair, let it be $x$. Then we need to count numbers from $ 1 $ to $ m $ with the remainder of dividing $ 5 $ equal to $ (5 - x mod 5) mod $ 5. For example, you can precalc how many numbers from $ 1 $ to $ m $ with every remainder between $ 0 $ and $ 4 $.↵
↵
[682B — Alyona and Mex](http://codeforces.net/contest/682/problem/B)↵
↵
Let's sort the array. Let $ cur = $ 1. Then walk through the array. Let's look at current number. If it is greater or equal to $cur$, then let's increase $cur$ by $1$. Answer is $ cur $.↵
↵
[682C — Alyona and the Tree](http://codeforces.net/contest/682/problem/C)↵
↵
Let's do dfs. Suppose that we now stand at the vertex $u$. Let $v$ be some ancestor of vertex $u$. Then $ dist (v, u) = dist (1, u) - dist (1, v) $. If $ dist (v, u)> a_u $, then the vertex $ u $ makes $v$ sad. So you must remove the whole subtree of vertex $ u $. Accordingly, it is possible to maintain a minimum among $ dist (1, v) $ in dfs, where $ v $ is ancestor of $ u $ (vertex, in which we now stand). And if the difference between the $ dist (1, u) $ and that minimum is greater than $ a_u $, then remove $ a_u $ with the whole subtree.↵
↵
[682D — Алёна и строки](http://codeforces.net/contest/682/problem/D)↵
↵
Если s[i] = t[j], то, если end = 1, то можно обновить d[i + 1][j + 1][k][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k][1]). Поскольку end = 1, при добавлении элемента к ответной подпоследовательности, количество подстрок, из которых она состоит, останется таким же. Если end = 0, то можно обновить d[i + 1][j + 1][k + 1][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k + 1][1]). В этом случае новые символы, которые мы пытаемся добавить к ответной подпоследовательности, будут образовывать уже новую подстроку, поэтому в этом случае переход из состояния с k в состояние с k + 1. ↵
↵
Ответом будет являться наибольшее число среди состояний вида d[n][m][k][end], где значения k и end принимают всевозможные значения.↵
↵
Let's use the method of dynamic programming. Let d[i][j][cnt][end] be answer to the problem for the prefix of string $s$ of length $i$ and for the prefix of string $t$ of length $j$, we have chosen $cnt$ substrings. $end = 1$, if both last characters of the prefixes are included in the maximum subsequence and $end = 0$ otherwise.↵
↵
When the state is d[i][j][cnt][end], you can add the following letters in the string s or t, though it will not be included in the response subsequence. Then d[i + 1][j][cnt][0] = max(d[i + 1][j][cnt][0], d[i][j][cnt][end]), d[i][j + 1][cnt][0] = max(d[i][j + 1][cnt][0], d[i][j][cnt][end]). So the new value of end is 0, because the new letter is not included in the response subsequence.↵
↵
If s[i] = t[j], then if $end = 1$, we can update the d[i + 1][j + 1][k][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k][1]). When we add an element to the response subsequence, the number of substring, which it is composed, will remain the same, because $end = 1$. If $end = 0$, we can update
↵
The answer will be the largest number among the states of the d [n] [m] [k] [end], where the values of k and end take all possible values.↵
↵
[682E — Alyona and Triangles](http://codeforces.net/contest/682/problem/E)↵
↵
Let's find the triangle with maximum area among all triangles whose vertices belong to the set of points. (For $ N ^ 2 $ with the convex hull and the two pointers). We can prove that if we take the triangle, whose vertices are the midpoints of the sides of the triangle with maximum area, the area of such a triangle is not greater than $ 4S $, and it contains all the points of the set. Let us assume that there is a point lying outside the triangle-response. Then we can get longer height to some side of triangle, so we have chosen a triangle with not maximum area(contradiction).
