Hi everyone!

Codeforces Round #381 will take place tomorrow on the 23rd of November at 19:35 MSK.

The problems were prepared by Alexander Alexandr_TS Tsaplin, Maxim HellKitsune Finutin and me. I hope you will enjoy it.

I'd like to thank Gleb GlebsHP Evstropov, Nikolay KAN Kalinin and Yevhen MrDindows Zadorozhnii for helping me in preparing problems, Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

There will be five problems and two hours for solving them. The scoring distribution will be announced later.

UPD

Scoring for both divisions: 500-1000-1500-2000-2500

UPD

Congratulations for winners.

Div 1:

1. jqdai0815

2. FatalEagle

3. izban

4. LHiC

5. Radewoosh

6. Egor

Div 2:

1. liumh8

2. retired_coder

3. fuboat

4. v4lerich

A special congratulations to Petr for being the only contestant to solve the problem D in div. 1.

UPD

The editoral in english will be published tomorrow, but you can read it now in russian

UPD

The editoral was added for the first five problems.

UPD

The editoral was added for the Div.1 D and Div1. E.

682A — Alyona and Numbers

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 - xmod5)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

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

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 — Alyona and Strings

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 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 characters, which we try to add to the response subsequence, will form a new substring, so in this case we do the transition from the state k to the state k + 1.

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

Let's find the triangle with maximum area among ​​all triangles whose vertices belong to the set of points. (For N² 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).

Hi everyone!

Codeforces Round #358 (Div. 2) will take place today on the 17th of June at 19:35 MSK.

I am the author of all the problems, and this is my first round on Codeforces. I hope you will enjoy it.

I'd like to thank Gleb GlebsHP Evstropov and Dan danilka.pro Sagunov for helping me in preparing problems, Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

There will be five problems and two hours for solving them. The scoring distribution will be announced later.

UPD

Scoring: 500-1000-1500-2000-3000

UPD

Editoral

UPD

Congratulations to winners!

Div.2:

1. Subway_Sandwich

2. mcdonalds

3. KentuckyFriedChicken

4. zijue

5. dacaiji

Div.1:

1. MrDindows

2. Um_nik

3. anta

4. uwi

5. Shik

Code Jam Round 1B starts in a few hours(19:00 MSK).

GL & HF.