Блог пользователя Vladosiya

Автор Vladosiya, история, 5 недель назад, По-русски

1932A - Шипы и монеты

Идея: denk

Разбор
Решение

1932B - Календарь Чая

Идея: Vladosiya

Разбор
Решение

1932C - LR-остатки

Идея: MikeMirzayanov

Разбор
Решение

1932D - Карточная игра

Идея: goncharovmike

Разбор
Решение

1932E - Финальный отсчёт

Идея: step_by_step

Разбор
Решение

1932F - Кормление кошек

Идея: denk

Разбор
Решение

1932G - Перемещающиеся платформы

Идея: denk

Разбор
Решение

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

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

Автор Vladosiya, история, 6 недель назад, По-русски

1931A - Восстановление маленькой строки

Идея: myav Разработка: myav

Разбор
Решение

1931B - Сделай равными

Идея: MikeMirzayanov Разработка: Vladosiya

Разбор
Решение

1931C - Снова сделай равными

Идея: senjougaharin Разработка: senjougaharin

Разбор
Решение

1931D - Делимые пары

Идея: MikeMirzayanov Разработка: Vladosiya

Разбор
Решение

1931E - Аня и подарок на День святого Валентина

Идея: Gornak40 Разработка: Gornak40

Разбор
Решение

1931F - Скриншоты чата

Идея: senjougaharin Разработка: senjougaharin

Разбор
Решение

1931G - Одномерный пазл

Идея: senjougaharin Разработка: senjougaharin

Разбор
Решение

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

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

Автор Vladosiya, история, 7 недель назад, По-русски

Привет! В 13.02.2024 17:35 (Московское время) начнётся Codeforces Round 925 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи были придуманы и написаны нашей командой: myav, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо:

  1. MikeMirzayanov за помощь с идеями и системы Polygon и Codeforces.

  2. nigus за красное тестирование раунда.

  3. vladmart, Gheal, KseniaShk за жёлтое тестирование раунда.

  4. htetgm за фиолетовое тестирование раунда.

  5. natalina, SashaT9, lockdown, bma20006 за синее тестирование раунда.

  6. RedDreams за бирюзовое тестирование раунда.

  7. the_Incharge, Aurora__, Longqiang за зелёное тестирование раунда.

Всем удачи!

P.S. С наступающим днём святого Валентина!

UPD: Давайте продолжим серию анонсов с фотографией авторов :)

UPD2: Разбор

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

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

Автор Vladosiya, история, 7 недель назад, перевод, По-русски

1927A - Сделайте белой

Идея: MikeMirzayanov

Разбор
Решение

1927B - По следам строки

Идея: MikeMirzayanov

Разбор
Решение

1927C - Выбери различные!

Идея: MikeMirzayanov

Разбор
Решение

1927D - Найди различные!

Идея: MikeMirzayanov

Разбор
Решение

1927E - Каровная перестановка

Идея: MikeMirzayanov

Разбор
Решение

1927F - Микроцикл

Идея: MikeMirzayanov

Разбор
Решение

1927G - Заряды с краской

Идея: MikeMirzayanov

Разбор
Решение

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

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

Автор Vladosiya, история, 4 месяца назад, По-русски

1907A - Ладья

Идея: pashka

Разбор
Решение

1907B - YetnotherrokenKeoard

Идея: pashka, MikeMirzayanov

Разбор
Решение

1907C - Удаление некрасивых пар

Идея: Vladosiya

Разбор
Решение

1907D - Прыжки по отрезкам

Идея: MikeMirzayanov, Vladosiya

Разбор
Решение

1907E - Хорошие тройки

Идея: pashka

Разбор
Решение

1907F - Сдвиг и разворот

Идея: pashka

Разбор
Решение

1907G - Освещение

Идея: pashka

Разбор
Решение

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

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

Автор Vladosiya, история, 4 месяца назад, По-русски

Привет! В 05.12.2023 17:45 (Московское время) начнётся Codeforces Round 913 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи были придуманы и написаны pashka, MikeMirzayanov и мной.

Часть задач раунда была в Cyprus Programming Challenge, если вы участвовали в нём, пожалуйста воздержитесь от участия в этом раунде.

Также большое спасибо:

  1. peltorator, FairyWinx за красное тестирование раунда.
  2. Vladithur, Valters07 за жёлтое тестирование раунда.
  3. stefanbalaz2, FBI, SlavicG, flamestorm, SashaT9, mesanu, trainerherp, Ush1su за фиолетовое тестирование раунда.
  4. dan_dolmatov, Yousef.Osama за синее тестирование раунда.
  5. Sergey140146659, Pa_sha, gas за бирюзовое тестирование раунда.

Всем удачи!

UPD: Разбор

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

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

Автор Vladosiya, история, 5 месяцев назад, По-русски

Hello, Codeforces!

I wanted to add CERC 2021 to gyms, but I can't seem to find the tests, checkers, and solutions. If you know where they can be found or someone who might have them, please let me know.

UPD: Thanks everyone for help and xiaowuc1 who shared the archive to me!

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

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

Автор Vladosiya, история, 6 месяцев назад, По-русски

1881A - Не пытайтесь посчитать

Идея: Vladosiya

Разбор
Решение

1881B - Три паутинки

Идея: Gornak40

Разбор
Решение

1881C - Идеальный квадрат

Идея: myav, MikeMirzayanov, Vladosiya

Разбор
Решение

1881D - Уравняй делением

Идея: myav

Разбор
Решение

1881E - Блоковая последовательность

Идея: MikeMirzayanov

Разбор
Решение

1881F - Минимальное максимальное расстояние

Идея: senjougaharin

Разбор
Решение

1881G - Аня и таинственная строка

Идея: Gornak40

Разбор
Решение

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

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

Автор Vladosiya, история, 6 месяцев назад, По-русски

Привет! В 12.10.2023 17:35 (Московское время) начнётся Codeforces Round 903 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи были придуманы и написаны нашей командой: myav, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо:

  1. MikeMirzayanov за системы Polygon и Codeforces.

  2. SomethingNew, rniya, zwezdinv за красное тестирование раунда.

  3. makrav, snowysecret, AlexanderL, KseniaShk, pavlekn за жёлтое тестирование раунда.

  4. gigabuffoon, EgorUlin, KerakTelor, Pa_sha, I_love_geom, petyb, MinaRagy06, toniskrijelj, FynjyBath за фиолетовое тестирование раунда.

  5. Abo_Samrah, dan_dolmatov, pedrosorio, ezdp, azureglow, Chrisedyong, Apachee, arseny2606 за синее тестирование раунда.

  6. t0rtik, Sergey140146659, hader239, Modern за бирюзовое тестирование раунда.

  7. mkshh, petertromso за зелёное тестирование раунда.

Всем удачи!

UPD: Разбор

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

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

Автор Vladosiya, история, 6 месяцев назад, По-английски

Hello, Codeforces!

We've compiled a list of command lines that Codeforces uses to compile and run solutions in various languages and compilers.

It is up-to-date as of today (2023-10-06), and we will make efforts to keep it current in the future, but this is not guaranteed.

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

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

Автор Vladosiya, история, 6 месяцев назад, По-русски

Привет, Codeforces! Месяц назад я начал работать неполный день у MikeMirzayanov. Пора поделиться итогами первого месяца!

Глобально я занимался несколькими вещами:

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

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

Автор Vladosiya, история, 7 месяцев назад, По-английски

Hello, Codeforces!

Today, MikeMirzayanov taught me how to add contests to the Gym, so we've started adding old Google Code Jam rounds. We think it's a good idea to create a comprehensive (or almost comprehensive) archive of all GCJ rounds in the Gym.

I've added 2015 Google Code Jam Round 1A (GCJ 15 Round 1A) and 2015 Google Code Jam Round 1C (GCJ 15 Round 1C) today. It seems that for the 2015 season, only the Finals are missing now. I'll be adding that soon as well!

While Google's archives don't include solutions, we did find a user-generated archive at https://github.com/kamyu104/GoogleCodeJam-2015. However, it would be great to have additional sources for verification.

Would any of you be able to help us find other reliable sources for correct solutions? This way, we can be absolutely sure that all uploaded problems are accurate.

Thank you!

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

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

Автор Vladosiya, история, 8 месяцев назад, По-русски

Привет, Codeforces! Довольно часто делал анонсы раундов, так что какое-то время назад сделал скрипт, который выдаёт весь список тестеров по цветам. Вы, конечно, можете его немного переписать, чтобы порядок был какой вам угодно.

Скрипт использует Codeforces API, так что первым делом вам нужно зайти в настройки аккаунта и сгенерировать ключи API и поместить открытый в файл "key", а секретный в файл "secret" в одной папке со скриптом (или просто присвоить их соответствующим переменным в скрипте). Теперь нужно просто заполнить массив contestids id мешапов, которые вы использовали для тестирования и запустить скрипт. По окончании своей работы скрипт создаст файлы "ru.txt" и "en.txt" с благодарностями на соответствующих языках.

Надеюсь он поможет вам быстро изменять список тестеров. Всем удачи и успешных раундов!

Скрипт

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

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

Автор Vladosiya, история, 8 месяцев назад, перевод, По-русски

1851A - Разговоры на эскалаторе

Идея: Vladosiya, разработка: Aris

Разбор
Решение

1851B - Сортировка четностью

Идея: Vladosiya, разработка: myav

Разбор
Решение

1851C - Плитки возвращаются

Идея: Vladosiya, разработка: myav

Разбор
Решение

1851D - Префиксные суммы перестановки

Идея: Gornak40, разработка: senjougaharin

Разбор
Решение

1851E - Настя и зелья

Идея: Vladosiya, разработка: Vladosiya

Разбор
Решение

1851F - Лиза и марсиане

Идея: Gornak40, разработка: Gornak40

Разбор
Решение

1851G - Влад и горы

Идея: Vladosiya, разработка: Vladosiya

Разбор
Решение

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

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

Автор Vladosiya, история, 8 месяцев назад, По-русски

Привет! В 25.07.2023 17:35 (Московское время) начнётся Codeforces Round 888 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи были придуманы и написаны нашей командой: myav, Aris, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо:

  1. MikeMirzayanov за системы Polygon и Codeforces.

  2. tute7627 за красное тестирование раунда

  3. oversolver, sevlll777, pavlekn, zwezdinv, Sokol080808, 74TrAkToR, vladmart, EJIC_B_KEDAX, Vladithur, KseniaShk, Be_dos за жёлтое тестирование раунда
  4. moonpie24, FBI, meowcneil, NintsiChkhaidze, Phantom_Performer, SashaT9, spike1236, Kalashnikov за фиолетовое тестирование раунда
  5. TheGoodest, Pa_sha, Sasha0738 за синее тестирование раунда
  6. Syuzi777, Tahseen за бирюзовое тестирование раунда

Всем удачи!

UPD: Разбор

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

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

Автор Vladosiya, история, 10 месяцев назад, перевод, По-русски

1833A - Музыкальный паззл

Идея: Vladosiya, разработка: Vladosiya

Разбор
Решение

1833B - Восстанови погоду

Идея: myav, разработка: myav

Разбор
Решение

1833C - Влад строит красивый массив

Идея: Vladosiya, разработка: Vladosiya

Разбор
Решение

1833D - Перевертыш

Идея: Gornak40, разработка: Aris

Разбор
Решение

1833E - Хороводы

Идея: MikeMirzayanov, Vladosiya, разработка: senjougaharin

Разбор
Решение

1833F - Ира и фламенко

Идея: Gornak40, разработка: Gornak40

Разбор
Решение

1833G - Ксюша и шиншилла

Идея: Gornak40, разработка: Gornak40

Разбор
Решение

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

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

Автор Vladosiya, история, 10 месяцев назад, По-русски

Привет! В 19.05.2023 17:35 (Московское время) начнётся Codeforces Round 874 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо: pavlekn, KoT_OsKaR, natalina, vladmart, Phantom_Performer, Be_dos, ctraxxd, diskoteka, lunchbox, kzyKT, MODDI, molney, FEDIKUS, Nickir, 74TrAkToR, kamishogun, KseniaShk, Sokol080808, NintsiChkhaidze, Asad5059, heon за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Разбор

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

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

Автор Vladosiya, 12 месяцев назад, По-русски

1811A - Вставь цифру

Идея: senjougaharin, разработка: senjougaharin

Разбор
Решение

1811B - Конвейерные ленты

Идея: Vladosiya, разработка: senjougaharin

Разбор
Решение

1811C - Восстанови массив

Идея: MikeMirzayanov, разработка: myav

Разбор
Решение

1811D - Умка и долгий перелёт

Идея: Gornak40, разработка: Gornak40

Разбор
Решение

1811E - Живая последовательность

Идея: Aris, разработка: Aris

Разбор
Решение

1811F - Это цветок?

Идея: Vladosiya, разработка: Vladosiya

Разбор
Решение

1811G1 - Влад и правильные пути (простая версия)

Идея: Vladosiya, разработка: Vladosiya

Разбор
Решение

1811G2 - Влад и правильные пути (сложная версия)

Идея: Vladosiya, разработка: Vladosiya

Разбор
Решение

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

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

Автор Vladosiya, 12 месяцев назад, По-русски

Привет! В 04.04.2023 17:35 (Московское время) начнётся Codeforces Round 863 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо: Sugar_fan, doreshnikov, powergee101, pashka, KseniaShk, 74TrAkToR, stefanbalaz2, playerr17, diskoteka, BF_OF_Priety, nigus, erankyun, plourde27, Be_dos, donghoony, lucasxia01, Jostic11, sansen, gigabuffoon, akulenok, pwned, vrintle за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Разбор

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

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

Автор Vladosiya, история, 13 месяцев назад, По-русски

1800A - Это кошка?

Idea: Vladosiya, MikeMirzayanov

Tutorial
Solution

1800B - Посчитай количество пар

Idea: myav

Tutorial
Solution

1800C1 - Усиление героев (простая версия)

Idea: Vladosiya

Tutorial
Solution

1800C2 - Усиление героев (сложная версия)

Idea: Vladosiya

Tutorial
Solution

1800D - Удали два символа

Idea: MikeMirzayanov

Tutorial
Solution

1800E1 - Непростительное заклятие (простая версия)

Idea: Aris, talant

Tutorial
Solution

1800E2 - Непростительное заклятие (сложная версия)

Idea: Aris, Vladosiya

Tutorial
Solution

1800F - Даша и кошмары

Idea: Gornak40

Tutorial
Solution

1800G - Симмеtreeя

Idea: Vladosiya

Tutorial
Solution

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

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

Автор Vladosiya, история, 13 месяцев назад, По-русски

Я обнаружил небольшую нехватку материалов на эту тему и хочу начать со статьи rationalex:

Задача

Хотим научиться сравнивать корневые деревья на изоморфизм (равенство с точностью до перенумерования вершин + корень одного дерева обязательно переходит в корень другого дерева).

Хеш вершины

Заметим, что поскольку мы не можем апеллировать к номерам вершин, единственная информация, которую мы можем оперировать — это структура нашего дерева.

Положим тогда хешем вершины без детей какую-нибудь константу (например, 179), а для вершины с детьми положим в качестве хеша некоторую функцию от отсортированного (поскольку мы не знаем истинного порядка, в котором дети должны идти, нужно привести их к одинаковому виду) списка хешей детей. Хешом корневого дерева будем считать хеш корня.

По построению, у изоморфных корневых деревьев хеши совпадают (доказательство индукцией по числу уровней в дереве автор оставляет читателю в качестве упражнения).

Полиномиальный хеш не подходит

Рассмотрим 2 дерева:

Если мы посчитаем для них в качестве функции от детей взять полиномиальный хеш, то получим: $$$h(T1)=179+179p+179p^2=179+p(179+179p)=h(T2)$$$

Какую же хеш-функцию взять?

В качестве хорошей хеш-функции подойдёт, например

$$$h(v)=42 + \sum_{u \in sorted\_by\_hash(child(v))} \log(h(u))$$$

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

Пример более complicated хеш-функции:

$$$h(v)= \big[\sum_{u \in sorted\_by\_hash(child(v))} h(u)^2+h(u)p^i+42\big]\mod2^{64}$$$

Асимптотика

Всё что нам нужно делать на каждом уровне — это сортировка вершин по значению хеша и суммирование, так что итоговая сложность: $$$O(|V| \log(|V|))$$$

Хочу продолжить от себя:

В реалиях Codeforces у данных подходов есть проблемы в виде взломов (что можно увидеть, например, по взломам этой задачи). Поэтому хочу рассказать о подходе, при котором не возникает коллизий.

Что же за хеш-функция?

Давайте для вершины отсортируем хеш-функции детей и сопоставим этому массиву номер, который и будем считать хешем вершины (если массив новый, то присвоим ему минимальный незанятый номер, иначе возьмём тот который уже дали).

Почему это работает быстро?

Легко заметить, что суммарный размер массивов, которые мы посчитали, равен $$$n - 1$$$ (каждое добавление это переход по ребру). Благодаря этому, даже используя для сопоставления treemap, на все обращения к нему потребуется суммарно $$$O(n \cdot \log(n))$$$. Сравнение ключа размера $$$sz$$$ с другим ключом работает за $$$O(sz)$$$ и таких сравнений для каждого ключа произойдёт $$$O(\log(n))$$$, а сумма всех $$$sz$$$ как мы помним равна $$$n-1$$$, так что получается суммарно $$$O(n \cdot \log(n))$$$. (Вы могли подумать что стоит использовать hashmap, но это не улучшает асимптотику и вызывает вероятность коллизии).

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

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

Автор Vladosiya, история, 13 месяцев назад, По-русски

Привет! В 02.03.2023 17:35 (Московское время) начнётся Codeforces Round 855 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо: tolbi, lunchbox, Son, sary, Wibo, yorky, nigus, tute7627, 74TrAkToR, bigfoot19982, oversolver, Be_dos, CARBINE, molney, KoT_OsKaR, Nickir, cute_hater, Crutch, vrintle, Rubikun, akulenok, medk, Jostic11, Ghassane за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Разбор

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

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

Автор Vladosiya, история, 14 месяцев назад, По-русски

1790A - Поликарп и День числа Пи

Идея: MikeMirzayanov

Разбор
Решение

1790B - Таисия и кубики

Идея: Gornak40

Разбор
Решение

1790C - Престановка

Идея: MikeMirzayanov

Разбор
Решение

1790D - Матрёшки

Идея: MikeMirzayanov

Разбор
Решение

1790E - Влад и пара чисел

Идея: Vladosiya

Разбор
Решение

1790F - Тимофей и черно-белое дерево

Идея: molney

Разбор
Решение

1790G - Фишки на графе

Идея: senjougaharin

Разбор
Решение

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

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

Автор Vladosiya, история, 14 месяцев назад, По-русски

Привет! В 27.01.2023 17:35 (Московское время) начнётся Codeforces Round 847 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, senjougaharin и Vladosiya. Также в этот раз одну из задач предложил molney.

Также большое спасибо:alwyn, morasha3, csegura, BledDest, stevenkplus, Darko, Coki628, Crutch, Qwerty1232, Jostic11, liouzhou_101, Jeffin, AW_Flister, glebustim, yorky, mango_lassi, 74TrAkToR, ErrorDeveloper, Be_dos, MODDI, Vercingetorix за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Разбор

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

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

Автор Vladosiya, история, 16 месяцев назад, По-русски

1759A - Да-да?

Идея: MikeMirzayanov

Разбор
Решение

1759B - Потерянная перестановка

Идея: MikeMirzayanov

Разбор
Решение

1759C - Термостат

Идея: Vladosiya

Разбор
Решение

1759D - Сделай круглым

Идея: MikeMirzayanov

Разбор
Решение

1759E - Гуманоид

Идея: Gornak40

Разбор
Решение

1759F - Всевозможные цифры

Идея: senjougaharin

Разбор
Решение

1759G - Восстанови перестановку

Идея: MikeMirzayanov

Разбор
Решение

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

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