Автор Edvard, 12 лет назад, По-русски

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) по памяти.

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 98 (Div. 2)
  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

Автор Edvard, 12 лет назад, По-русски

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

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

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

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

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

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

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

UPD:

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

Top 10 (Div. 2)

3. stx2

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +141
  • Проголосовать: не нравится

Автор KADR, 12 лет назад, По-русски

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

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


В этой задаче нужно было просто считать перестановку и вывести обратную к ней. Для этого просто при считывании i-го по счету числа, которое равно a поместим i в ячейку массива с номером a. После этого выведем полученный массив.

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

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 97 (Div. 1)
Разбор задач Codeforces Beta Round 97 (Div. 2)
  • Проголосовать: нравится
  • +87
  • Проголосовать: не нравится

Автор KADR, 12 лет назад, По-русски
Всем привет!

В пятницу, 9 декабря в 19:00 MSK состоится Codeforces Beta Round #97, автором которого являюсь я. Это мой второй полноценный раунд на Codeforces и надеюсь, что не последний :)

Спасибо maksay, Shtrix, it4.kp, RAD и Delinur за помощь в подготовке раунда, тестировании задач и переводе условий.

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

UPD: По техническим причинам раунд переносится на 5 минут вперед.

UPD 2: По причине большого числа участников и большого количества тестов, результаты появятся не скоро.

UPD 3: Тестирование завершено, результаты известны. Всем спасибо за участие! Приношу свои извинения за настолько длительное тестирование.

Победители:

Div 1
4. Shef
7. ania
9. NALP

Div 2

UPD 4: Опубликован разбор.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +237
  • Проголосовать: не нравится

Автор Nickolas, 12 лет назад, По-русски

A. HQ9+

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

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 96 (Div. 1)
Разбор задач Codeforces Beta Round 96 (Div. 2)
  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

Автор Nickolas, 12 лет назад, По-русски

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +135
  • Проголосовать: не нравится

Автор ag45root, 12 лет назад, перевод, По-русски
Добрейшего!

11 декабря 2011 Молодёжное научное общество "Q-BIT" и кафедра информационных систем Харьковского национального экономического университета проводят традиционный (уже 9-й по счёту) открытый Чемпионат Харькова по спортивному программированию.

Чемпионат является регулярным (проводится два раза в год) и одним из наиболее массовых соревнований по программированию в Украине.

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

Участвовать можно как "онсайт" - лично присутствуя на Чемпионате, так и "онлайн" - т.е. удалённо.

Тестирующая система Чемпионата - DOTS (Distributed Olympiad Test System), в разработке которой принимал участие dzulgakov

  • для "онсайт" участников до 5 декабря 2011
  • для "онлайн" участников до 09:00 11 декабря 2011
Следите за новостями на сайте http://qbit.org.ua!
Официальный сайт Чемпионата http://khcup.qbit.org.ua

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор MikeMirzayanov, 12 лет назад, По-русски

Всем привет!

2-го декабря (в пятницу) в 19:00 (московское время) будет проведен неофициальный нерейтинговый контест Codeforces Testing Round #3. Во время него мы проверим на практике, что последние нововведения Codeforces не влияют на ход соревнований, а если это не так, то быстренько все исправим :) Так что этот раунд будет проходить as is, никаких гарантий на ход его проведения я не даю.

Задачи на раунде кому-то могут оказаться известными, но я постараюсь сделать так, чтобы это было верно не для всех. Будет 3-4 довольно простых задач. Продолжительность соревнования — 1 час.

Говорю заранее спасибо всем тем, кто придет и протестирует систему. Спасибо!

Все изменения в системе будут сугубо внутренние, видимых нововведений почти не будет.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +81
  • Проголосовать: не нравится

Автор MikeMirzayanov, 12 лет назад, По-русски

Полуфинал чемпионата мира по программированию завершен. Поздравляем победителей и призеров! Особенно хочется отметить команды, которые будут представлять наш регион на финале в Варшаве:

  1. SPb NRU ITMO 1 (Kapun, Kever, Nigmatullin) — 1-ое место, чемпионы региона
  2. Moscow SU 1 (Fedorov, Kaluzhin, Rogulenko) — 2-ое место
  3. Belarusian SU 1 (Bahdanau, Pisarchyk, Sobol) — 3-е место
  4. Saratov SU 2 (Ivanov, Kuznetsov, Rakhov)
  5. SPb SU 1 (Andreev, Boykiy, Fondaratov)
  6. Moscow IPT 1 (Dlugach, Gimadeev, Shishkin)
  7. Ural FU 1 (Dolgorukov, Schelkonogov, Soboleva)
  8. Altai STU 1 (Silin, Uvarov, Yesipenko)
  9. Ufa SATU (Lezhankin, Mazgarov, Ripatti)
  10. Nizhny Novgorod SU (Lyulkov, Shmelev, Vadimov)
  11. Belarus SUIR 2 (Berezhnov, Brukau, Ropan)
  12. Udmurt SU (Abizyaev, Kibardin, Urbanovich)
  13. Latvian U 2 (Kalinicenko, Vihrovs, Vilcins)
  14. Kazakh-British TU 3 (Aitbayev, Satylkhanov, Almakhan)
  15. Tomsk SU 1 (Chadnov, Kolupaev, Afanasev)
  16. Volgograd STU (Agafonov, Chalyshev, Zhorin)

Проект Codeforces желает всем будущим участникам финала успехов в подготовке к ответственному соревнованию и достойных результатов в финале!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +92
  • Проголосовать: не нравится

Автор MikeMirzayanov, 12 лет назад, По-русски

Всем привет!

В пятницу, 25-го ноября в 19:00 вас ожидает раунд, который был подготовлен мной. Подготовить раунд занятие хлопотное, но полезное и интересное. Своим примером я хочу намекнуть нашим топовым участникам, что раунды от известных людей — это всегда интересно!

Кроме меня раунд для вас делали RAD, Nickolas и Delinur. Им большое спасибо. Более того, Edvard еще не в курсе, но совсем скоро я попрошу его прорешать этот раунд в качестве тестера :)

Необычность раунда еще состоит в том, что вас ждет 6 задач. Это небольшой эксперимент — надеюсь, что это поможет каждому участнику найти интересные для себя задачи.

Полагаю, что внеконкурсное участие Div.1 участников сможет помочь немного разнообразить пятничный вечер.

Расценки в баллах на задачи будут такими: A - 500, B - 1000, C - 1500, D - 2000, E - 2500 и F - 2500.

MikeMirzayanov

UPD. Соревнования закончилось. Вот результаты. Первое место занял представитель Китая — liuq901. Приятно было наблюдать столь большой интерес к контесту. Спасибо за участие!

К сожалению, у меня нет возможности написать разбор. Если с этим справиться кто-то из членов сообщества, буду благодарен.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +75
  • Проголосовать: не нравится