Всем привет!

23 ноября в 19:35 MSK состоится очередной раунд Codeforces #381 для участников из обоих дивизионов.

Задачи подготовлены Александром Alexandr_TS Цаплиным, Максимом HellKitsune Финютиным и мной. Надеюсь, что задачи вам понравятся.

Хотелось бы сказать большое спасибо Глебу GlebsHP Евстропову, Николаю KAN Калинину и Евгению MrDindows Задорожнему за помощь в подготовке задач, а также Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon.

В каждом из дивизионов будет по 5 задач. Разбалловку объявим позднее.

UPD

Разбалловка для обоих дивизионов: 500-1000-1500-2000-2500

UPD

Поздравляем победителей!

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

Отдельно поздравляем Petr как единственного участника, который решил задачу D в div 1.

UPD Разбор

682A — Алёна и числа

Переберем первое число пары, пусть оно равно x. Тогда нам нужно посчитать количество чисел от 1 до m с остатком от деления на 5 равным (5 - xmod5)mod5. Например, можно предпосчитать, сколько чисел от 1 до m с каждым остатком от 0 до 4.

682B — Алёна и mex

Отсортируем массив. Заведем переменную cur = 1. Пройдемся по массиву. Посмотрим на очередное число. Если оно больше или равно cur, то увеличим cur на 1. Ответ — это cur.

682C — Алёна и дерево

Будем делать dfs. Пусть мы сейчас стоим в вершине u. Пусть v — это какой-то предок вершины u. Тогда dist(v, u) = dist(1, u) - dist(1, v). Если dist(v, u) > a_u, то вершина u заставляет вершину v грустить. Так что необходимо удалить все поддерево вершины u. Соответственно, в dfs можно поддерживать минимум среди dist(1, v), где v — это предок u(вершина, в которой мы сейчас стоим). И если разность dist(1, u) и этого минимума больше a_u, то удаляем a_u вместе со всем поддеревом.

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

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

Всем привет!

17 июня в 19:35 MSK состоится очередной раунд Codeforces #358 для участников из второго дивизиона.

Автором всех задач являюсь я, и это мой дебютный раунд на Codeforces. Надеюсь, что задачи вам понравятся.

Хотелось бы сказать большое спасибо Глебу GlebsHP Евстропову и Данилу danilka.pro Сагунову за помощь в подготовке задач, Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.

UPD

Разбалловка: 500-1000-1500-2000-3000

UPD

Разбор

UPD

Поздравляем победителей!

Div.2:

1. zijue

2. dacaiji

3. dan19

4. yusufsholeh

5. BIT-silence

Div.1:

1. MrDindows

2. Um_nik

3. anta

4. uwi

5. Shik

Стало интересно, много ли среди пользователей codeforces людей, которые имеют разряд(или в прошлом имели) по одному из контактных видов спорта(бокс, кикбоксинг, греко-римская борьба, вольная борьба, самбо, дзюдо, смешанные единоборства и другие)? В основном интересуют люди с рейтингом 1900+. Отпишите, пожалуйста, в комментарии вид спорта и разряд.

Code Jam Round 1B начнется через несколько часов(19:00 MSK).

GL & HF.

Вот условие задачи. Начальные значения:

F[0][0]=100;
F[0][1]=F[0][0]/Price[0][0]; // макс. количество долларов в нулевой день
F[0][2]=F[0][0]/Price[0][1]; // макс. количество евро в нулевой день
//Переходы
for(int i=1; i<n; i++)
{
    F[i][0]=max(max(F[i-1][1]*Price[i][0], F[i-1][2]*Price[i][1]), F[i-1][0]);
    F[i][1]=max(F[i-1][0]/Price[i][0], F[i-1][1]);
    F[i][2]=max(F[i-1][0]/Price[i][1], F[i-1][2]);
}
// Ответ в F[n-1][0]

Суть такова, что в F[i][0] лежит максимальное кол-во рублей, которое можно собрать в первые i дней. Price[i][0] — курс доллара в i-тый день. Price[i][1] — курс евро в i-тый день.

Над задачей ломаю голову вторые сутки. Симпл тест проходит, прога падает с WA2. Если динамика верна, то буду искать в коде ошибку, иначе прошу подсказки.

Спасибо!

P.S. А те, кто ставят минусы, они вообще пытались помочь? Чем обосновываются эти минусы?

P.P.S. Это исправленная версия, после замечания dima_gozha, которая также падает с WA2.

P.P.P.S. Задача решена, отдельное спасибо KADR!