Codeforces Round #358 (Div. 2) Editorial

Правка en4, от halin.george, 2016-06-18 13:22:26

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 — Алёна и треугольники

Найдем треугольник максимальной площади из всех треугольников, вершины которого — точки из данного набора. (за N2 с выпуклой оболочкой и двумя указателями). Утверждается, что если взять треугольник, на серединах сторон которого лежат вершины треугольника с максимальной площадью, площадь такого треугольника не превосходит 4S, и он содержит в себе все точки из набора. Допустим, что найдется точка, лежащая вне треугольника-ответа. Тогда можно из этой точки более длинную высоту на какую-то сторону опустить, следовательно мы нашли треугольник не максимальной площади(противоречие).

История

 
 
 
 
Правки
 
 
  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 Первая редакция (сохранено в черновиках)