Всем привет!

Совсем скоро, 16 декабря в 19:30 MSK состоится Codeforces Round #156, автором которого являюсь я. Это мой второй раунд на Codeforces и я надеюсь, что не последний.

Спасибо Steps09, Seyaua и sdya за помощь в тестировании задач, а также Gerald за помощь в подготовке раунда. Отдельное спасибо Delinur за перевод условий на английский.

Разбалловка в первом и во втором дивизионе стандартная: 500-1000-1500-2000-2500.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

Контест окончен, надеюсь вам понравилось :)

Поздравляю победителей див1:
1). YuukaKazami
2). al13n
3). rng_58
4). Bigsophie
5). KADR

И победителей див2:
1). ShadowSong
2). ynbpdy072
3). jiaobu

Разбор задач по ссылке.

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

Как все вы уже знаете, олимпиада была проведена в Sermione и Montichiari.
Sermione — не большой курортный городок, содержащий множество 3х и 4х звездочных отелей. В одном из таких отелей(точнее говоря поселке) под название Garda Village были поселены все участники олимпиады. Вот несколько фоток поселка:

Домики участников:

Домики организаторов:

Поселок находится на берегу озера Garda, за озером иногда было видно горы. Когда мы сидели на лавочке и любовались пейзажами, Рома(Furko) говорил, что даже ради того, что-бы посмотреть на это в живую стоит проходить на соревнования такого уровня.
Собственно пейзажи:

По последней фотке, в первый день, наличие кроликов напомнило Канаду, где было много белок.

Как на любом онсайте, в первые дни происходит много знакомств, мы тоже не упустили такой возможности :) Но к сожелению фоток с другими странами крайне мало.

На второй день было открытие. Как обычно это бывает (для меня так было все 3 межнара) оно было весьма скучно. Несколько парней играли на пианино, ведущий пытался шутить, но как получилось самые удачные шутки были про спящих там участников и лидеров. Про само открытие больше сказать нечего, так уж сложилось что я был одним из тех, над кем мог пошутить ведущий :) Очень понравились веселые костюмы некоторых команд, например шапки белорусов:

или маски мексиканцев:

Фотки нашей сборной выложу чуть-чуть позже.

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

После обеда нас повезли домой, где мы уже настраивались на завтрашний тур. После ужина был карантин, нам выключили wi-fi, и забрали телефоны, организаторы пошли переводить задачи.

Следующим утром мы поехали в тоже место, где было открытие: писать тур. Про задачи вам уже рассказали тренеры России. Но все же тоже немного про них расскажу.
Первая задача была стиля "Unknown Laguage Round", разделена на 5 блоков по 9, 12, 19, 32, 28 баллов соответственно. Суть задачи: научить робота собирать камешки и перемещаться в нужную клетку по некоторой информации. Задача весьма интересна, но коды на нее были просто огромных размеров.
Вторая задача была про граф, в который в онлайне добавляется ребра и нужно говорить кол-во вершин, после удаления которых распадается на цепочки (компонента в которой нету циклов, и все вершины степени меньше-равно 2). Задача весьма простая, но я не придумал очевидной халявы: вся суть в том, что когда у вершины 3 соседа, то ответами могут быть только они или сама вершина. Я пропустил момент когда такое получается, и думал над случаем, когда у вершины порядка 100000 соседей, не знаю почему не придумал :(
Третья задача — персистентный стек, тоесть есть запрос добавить букву или отменить последние х команд, отмена тоже может быть отменена. Собственно достаточно заметить что у нас будет ребро в предыдущую вершину или в вершину которую приведет отмена. На ребре будет буква, для каждой вершины нужно запомнить длину слова в ней. Дальше простой двоичный подъем. Ответ на запрос (Хя буква текущего слова), очевиден при помощи такой структуры.

В результате у меня было 40+55+100 = 195, что выходило 30е место. Я очень сильно ругался когда у мне не хватило 1 миунты, что-бы доздать 1ю задачу на +10-18 баллов (4я подзадача).

Я и Фурик общаямся по скайпу после первого тура:

Потом был массовый прорсмотр результатов :) :

На 4й день мы решили забыть про результаты и круто оторваться в парке Garda Land :)
Я на фоне парка:

Несколько фоток из парка:

Наша команда:

Парк был просто крутой, очереди маленькие — катались много и везде, в отличии от Канады, где очереди в среднем были по 30 минут. Цены на все были весьма высоки.
На водном атракционе, когда мы свалились с горки, нас еще с автомата обстреливали ребятки, буквально через пару минут я их подменил :)) 1 минута поливания — 40 центов, кусается, но очень приятно :))

Иногда пересекались с другими командами, иногда даже катались вместе :) Фотка 6/8 участников команд Украины и Белорусии:

После поездки снова начался карантин.

Перед вторым туром я вспомнил, что это было мое последнее школьное соревнование, и что нужно не втыкать. А непосредственно перед туром полностью настроился его писать.
3! 2! 1! тур начался!
1я задача показалась очевидной в первых 3х блоках, но писать ее не стал, временно. 2ю задачу сразу читать не стал, при виде ВОСЬМИ страниц условия. 3я показалась весьма интересной, за час с лишним я ее осилил. Дальше пошли в ход решения по 1й, когдла сдал ее на 55 перешел к 2й, за 30 минут вник в условие, увидел халявное решение на первые 2 блока, через минуту придумал 3й, написал и на удивление получил еще 16 баллов за последний субтаск (как и предпологалаось авторами). Дальше я сел думать над 4й группой, и за 2 с лишним часа не придумал, да над 1й задачей я почти не думал, точнее думал в течении 20 минут где-то. Под конец тура я был уверен, что у меня серебро, но по окончанию тура я узнал что у 3их ребят из России такой-же балл (198) как и у меня. Мою радость было не описать когда я увидел таблицу. Единственное, что еще немного меня тревожило, что результаты могли быть не окончательны, как на 1м туре(там я был 29, хотя на самом деле 30й). Но меня успокоили, что уже точно все нормально. У наших ребят все было не так уж и хорошо, Рубик упал в бронpу, Фурик на границу, которая потом еще и сместилась. Виталик остался в серебре. После тура мы пошли релаксить на озеро, басейн, теннис и прочие места.

Следующий день оказался очень непамятным для меня, так как "хорошая" организация разбудила нас в 5 утра и отправила на не интересную экскурсию в красивый город Венецию:

Организация там была просто позорной. Все спали на ходу по двум причинам: не выспаны, не интересно слушать тихие непонятные разговоры ведущих. Больше по этому дню писать ничего не буду.

Закрытие прошло также не организовано. Начался дождь, и в зале сидели только медалисты, остальные были на балконе. На закрытии президент сказал, что олимпиада была проведена по "итальянски" :). Еще они начали вручать бронзу серебряным медалистам, потом одумались, правда. топ 3 вызывали по очереди, в отличии от всех остальных (группами). Победителю дали кубок и медаль. Странам-победителям дали чеки на 8К евро, как потом окзалось на обучение в Милане. Потом нас быстро отправили домой, по пути у половины участников поломались медали, точнее они поотрывались с ленточки. Ужин был значительно вкуснее предыдущих дней, нам дали сосиски :)
Пару фоток нашей сборной:

После ужина было пати, но это уже не публично :)

Обычно есть еще куча деталей, которые делали событие более интересным, но их все не опишешь тут, их можно только рассказать. Надеюсь вам понравился обзор, он был мой первый так что не судите строго :)

У кого-то заходит на сервер в данный момент?

214A - Система уравнений

В данной задаче решение — просто перебрать возможные пары чисел и проверить их на правильность. Делать это можно было любым способом.

214B - Домашнее задание

Число делится на 2,3,5 только в том случае, если сумма цифр кратна 3, а последняя цифра 0, то есть если в наборе нету нулей, то ответ -1. Дальнейшее решение — разбор случаев.
Возьмем все цифры в невозрастающем порядке, если сумма цифр кратна 3, то это и есть ответ. Если остаток от деления вышел 1, то нужно убрать 1 цифру у которой остаток от деления на 3 равен 1. Если такой не нашли то нужно убрать 2 цифры с остатком 2. Аналогично рассматривается случай когда изначальный остаток равен 2. Так-же нужно рассмотреть случай когда остались только нули, в этом случае нужно вывести только 1 ноль.

213A - Игра

Решение — жадность. Пусть у нас компьютеры стоят по кругу, и ходами "вперед" назовем перемещения (1->2, 2->3, 3->1), а перемещением "назад" (1->3,3->2,2->1).

Заметим что ходить "назад" не выгодно, так как можно 2 раза походить "вперед", что в сумме равноценно. Будем перебирать стартовую вершину. Дальше будем ходить по кругу до тех пор, пока не "откроем" все уровни. В авторском решении для каждого уровня поддерживается количество уровней, которые нужны для него. После того как мы находим очередной 0 в этом списке, мы просто уменьшаем такую величину для всех уровней, которые от него непосредственно зависят. Сложность решения O(n^3).

213B - Числа

Решение — динамика. Перебираем длину числа, которое будем строить. Далее будем пользоваться динамикой f(len,i) — сколько чисел диной len можно составить из цифр i..9.
Пересчет:
- f(len,0) = sum(f(len-i,1)*C(len-1,i), i=a[0]..len);
- f(len,j) = sum(f(len-i,j+1)*C(len,i), i=a[j]..len), 0<j<9;
- f(len,9) = 1, если len>=a[9], 0 если len<a[9].
C(n,k) — количество способов выбрать k элементов из n.

213C - Эстафета

Решение — динамика.
Заметим, что мы можем просто провести два пути их клетки (1,1) в клетку (n,n).
Заметим, что после каждого шага клетки будут оставаться на одной диагонали. Будем решать задачу динамикой f(d,i1,i2), d — номер диагонали, i1 — 1я координата 1го маршрута, i2 — 1я координата 2го маршрута. Понятно что вторую координату мы можем определить однозначно. Переходы — очевидны, делаем 4 возможных перехода, если маршруты пересеклись, то добавляем величину клеточки один раз, иначе добавляем величины посещенных клеток. Так как данная динамика не влазит по памяти, то ее нужно делать двумерной, просто перенося значения из прошлой диагонали в новую.
Еще нужно не забыть про то, что ответ может выйти отрицательным.

213D - Звезды

Предоставлю разбор как небольшую презентацию картинками:
https://get.google.com/albumarchive/pwa/115317317397602031319/Solutions131

Реализация.
Единственную сложность могло составить определение координат, все координаты можно найти из правильного пятиугольника. Все что о нем нужно описано тут.

213E - Две перестановки

Первый шаг: заменить перестановки на обратные, то есть из перестановки A мы делаем перестановку B, такую что B[A[i]] = i. Если посмотреть на то, что получилось, то выходит такая задача: сколько подотрезков второй перестановки равны первой, в случае если мы "сожмем координаты", то есть числам сопоставим их номер в отсортированном виде. Эту задачу предполагалась решать хэшами, но брать их нужно было не только по основанию 2^64, а и еще по нескольким простым модулям, тайм лимит специально стоял 3 секунды.
Теперь, собственно, как ее решать: Для каждой позиции i — сопоставим коєфициент step[i], где step[i] = 1000003^i. Теперь Рассмотрим такую функцию: F(A) = num[1]*step[1] + num[2]*step[2] + num[3]*step[3] + ... + num[n]*step[n], где num[i] — порядковый номер элемента A[i] в отсортированном списке. Понято что эта функция однозначно задает множество, от нее и будем считать хэш.
Как пересчитывать при переходе не следующий элемент.
Заметим что когда мы убираем какой-то элемент, то все элементы которые больше его уменьшают значение num на единицу. Ровно как и после добавления они его увеличивают. То есть заведем Дерево отрезков/Фенвика для хранения таких величин как сумма степеней на отрезке и количество элементов на отрезку, что-бы за O(log(n)) находить величину num для числа и после каждого добавления/удаления будем пересчитывать хэш, тоже за O(log(n)). Так-же нужно будем умножать хэш на от первой перестановки на 1000003 после каждого смещения на 1 элемент вправо, так как коэффициенты step уже не будут идти от единицы.

Все замечания просьба писать в комментарии.

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

Всем привет!

Сегодня, 30 июля в 19:30 MSK состоится Codeforces Round #131, автором которого являюсь я(Сергей Нагин). Это мой первый раунд на Codeforces и надеюсь, что не последний.

Спасибо Фурко Роману(Furko) и Геральду Агапову(Gerald) за помощь в подготовке задач, а Марии Беловой(Delinur) за перевод условий. Также выражаю благодарность создателю Codeforces Михаилу Мирзаянову (MikeMirzayanov) за прекрасную систему.

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

Разбалловка в первом дивизионе: 1000-1000-1500-2000-2500. Разбалловка во втором дивизионе: 500-1000-2000-2000-2500. Настоятельно рекомендую прочитать условия ВСЕХ задач.

Контест завершен! Поздравляю победителей!

1й дивизион:
1 место: Egor
2 место: Petr
3 место: tourist
2й дивизион:
1 место: antimatter
2 место: c175353
3 место: takaramono

Надеюсь, задачи вам понравились.

Разбор задач.

Всем привет!
Думаю, уже наступило время создать нужный пост. Пишите в комментарии предварительный состав команд которые уже знаете, а я буду по мере поступления данных добавлять их в таблицу.

Давайте здесь обсуждать задачи.
Кто как делал J в усложненке?