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

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

Всем привет!

В эти дни в Москве проходит уже четвёртая Международная олимпиада мегаполисов — международное соревнование для школьников из крупнейших городов и столиц мира, одной из дисциплин которого является информатика. Над турами по информатике имели удовольствие работать члены жюри, приглашённые из Санкт-Петербурга, Минска и Белграда, а также Московская методическая комиссия, известная вам по Московской командной олимпиаде, Открытой олимпиаде школьников по программированию и Московской олимпиаде для 6-9 классов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567).

В составе жюри олимпиады: Chmel_Tolstiy, Jelena Hadži-Purić, Елена Андреева, Zlobober, GlebsHP, andrewzta, meshanya.

Задачи олимпиады разрабатывали isaf27, cdkrot, manoprenko, GoToCoding, ch_egor, vintage_Vlad_Makeev, voidmax, grphil, malcolm под руководством GlebsHP и Zlobober.

Задачи адаптированы под codeforces vintage_Vlad_Makeev и cdkrot, спасибо MikeMirzayanov за системы codeforces и polygon, который использовался при подготове задач этой олимпиады. Также спасибо за тестирование LHiC, voidmax и wrg0ababd!

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

Раунд состоится 04.09.2019 12:05 (Московское время) и будет идти два с половиной часа.

Раунд будет состоять из 8 задач и будет общим для обоих дивизионов. Раунд будет рейтинговым для всех участников!

P.S. Мы просим всех, кто участвует или знает задачи с основного соревнования, воздержаться от участия в раунде и публичного обсуждения задач, в противном случае вы можете быть дисквалифицированы.

UPD1: Победители!

  1. jqdai0815
  2. gina0605
  3. never_giveup
  4. Radewoosh
  5. 244mhq
  6. cz_yixuanxu
  7. ko_osaga
  8. mango_lassi
  9. GoForIt
  10. ksun48

Разбор будет опубликован скоро.

UPD2: Разбор

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

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

Автор ch_egor, 6 лет назад, По-русски
Tutorial is loading...

(Разработка и идея — vintage_Vlad_Makeev)

Tutorial is loading...

(Разработка и идея — MikeMirzayanov)

Tutorial is loading...

(Разработка — cdkrot, идея — жюри)

Tutorial is loading...

(Разработка — Sehnsucht, идея — Андреева Е. В.)

Tutorial is loading...

(Разработка и идея — VFeafanov)

Tutorial is loading...

(Разработка и идея — Sender)

Tutorial is loading...

(Разработка и идея — voidmax)

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

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

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

Всем привет!

В эту субботу пройдет московская олимпиада школьников по программированию для 6-9 классов. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516).

Раунд состоится в 13:05 23 февраля. Вам будет предложено 6 задач и 2 часа на их решение. Раунд будет рейтинговым для второго дивизиона (рейтинг ниже 2100). Как обычно, участники из первого дивизиона могут написать контест вне конкурса.

Задачи соревнования подготовлены vintage_Vlad_Makeev, grphil, cdkrot, VFeafanov, Sehnsucht, Sender, voidmax под моим руководством.

За координацию раунда и перевод условий спасибо cdkrot, а так же MikeMirzayanov за системы Codeforces и Polygon, который использовался при подготовке задач этой олимпиады.

Всем удачи!

UPD1: Из-за решений, принятых в последний момент, в раунде будет 7 задач.

UPD2: Победители!

Div 2:

  1. Big_gold_date

  2. PinkieRabbit

  3. disposrestfuIIy

  4. Dobrobober

  5. szh0808

  6. prodakcin

  7. Argentina

  8. afedor

  9. bigelephant29

  10. Young25

Div.1 + Div.2:

  1. JustasK

  2. BigBag

  3. Egor.Lifar

  4. Big_gold_date

  5. waynetuinfor

  6. dreamoon_love_AA

  7. danya090699

  8. KrK

  9. Farhod

  10. PinkieRabbit

UPD3: Разбор

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

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

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

Всем привет!

В воскресенье в Москве пройдет шестнадцатая Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской олимпиаде для 6-9 классов и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507).

Раунд состоится в 13:05 14 числа и продлится 2 часа. В каждом дивизионе будет предложено по 6 задач.

Задачи соревнования подготовлены vintage_Vlad_Makeev, Glebodin, Andreikkaa, qoo2p5, mingaleg, Flyrise, cdkrot, achulkov2, grphil, Sehnsucht, Aphanasiy, Sender, DebNatkh, GreenGrape под моим руководством, а также GlebsHP, meshanya, Endagorion, Zlobober и Андреевой Е. В.

За координацию раунда и перевод условий спасибо cdkrot, а так же MikeMirzayanov за системы codeforces и polygon, который использовался при подготовке задач этой олимпиады.

Всем удачи!

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

500 — 10001000 — 1500 — 2000 — 2500 для div. 1.

500 — 1000 — 1500 — 20002000 — 2500 для div. 2.

UPD2: Разбор

UPD3: Победители:

Div. 1:

  1. mnbvmar
  2. bmerry
  3. jcvb
  4. TLEwpdus
  5. WA_TLE

Div. 2:

  1. Ebola_Emperor
  2. Orange_User
  3. orbitingfIea
  4. little_waxberry
  5. fnch

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

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

Автор ch_egor, 7 лет назад, По-русски
Tutorial is loading...

(Разработка — vintage_Vlad_Makeev, ch_egor, V--o_o--V, demon1999)

Tutorial is loading...

(Разработка — ch_egor)

Tutorial is loading...

(Разработка — ch_egor)

Tutorial is loading...

(Разработка — halin.george)

Tutorial is loading...

(Разработка — Sehnsucht)

Tutorial is loading...

(Разработка — cdkrot, ch_egor)

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

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

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

Всем привет!

Завтрашний раунд пройдёт в нестандартное время на наборе задач Московской олимпиады школьников по программированию для 6-9 классов. Пусть вас не смущает возраст участников, московская методическая комиссия постаралась отобрать для олимпиады разнообразные и интересные задачи. Непосредственной разработкой задач занимались halin.george, Sehnsucht, cdkrot, vintage_Vlad_Makeev и ch_egor.

Спасибо MikeMirzayanov за прекрасную платформу Codeforces для проведения контестов и замечательную платформу Polygon, значительно упрощающую подготовку задач.

Спасибо V--o_o--V за сокращение официальных легенд задач и перевод их на английский язык.

Надеемся увидеть вас завтра в таблице результатов!

UPD1: Разбалловка 500-1250-1250-1500-2000-2750

UPD2: Наши разработчики очень устали после вчерашней олимпиады, поэтому разбор будет позже. Приносим извинения.

Победители:

Division 2:

  1. zzs_dasc

  2. Kataoka_Yuuki

  3. AkiLotus

  4. tshil

  5. WatchClannad

Division 1 + 2 (unofficial):

  1. uwi

  2. zzs_dasc

  3. fmota

  4. Kataoka_Yuuki

  5. eddy1021

UPD3: Разбор

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

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

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

Если заметите неточности или ошибки, сообщите личным сообщением.

Div2A Раздача мороженого

Автор идеи: cdkrot
Подготовил задачу: ch_egor

В задаче требовалось просто реализовать то, что было сказано в условии.

Если у вас не получилось, то возможно вы забыли использовать 64-битные типы данных, или сделали какую-то ошибку.

Код правильного решения:

C++ code
Python code

Div2B Зверинец маленькой разбойницы

Автор идеи: ch_egor
Подготовил задачу: ch_egor

Нам нужно отсортировать массив достаточно странными действиями, а именно — поменять местами элементы с четными и нечетными индексами на подотрезке четной длины. Заметим, что мы можем поменять 2 соседних элемента местами, просто выполнив наше действие обмена для подотрезка длины 2, содержащего эти элементы. Так же заметим, что n ≤ 100, а позволенно делать 20 000 действий, следовательно, мы можем написать любую квадратичную сортировку, которая меняет соседние элементы на каждой итерации (пузырьковую сортировку например).
Асимптотика O(n2)

C++ code
Python code

Бонус: Кто-нибудь умеет искать минимальное по длине решение данной задачи? Если да, то за какую сложность?

Div2C Разбойничьи часы/Div1A Разбойничьи часы

Автор идеи: cdkrot
Подготовил задачу: themikemikovi4

В этой задаче есть очень важное ограничение, а именно, используется семеричная система счисления! Давайте посчитаем сколько всего цифр отображается одновременно на циферблате часов и назовем cnt. Если cnt больше чем 7, то ответ, очевидно, 0. Если же cnt не больше 7, то переберем все возможные варианты выбора cnt цифр из 7 и в каждом варианте переберем все перестановки.
В зависимости от реализации получаем O(BASEBASEBASE), O(BASEBASE) или O(BASEBASE!), где BASE = 7.
Та же заметим, что в случае, когда cnt ≤ 7 мы можем просто 2 циклами перебрать час от 0 до n - 1 и минуту от 0 до m - 1 и проверить каждое время за O(cnt).
В худшем случае это отработает за O(BASEBASEBASE).

C++ code
Python code

Бонус: Предположим система счисления не фиксированная, а произвольная. Решить задачу при n ≤ 109, m ≤ 109, BASE ≤ 109. Можете ли вы сделать это за ?

Div2D Кай и снежинки/Div1B Кай и снежинки

Автор идеи: cdkrot
Подготовили задачу: ch_egor, cdkrot

Данная задача имеет несколько решений.

Решение от cdkrot:
Рассмотрим кандидатов на центроид поддерева вершины v. Очевидно, что размер поддерева центроида должен составлять хотя бы размера поддерева вершины v. Выберем из таких вершин вершину с минимальным размером поддерева. Если мы удалим эту вершину, то останется часть поддерева, связная с v размером не больше исходного поддерева и несколько других, размер каждой из которых тоже будет не более половины размера исходного поддерева. Следовательно мы нашли центроид. Чтобы быстро искать такую вершину выпишем эйлеров обход дерева и будем использовать двумерное дерево отрезков.
Асимптотика

C++ code

Так же можно насчитать ответы для всех поддеревьев за один dfs используя данную идею — будем использовать std::set по паре (размер поддерева, номер вершины) и в каждой вершине сливать сеты, полученые при запуске от детей. Таким образом мы получим ответы для всех вершин и нам остается только вывести ответы на запросы.
Асимптотика

C++ code

Решение от ch_egor:
Решим для всех поддеревьев. Пусть решаем задачу для какого-то поддерева, решив задачу для всех его детей. Выберем самого тяжёлого сына. Заметим, что центроид этого сына при некотором подъёме перейдёт в наш центроид. Промоделируем подъём. Таким образом мы получим ответы для всех вершин и нам остается только вывести ответы на запросы.
Асимптотика O(n + q)

C++ code

Div2E Оптимальная точка/Div1C Оптимальная точка

Автор идеи: cdkrot
Подготовил задачу: cdkrot

Пару слов о тернарном поиске. Тернарный поиск работает слишком долго.
Асимптотика работы тернарного поиска , где n = 105, а v = 1018.

Решение.
1) Давайте сделаем бинпоиск по ответу.
2) От каждой из данных точек отложим область подходящих точек (на расстоянии  ≤ mid).
3) Пересечём области и проверим на пустоту.

Области будут иметь форму правильных октаэдров, и каждую из них можно описать системой линейных неравенств следующего вида:

(Получить данные уравнения можно расписав условие того, что манхэттанское расстояние  ≤ mid)

.. ≤ x + y + z ≤ ..


.. ≤  - x + y + z ≤ ..


.. ≤ x - y + z ≤ ..


.. ≤ x + y - z ≤ ..


Где вместо .. стоят какие-то числа.

Пересечением множества таких систем будет система такого же вида, поэтому остаётся научится проверять существование решений у такой системы.

Сделаем замену:

a =  - x + y + z


b = x - y + z


c = x + y - z


Тогда:

x + y + z = a + b + c


x = (b + c) / 2


y = (a + c) / 2


z = (a + b) / 2


Итого имеем систему:

.. ≤ a ≤ ..


.. ≤ b ≤ ..


.. ≤ c ≤ ..


.. ≤ a + b + c ≤ ..


Нам нужно проверить есть ли решение у такой системы в целых числах, при этом числа a, b, c должны быть одной чётности (чтобы конечные x, y, z тоже были целыми).

Как избавится от условия на одинаковую чётность? Давайте переберём какой чётности должны быть a, b, c (2 варианта).

Сделаем замену a = 2a' + r, b = 2b' + r, c = 2c' + r, где r = 0 или r = 1. Подставим, приведём, и получим систему такого же вида, но без обременения по поводу чётности.

Оставшаяся система легко решается жадно (Сначала набираем a, b, c по минимуму, а затем, в случае необходимости, потихоньку повышаем).

Итого асиптотика решения .

C++ code

Бонус. У задачи есть много разных вариаций, например евклидово расстояние вместо манхэттенского, 2d вместо 3d, флоты вместо целых. Как решить эти вариации?

Div1D Кай и вечность

Авторы идеи: platypus179, Endagorion
Подготовил задачу: platypus179

Будем решать данную задачу методом сканирующей прямой. Будем идти по вертикалям слева на право и поддерживать массив, в котором на i вертикали в j ячейке будет храниться количество точек в квадрате с координатой левого нижнего угла (i, j). Сейчас это требует O(MAXCORD2) времени.

Заметим, что множество квадратов, которые содержат какую-то из закрашеных точек не очень велико, а именно — если точка имеет координаты (x, y), то множество левых нижних углов квадратов, содержащих ее задается так: {(a, b)|x - k + 1 ≤ a ≤ x, y - k + 1 ≤ b ≤ y}. Давайте рассматривать каждую точку (x, y) как 2 события:
Прибавить единицу на отрезке с y - k + 1 по y на вертикали x - k + 1 и отнять единицу на этом же отрезке на вертикали x + 1. Как же считать ответ при таком методе решения? Пусть мы обновляем значение ячейки на вертикали a, а до этого обновляли ее значением x на вертикали b. Прибавим к ответу для количества квадратов, содержащих x точек значение a - b. Мы можем реализовывать прибавление на отрезке в лоб и получим O(nk) на обработку всех событий, что укладывается по времени. Чтобы избавиться от O(MAXCORD) памяти, выпишем перед обработкой событий все интересующие нас координаты (их не более nk) и сожмем координаты в событиях. Это займет времени и O(nk) памяти. Теперь мы можем выполнить предыдущий пункт за O(nk) памяти.
Итоговая асимптотика времени и O(nk) памяти.

C++ code

Бонус: времени и O(n) памяти.

C++ code

Div1E Путешествие по царству Снежной королевы

Авторы идеи: cdkrot, GlebsHP
Подготовили задачу: ch_egor, cdkrot

Из-за моей (cdkrot) ошибки было возможно сдать задачу с решением за O(nm). Приношу свои извинения.

Мы предлагаем следующее решение:
Решим задачу используя метод разделяй и властвуй. Для начала поднимем l до первого индекса, в котором s была упомянута. Также опустим r до того индекса, где упомянута вершина t Это не повлияет на ответ, но позволит сделать дальнейшее решение гораздо проще.

Посмотрим на запросы, для каждого запроса определим его расположение относительно центра массива рёбер. Либо он целиком справа, либо целиком слева, либо содержит середину. В первых двух случаях решим рекурсивно. (Предлагается написать функцию solve(reqs, l, r))

Решим третий случай. Предпосчитаем вспомогательные динамики:

dpr[i] =  bitset вершин из которых можно попасть в вершину vi или ui, считая, что l = m и r = i.

dpl[i] =  bitset вершин до которых можно дойти из vi или ui, считая, что l = i и r = m - 1

vi и ui — вершины i-го ребра.

Ответ на запрос будем "Yes" тогда и только тогда, когда: dpl[l][u] = true и dpr[r][u] = true для некоторого u.

Все вышесказаное нужно реализовать используя битовые операции. Итого время работы:

C++ code

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

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