Codeforces Round #358 (Div. 2) Editorial

Правка en5, от halin.george, 2016-06-18 13:31:50

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) > au, 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 au, then remove au with the whole subtree.

682D — Алёна и строки

Воспользуемся методом динамического программирования. Пусть d[i][j][cnt][end] — ответ на задачу для префикса строки s длины i и префикса строки t длины j, при том, что подпоследовательность, являющаяся ответом состоит из cnt подстрок. end = 1, если оба последних элемента данных префиксов строк входят в максимальную подпоследовательность и end = 0 в противном случае.

Находясь в состоянии d[i][j][cnt][end], можно добавить следующую букву в строках s или t, при том она не будет входить в ответную подпоследовательность. Тогда 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]). То есть новое значение end равно 0, поскольку новая буква не входит в ответную подпоследовательность.

Если 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 принимают всевозможные значения.

682E — Alyona and Triangles

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en11 Английский halin.george 2016-06-18 13:47:05 0 (published)
en10 Английский halin.george 2016-06-18 13:46:51 821
en9 Английский halin.george 2016-06-18 13:46:04 75
en8 Английский halin.george 2016-06-18 13:43:14 462
en7 Английский halin.george 2016-06-18 13:40:00 451
en6 Английский halin.george 2016-06-18 13:37:37 1485
en5 Английский halin.george 2016-06-18 13:31:50 1013
en4 Английский halin.george 2016-06-18 13:22:26 687
en3 Английский halin.george 2016-06-18 13:15:54 189
en2 Английский halin.george 2016-06-18 13:15:31 3663 Tiny change: 'ou can predposchitat how many ' - (saved to drafts)
ru5 Русский halin.george 2016-06-18 12:42:20 5 Мелкая правка: 'i][j][cnt]). То ест' -> 'i][j][cnt][end]). То ест'
en1 Английский halin.george 2016-06-17 23:57:38 77 Initial revision for English translation
ru4 Русский halin.george 2016-06-17 23:42:10 2256 Мелкая правка: '(v, u) (опубликовано)
ru3 Русский halin.george 2016-06-17 23:35:43 865
ru2 Русский halin.george 2016-06-17 23:31:02 8 Мелкая правка: ' равным $(4 - x mod 5)$. Наприме' -
ru1 Русский halin.george 2016-06-17 23:28:39 371 Первая редакция (сохранено в черновиках)