Всем добрый день.

Новый год — время чудес и подарков! Совершенно случайно 100-й раунд Codeforces совпал с этим замечательным моментом.

Итак, 4-го января в 19:00 (Московское время) состоится юбилейный раунд Codeforces Round 100. Да, мы прощаемся со словом Beta в названии раундов :)

Это будет совмещенный раунд, то есть участники Div1, Div2 и новички будут соревноваться на одном комплекте задач. Чтобы всем было интересно, и каждый нашел задачи по силам, мы планируем расширить раунд до 6-ти задач.

Самое главное: лучшие сто участников по результатам 100-го раунда получат по юбилейной эксклюзивной футболке Codeforces!

Счастливого нового года!
Команда Codeforces

Привет.

Сегодняшний раунд подготовил я. Меня зовут Михаил Тихомиров, я студент 4 курса мехмата МГУ, помимо этого работаю в Яндексе разработчиком-исследователем.

Хочется сказать спасибо Артему Рахову (RAD) за значительную помощь и грамотную координацию, Марии Беловой (Delinur) за традиционно качественный перевод условий, а также MikeMirzayanov за то, что все мы здесь сегодня собрались. =)

Раунд будет для обоих дивизионов. В каждом дивизионе, как и всегда, будет по пять задач, некоторые из которых будут общими, но не все.

Разбалловка:

Div1: 500-1000-2000-2000-2500.

Div2: 500-1000-1500-2000-3000.

Сегодняшний раунд - последний в 2011 году. Я хочу поблагодарить команду Codeforces, всех, кто придумывал, готовил или помогал готовить задачи в этом или прошлых годах, а также тех, кто способствует развитию проекта. Codeforces давно перестал быть просто платформой для соревнований по программированию, сейчас это - место, где каждому есть чему научиться у других, каждый может почерпнуть частичку опыта у более опытных товарищей при непосредственном общении, повысить свой уровень на контестах и тренировках, или просто получить удовольствие от красивых и оригинальных задач.

Пожалаем проекту удачного развития в следующем году и долгих лет существования.

Всем удачи. Желаю получить максимум удовольствия от сегодняшнего раунда и выступить на уровне.

И да, всех с наступающим! =)

UPD:

Раунд окончен. Всем спасибо за участие! Надеюсь, вам понравилось.

Победители.

Div1:

1. ivan.popelyshev

2. al13n

3. WJMZBMR

4. yeputons

5. romanandreev

6. dolphinigle

7. wata

8. Shef

9. shangjingbo

10. azizkhan

Div2:

1. s-quark

2. wayne-ho

3. emrevarol

4. agh

5. lzqxh

В конце раунда по техническим причинам несколько минут был недоступен сервер. К сожалению, мы не имеем возможности принять решения, которые вы не смогли из-за этого сдать. Из двух неприятных вариантов: делать раунд нерейтинговым и оставить все, как есть, мы решили выбрать второй, поскольку это затрагивает меньше участников. Мы приносим извинения тем участникам, на которых влияет это решение.

UPD2: разбор из ап.

A. Открытки и фотографии

Будем идти по строке слева направо. Если мы прошли всю строку, либо в руках у нас уже 5 предметов, либо очередной предмет отличается от тех, что мы держим в руках, то относим все предметы в кладовку. Ответом на задачу будет количество посещений кладовки.

Сложность решения O(n).

B. Перестановка

Посчитаем количество чисел от 1 до n, которые встречаются в последовательности хотя бы один раз. Тогда ответ есть n минус это количество.

Сложность решения в зависимости от реализации O(n) или O(n logn).

C. История

Отсортируем пары, заданные в условии по году начала события. Будем идти по массиву этих пар и поддерживать значение rg - самый поздний год окончания какого-либо из уже обработанных событий. Тогда если для текущего года окончания события - year, верно что year < rg, то нужно прибавить к ответу единицу, поскольку данное событие покрыто каким-то из ранее обработанных (поскольку все обработанные события имеют левую границу меньше нашей и какое-то из них имеет правую границу rg большую year). После этого пересчитываем rg следующим образом: rg = max(rg, year).

Сложность решения: O(n logn) - на сортировку и O(n) - на решение.

D. Палиндромы

Сначала сделаем небольшой предподсчёт: cnt[lf][rg] - наименьшее количество символов, которое мы должны изменить, чтобы подстрока [lf, rg] стала палиндромом. Это легко сделать за O(n^3) времени и O(n^2) памяти. Теперь будем считать динамику z[i][j] - наименьшее число изменений, которое мы должны сделать, чтобы разбить префикс длины i на ровно j палиндромов. Сначала весь массив заполним бесконечностями, а z[0][0] присвоим 0. Теперь будем делать переходы вперёд: переберём длину len очередного (j-го) палиндрома и сделаем обновление состояния z[i + len][j + 1] значением z[i][j] + cnt[i][i + len - 1]. Ответ есть минимум z[n][i], где n - длина строки из входного файла, а i отрезка [1, k]. Чтобы вывести ответ необходимо в дополнительном массиве сохранить предка для каждого состояния.

Сложность решения: O(n^3) по времени и O(n^2) по памяти.

E. Последний шанс

В этой задаче можно было подумать, что при фиксированном начале строки функция "хорошести" от конца строки монотонная, но это не так (хотя бы на примере строки baaab). Заменим все гласные из строки на число -1, а все согласные на число 2. Теперь легко понять, что подстрока [i, j] будет хорошей, если сумма в подотрезке [i, j] неотрицательна. Обозначим эту сумму sum[i][j]. Очевидно sum[i][j] = p[j + 1] - p[i]. Где p[i] - сумма первых i элементов. Теперь решение становится достаточно понятным. Одним из решений было следующее: отсортируем все частичные суммы вместе с индексом частичной суммы и заведём структуру данных над массивом индесов частичных сумм, позволяющую извлекать максимум на суффиксе, а также изменять значение в точке (в качестве такой структуры подойдёт дерево отрезков). Теперь будем пробегаться по массиву частичных сумм (отсортированных) и для текущего индекса частичной суммы (начала хорошей строки) найдём самую правую частичную сумму больше либо равную нашей. Пусть величина текущей частичной суммы равна s, а её номер - i. Найдём в массиве частичных сумм первую частичную сумму с величиной больше либо равной s. Найдём максимум на суффиксе найденной частичной суммы - это и будет позиция самой правой хорошей границы для i (если эта граница больше i). Для удаления нашей суммы из массива обновим значение в ней величиной отрицательной бесконечности. Таким образом легко найти не только максимальную длину хорошей подстроки, но и количество таких подстрок.

Сложность решения: O(n logn) по времени и O(n) по памяти.

Всем привет!!!

Осталось меньше 11 часов до начала Codeforces Beta Round #98 (Div. 2). Этот раунд для вас подготовил я, идеи задач мне подкинул MikeMirzayanov. По традиции RAD проследил за тем, чтобы я не посадил багов и написал нормальные условия, а Delinur перевела условия на английский язык. За что им всем спасибо!

Если вы решите поучаствовать в раунде вам придётся помочь мальчику Поликарпу и его однокласснику Иннокентию во всех трудностях с которыми они сталкиваются. Чем лучше вы им поможете, тем более высокое место займёте.

Надеюсь задачи окажутся интересными не только участникам из Div. 2, но и участникам с рейтингом больше 1699.

Продолжу небольшое повествование о себе (начало в предыдущей записи в блоге). Кроме программирования я очень люблю спорт. В течении нескольких лет до того как я начал писать код, я достаточно серьёзно занимался академической греблей. А до этого я занимался практически всеми видами спорта :-): каратэ, футбол, хоккей, борьба самбо и ещё много всего интересного. Сейчас очень люблю (особенно на сборах) играть в волейбол и настольный теннис. Я решил подготовить этот раунд несмотря на то, что в течении последних двух недель Codeforces заметно менялся внутри и я принимал в этом участие.

Следуя модным тенденциям скоро поменяю аватарку.

Всем удачи на раунде и высокого рейтинга!

UPD:

Соревнование закончено, результаты окончательные, рейтинги пересчитаны.

Top 10 (Div. 2)

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

Представляю разбор задач Codeforces Beta Round #97. Если есть какие-то вопросы или пожелания --- пишите в комментариях.

136A - Подарки (A Div 2)

A. HQ9+

В задаче давалось описание HQ9+ и спрашивалось, выведет ли заданная программа что-то на печать. Ввиду исключительной простоты языка для этого было достаточно проверить, содержит ли программа хотя бы один из символов H, Q и 9 (с учетом регистра).

В субботу 3 декабря состоится Codeforces Beta Round #96, мой первый классический раунд на Codeforces. Чтобы несколько сгладить переход от неизвестного языка к известным, я сделала раунд тематическим, и тема эта, разумеется, языки программирования :-)

Спасибо MikeMirzayanov, maksay и RAD за помощь в подготовке задач.

Удачи на раунде!

P.S. Баллы за задачи: первый дивизион — 500-1500-1500-2000-2500, второй дивизион — 500-1000-1500-2500-2500.

P.P.S. Разбор задач здесь.

Всем привет!