Всем привет!

В этом году Чемпионат Урала пройдет в Уфе 30 апреля на площадке Уфимского Государственного Авиационного Технического Университета.

Официальный сайт соревнования.

Правила отбора можно найти здесь.

Хочу обратить внимание, что отбор команд, не входящих в списки приглашенных, будет проводиться на базе этапа Открытого Кубка (OpenCup) ГранПри Польши, который пройдет 26 марта 2017 года.

Оргвзнос не предусмотрен.

Дополнительная информация будет появляться на официальном сайте по мере поступления.

UPD. Обратите внимание на изменение правил отбора.

UPD. Регистрация открыта.

UPD. Регистрация продлена до 16 апреля! Также отдельная просьба тем командам, которые приглашены, но точно не приедут — сообщить мне в личку.

важный UPD в конце записи

Всем привет!

Хочу представить вам мой небольшой проект, над которым я тружусь в свободное время уже более полугода. Это игра, которая называется Great Permutator.

Почему здесь? Дело в том, что данная игра представляет собой головоломку особого жанра, так называемого engineering puzzle. Примеры игр такого жанра: LightBot, Manufactoria, The Codex of Alchemical Engineering и, конечно же, SpaceChem. Мне такие игры очень нравятся и, вроде бы, нравятся многим программистам.

На самом деле первоначальная версия этой статьи была подготовлена для Хабра. Но я по глупости опубликовал ее не в тот хаб и меня забанили. Когда разбанят (и разбанят ли) — непонятно, поэтому публикую здесь.

Чтобы было интереснее, я расскажу некоторые моменты о том, как создавалась эта игра. Такое повествование еще называют постмортемом, но здесь это слово, наверно, будет не совсем уместно.

250A - Бумажная работа. Будем действовать жадно — а именно, формировать каждую следующую папку с бумагами так, чтобы она включала в себя как можно больше бумаг. Закончить формирование папку следует сразу же перед 3м убыточным листом, или же при достижении конца массива. Несложно доказать, что такая стратегия оптимальна. Итого решение за O(n).

Автор — MikeMirzayanov

.

Adiv2. Рассмотрим массив A целых чисел от 1 до nk. Удалим из него все числа a_i, а все, что осталось, запишем в массив B. Массив B будет состоять из (n - 1)k элементов. Теперь для i-го ребенка следует вывести числа a_i, B[(n - 1) * (i - 1) + 1], B[(n - 1) * (i - 1) + 2], ... B[(n - 1) * (i - 1) + n - 1] (индексация B начинается с 1).

Автор — Gerald

Всем привет!

Это 150й (юбилейный?) раунд на Codeforces. Для 1го и 2го дивизионов.

Раунд готовили: Ripatti , Gerald , Delinur .

Enjoy!

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

UPD2. Контест окончен. Читеры удалены. Рейтинги пересчитаны.

Победители в дивизионе 1:
1. scottai1
2. vepifanov
3. rng_58
4. Egor
5. Komaki

Победители дивизиона 2:
1. mochavic
2. hanamaki
3. mfv
4. shef_2318
5. TangJie

Всем спасибо за участие. Приходите еще.

Разбор задач будет завтра.

UPD3. Разбор

A. Будем идти сверху вниз и восстанавливать ответ. Нижнюю грань 1й кости восстановить легко. Далее по двум граням 2й кости можно установить какая пара чисел должна быть на верхней и нижней грани. Если одно из чисел совпадает с числов на нижней грани 1й кости, то 2я кость восстанавливается однозначно, и так далее. Если мы смогли восстановить все кости — выводим YES. Если где то возникла неоднозначность, то можно показать, что эта однозначность будет сохраняться и для всех последующих костей. То есть получится хотя бы 2 разничных ответа, поэтому нужно выводить NO.

Автор — Ripatti .

B. Сначала сгенерируем все числа k-боначчи, не превышающие n. Для k ≤ 32 это можно сделать в лоб, а для больших k можно заметить, что числа k-боначчи до 10⁹ являются только степени двойки (и еще 0). Итого получим не более 100 чисел.

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

Почему все полученные числа будут различны? Вот одно из возможных доказательств:

F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k)

F(k, n - 1) = F(k, n - 2) + F(k, n - 3) + ... + F(k, n - k - 1)

Вычтеми из 1го равенства 2е и получим F(k, n) + F(k, n - k - 1) = 2F(k, n - 1), то есть 2F(k, n - 1) ≥ F(k, n). Это неравенство так же справедливо и для n ≤ k.

теперь предположим, что жадный алгоритм даст 2 одинаковых числа F(k, x) в разложении. Но тогда, в силу неравенства, мы должны были взять число F(k, x + 1). Противоречие.

Впрочем, доказывать это не требовалось, можно было просто поверить что жадность пройдет:)

Авторы — Gerald , Ripatti .

C. Сначала посчитаем число белых и черных пикселов в каждом столбике. После этого посчитаем сумму черных и белых пикселов на каждом префиксе в последовательности столбиков. Это позволит нам за O(1) вычислять количество черных и белых пикселов на любом отрезке столбиков.

Далее воспользуемся динамическим программированием. dp[i][j] будет хранить наименьшее число перекрашиваемых пикселов на префиксе от 1го столбика до j-го, причем цвет последней полосы будет белым для i = 0 и черным для i = 1.

Далее dp пересчитывается следующим образом: dp[0][0] = dp[1][0] = 0

Ответом будет min(dp[0][m], dp[1][m]).

Итого решение за O(nm + m * (y - x)).

Автор — Ripatti .

D. Обычный поиск в ширину. Состояние — положение головы + маска, которая задает положение хвоста, а именно: двумя битами кодируется относительное положение каждого сегмента (кроме головы) относительно предыдущего. Итого в маске максимум 16 бит, оценка на общее число состояний — 4⁸ × 15 × 15 (на самом деле можно даже показать оценку порядка 3⁸ × 15 × 15).

Далее нужно просто все очень аккуратно реализовать.

Автор — Ripatti .

E. Дано: z = [x / 2] + y + xy. Это равносильно

z = [2k / 2] + y + 2ky, где x = 2k, k > 0
или
z = [(2k + 1) / 2] + y + (2k + 1)y, где x = 2k + 1, k ≥ 0.

Преобразуем:

z = k + y + 2ky, k > 0
или
z = k + y + (2k + 1)y, k ≥ 0.

Еще пару шагов:

2z + 1 = 2k + 2y + 4ky + 1, k > 0
или
z + 1 = k + 2y + 2ky + 1, k ≥ 0.

2z + 1 = (2k + 1)(2y + 1), k > 0
или
z + 1 = (2y + 1)(k + 1), k ≥ 0.

Из второго уравнения видно, что z должно быть вида 2^t - 1, иначе z + 1 имеет нечетный делитель и мы можем подобрать решение. Из первого же уравнения получаем, что 2^t + 1 - 1 должно быть простым, иначе опять можно подобрать решение. Если же z = 2^t - 1, а 2^t + 1 - 1 — простое, то очевидно, что уравнение неразрешимо.

Простые числа вида 2^a - 1 являются простыми числами Мерсенна, на данный момент найдено всего 46 чисел такого вида. Показатели степени для первых 40 из них можно найти, например, здесь.

Автор — Ripatti .

Привет всем!

Это 139 раунд на Codeforces специально для 2го дивизиона. Участники из 1го дивизиона могут принять в нем участие вне конкурса.

Раунд готовили Ripatti , Gerald , Delinur.

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

Удачи!

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

UPD2. Тестирование завершено. Победители:
1. wccy
2. ttl
3. shubhanshu
4. Atarashi_Ako
5. dvylfz921

2 участника решили все предложенные задачи.

Разбор.

A. Для решения задачи можно было вывести одни из следующих формул:
res = abc - (a - 1)(b - 1)(c - 1), res = ab + bc + ca - a - b - c + 1, или какую любо аналогичную.
Кроме того, задачу можно было решить за O(a + b + c) — аккуратно спускаться от верхнего слоя к нижнему и суммировать общее число плиток.

Автор — Ripatti .

B. Студентов можно представить вершинами некоторого графа, а отношения — ребрами в этом графе. Нам нужно выкинуть как можно меньше вершин, после чего покрасить вершины в 2 цвета так, чтобы любое ребро соединло вершины различных цветов, а вершин разных цветов было поровну.

Нетрудно понять, что граф состоит из цепочек, циклов и отдельных вершин. Каждую из этих компонент можно легко покрасить нужным образом в 2 цвета, кроме одного случая: циклы нечетной длины. Таким образом, для решения задачи необходимо выкинуть по 1 вершине из каждого нечетного цикла. После данной операции у нас может остаться нечетное число вершин — тогда выкинем еще одну. В итоге получим граф из четного числа вершин, состоящий из цепочек, четных циклов и отдельных вершин. Такой граф легко раскрасить нужным способом.

Авторы — Gerald , Ripatti .

С. Первое решение: разбор случаев.
1. k = 1. Здесь для n ≤ m + 1 нужно 3 сотрудника, а для n > m + 1 — 2 сотрудника, кроме одного хитрого случая: для n = 2, m = 2, k = 1 ответ 4.
2. k > 1. Для n = m ответ 2k + 1, для всех остальных случаев ответ 2k.
Во всех случаях легко построить сами решения, а так же вручную доказать их корректность.

Второе решение: жадность.
Заведем массив достаточно большого размера, в котором будем хранить текущее число работников в каждый из первых несколько дней. Теперь просто будем идти по нему слева направо от 1го для до n + m-го и нанимать работников так, чтобы все было хорошо. А именно: нанимаем работника если в текущий день персонала меньше k или же если в следующий день персонала 0 человек (этот работник нужен чтобы передать ключ).
Можно показать, что это решение работает за O((n + m)k).
Это решение так же работает и для случаев n < m, но за более большую асимптитику.

Авторы — Gerald , Ripatti .

D. Для каждого сектора отсортируем все перемычки по расстоянию от центра паутины. Теперь для каждого сектора при помощи трех указателей (один для данного сектора, 2 для соседних) посчитаем число плохих ячеек. Собственно, все. Главное не запутаться.

Решение за , где m — общее число перемычек.

Автор — Ripatti .

E. Цифровой корень почти всегда равен самому числу по модулю k - 1. Единственное расхождение для цифровых корней 0 и k - 1 — для них обоих число по модулю k - 1 будет 0. Но цифровой корень 0 мы можем получить только из числа вида 00...00, количество которых можно посчитать отдельно. Отсюда легко понять как вычислить количество подстрок с нужным цифровым корнем, зная число подстрок, равных по модулю некоторому числу.

Теперь давайте поймем как получить число подстрок нужного модуля. Будем идти по строке слева направо и поддерживать для каждого модуля количество префиксов с таким модулем в массиве dp[] размера k. Пусть текущая позиция i. Тогда число подстрок с модулем b, оканчивающихся в позиции i, равно числу префиксов левее позиции i с модулем (x - b)mod(k - 1), где x — модуль подстроки s[1... i]. Т.е. просто dp[(x - b)mod(k - 1)].

Чтобы это решение прошло по времени, массив dp[] следует заменить на какой нибудь ассоциативный массив. Например, на std::map в языке С++ или на хэштаблицу.

Итого решение за O(nz), где z — сложность доступа к массиву ( для std::map или O(1) для хэштаблицы).

Автор — Ripatti.

Всем привет.

Это очередной 133й раунд Codeforces. Специально для 2го дивизиона, участники 1го дивизиона могут принять участие вне конкурса.

Раунд готовили Ripatti , Gerald , Aksenov239 , Delinur и MikeMirzayanov .

Раунд будет с динамической системой оценки задач. Задачи будут расположены в случайном порядке (см UPD1). Чтобы раунд был для вас максимально интересным, пожалуйста, прочитайте условия всех задач.

Удачи!

UPD1. Члены жюри посовещались и решили расположить задачи в предполагаемом порядке увеличения сложности.

UPD2. Контест окончен. Победители:
1. karensun522
2. stostap
3. sisterX
4. BiliBili
решили все 5 предложенных задач. Ура!

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

Div2 A. Для решения данной задачи достаточно вывести "0 0 n".

Автор задачи — Alex_KPR

Привет всем!

Сегодня очередной раунд на Codeforces, вот уже 5³-ый.
Раунд будет проходить для обоих дивизионов по классическим правилам формата Codeforces.

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

В подготовке контеста участвовали Ripatti , Alex_KPR , Gerald , Aksenov239 , RAD , Delinur .

Всем удачи!

UPD. Раунд окончен.
Победители div1:
1. Petr
2. tourist
3. SergeyRogulenko
4. bmerry
5. UESTC_Nocturne

Победители div2:
1. gflegar
2. mylyanyk.ivan
3. arbesfeld

Petr — единственный в первом дивизионе, решивший все 5 задач. Во втором дивизионе 5 задач не решил никто.

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

A div2. Искомая строка — та, на которой звездочка встретилась ровно один раз, искомый столбец — тот, где звездочка встретилась только однажды. Перебрав все строки/столбцы и проверив количество звездочек в них, получаем ответ.

Авторы: MikeMirzayanov, Gerald

Всем привет!

Сегодня будет проходить второй раунд Открытого чемпионата Москвы и МО по программированию (КРОК). Начало запланировано на 19:00.

Соревнование будет проходить по обычным правилам Codeforces, со взломами и падением баллов со временем. В Раунд 2 допускаются все участники, набравшие в Раунде 1 баллов не меньше участника на 300-ом месте. Все остальные участники могут участвовать в раунде вне конкурса. Специально для участников второго дивизиона подготовлена облегченная версия набора задач. Наборы задач официальной и неофициальной версий раундов частично пересекаются.

Контест будет рейтинговым для всех участников.

Вас ждет несколько задач, упорядоченных примерно по возрастанию сложности. Разбалловка задач как для первого, так и второго дивизиона стандартная (500-1000-1500-2000-2500). Не забывайте, что во время контеста решения будут тестироваться на небольшом наборе претестов. Тестирование на полном наборе тестов будет произведено после окончания раунда. Набор претестов не всегда покрывает все возможные случаи входных данных, поэтому внимательно тестируйте свои решения.

До окончания раунда категорически запрещается публиковать условия/решения задач. Запрещено общаться по теме задач, обсуждать какие либо мысли о возможном их решении. Давайте будем честными! Обсуждать задачи можно после окончания раунда.

В финальный раунд проходит 50 участников, показавших наилучший результат. Все участники, набравшие столько же баллов, сколько и участник на 50-ом месте, также проходят в финал.

Раунд готовили: Ripatti, havaliza, Gerald, RAD, MikeMirzayanov, Delinur.

Всем удачи!

UPD. Напоминаем, что 27 апреля в офисе компании КРОК состоится финал Открытого чемпионата Москвы и МО по программированию (КРОК). Обратите внимание, что компания КРОК не оплачивает дорогу и проживание участников финала. Все участники финала должны прибыть в офис компании КРОК (г. Москва) утром 27 апреля.

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

Рекомендуется заполнить форму независимо от ваших результатов в Раунде 2, поскольку отказаться может достаточно большое количество участников.

A. Решение в лоб за O(n) (моделирование всех n раундов) получает TL. Ускорим наивное решение — рассмотрим раунды на отрезках [1..mk], [mk+1..2mk], [2mk+1..3mk] и так далее. Нетрудно заметить, что результаты раундов на этих отрезках будут повторяться. Поэтому промоделируем только один из этих отрезков, а затем учтем его [n/(mk)] раз ([x] — деление нацело). Остаточек из n%(mk) последних раундов промоделируем отдельно. Итого получаем решение за O(mk), которое легко проходит по времени.

Авторы — Ripatti и Gerald

div2 A. В этой задаче нужно было найти длину ломаной, умножить ее на k / 50 и вывести что получилось. Длина ломанной --- сумма длин всех ее звеньев. Длина каждого звена считается по теореме Пифагора: .

Привет всем!

Рад приветствовать вас на очередном раунде Codeforces. Надеюсь, что недавняя цветовая революция и несколько более позднее время проведения раунда внесут некоторое разнообразие в процесс решения задач:)

Автором задач сегодняшнего раунда являюсь я. Раунд помогал готовить RAD, на английский язык задачи перевела Delinur.

Всем удачи.

UPD.

Раунд окончен, рейтинги пересчитаны.

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

1. Egor

2. tourist

3. unicef

4. sevenkplus

5. ivan.popelyshev

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

1. RainbowDash

2. cjtoribio

3. miraliv

4. adrian.jaskolka

5. majia5

Ура!

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

Сайт Ала Циммерманна вот уже долгое время лежит. Постоянные участники соревнований этого сайта долго ждали когда он вернется к рабочему состоянию и так и не дождались. Поэтому они создали свой собственный сайт и запустили свой контест в стиле azspcs с блэкджеком и студентками. Победитель получит ааавтомобиииль! футболку с логотипом ISS. Подробности по ссылке.

A. (ссылка) Решение этой задачи описано в четвертом абзаце условия. Его надо было внимательно прочитать и реализовать. Единственная сложность которая могла возникнуть - как опередить какое достоинство старше. Для этого можно было двумя проходами по массиву [ '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A' ] определить номера достоинств карт в массиве, а полученные числа сравнить.

Добрый вечер.

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

Раунд мне помогали готовить RAD, Connector, it4.kp, а также MikeMirzayanov. На английский язык условия перевела Delinur.

На этот раз контест будет проходить в старых добрых традициях Codeforces. Никаких нововведений, в меру короткие и понятные условия.

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

Всем удачи!

UPD. Раунд завершен, рейтинги обновлены.

Победители:

1. tsundere

2. jte

3. abacadaea

4. ltaravilse

5. Billy_Herrington

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

A. (ссылка) В этой задаче нужно было сделать то, что было написано в условии. А именно: считать все имеющиеся навыки, затем степень их владения домножить на коэффициент k, после этого выкинуть все навыки, степень владения которых меньше 100. Далее нужно было добавить новые навыки (то только те, которых еще нет в списке). Полученный список отсортировать и вывести.

Привет всем!

Я автор задач сегодняшнего раунда. Контест помогали готовить RAD, Connector, it4.kp. На английския язык условия перевела Delinur.

Этот контест будет тематическим. И тема контеста - Disgaea.

Этна, Лахарл и Флонн - главные персонажи игры

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

Однако наивное решение не проходит по времени.

Авторское решение предполагает ускорение наивного решения при помощи битовых масок.

A div2. В этой задаче можно было промоделировать весь процесс. А именно - рассматривать все минуты подряд и, в зависимости от того, какого цвета в данную минуту подошла кабинка, уменьшать соответствующую группу студентов G на min(|G|, 2), где |G| - размер группы. После этого нужно определить самую первую по счету минуту t, в которую все три группы опустеют. Тогда t + 30 будет ответом. Это решение за O(r + g + b).

Привет всем!

Я автор задач сегодняшнего раунда. Раунд будет проходить сразу в двух дивизионах. Всего будет 7 задач, первые 5 из которых будут для второго дивизиона, а последние 5 - для первого.

О разбалловке. Сегодня она будет не совсем стандартная, а именно:
для див2: 500-1000-1500-2000-2000
для див1: 500-1000-1000-1500-2500
Так что будьте внимательны.

Раунд помогал готовить RAD. На английский язык задачи перевела Delinur.

Всем удачи и приятного времяпровождения.

A. Нужно было три раза подсчитать количество гласных букв в трех строках. Затем сравнить то, что получилось, с числами 5, 7 и 5. Если все совпало - вывести YES, иначе вывести NO.

Автор задачи - Ripatti.