Доброго времени дня сообщество Codeforces. В этом посте я хочу извинится за задачу div2C/div1A. Дело в том, что я очень долго ждал этого раунда, а заявку отправил 20 декабря прошлого года. Утверждение на раунд я получил только 2 недель назад, но некоторые задачи были сняты и надо было их менять. Тогда меня в голову пришла задача div2B (эта идею пришла из известной шутки "жители Ленинграда, переедавшие в Москву увеличивают средний IQ обеих столиц), а для div1A ничего нового не мог придумать и вспомнил о старой задаче, который у меня был в готовым виде и я давно снял с SPOJа. Оказалось, что он снят, но можно найти по ссылке. Прощу прощения у сообщества и надеюсь, что решая мои остальные задачи каждый что-то для себя нашел.

735A - Остап и Кузнечик

Задача на технику программирования. Надо найти на каких позициях находятся кузнечик и насекомое. Если разность позиций не делится на k, то ответ — NO. В обратном случаи надо проверять позиции pos+k, pos+2k, ... , где pos — это минимальная из позиций кузнечика и насекомого. Если где-то есть препятствие, то ответ — NO, в обратном случаи — YES.

735B - Урбанизация

Во первых, надо заметить, что n1+n2 "избранные" должны быть люди с top (n1+n2) коэффициентами. Во вторых, если человек с интеллектом C будет в первом городе, то он будет добавить к суммарному коэффициенту IQ C/n1 баллов. Так что, если n1<n2, то top-n1 рейтингов надо "запихнуть" в маленький город, а из остальных top-n2 — в большой.

736A - Теннисный Чемпионат

Давайте решать обратную задачу: сколько участников как минимум должен участвовать, если чемпион будет провести ровно n матчей. Тогда очевидно есть такая рекуррентая связь: f(n+1)=f(n)+f(n-1) (Сделаем сетку так, чтобы тот, кто победил в последнем матче до этого играл n матчей, а тот кто проиграл — сыграл (n-1) матчей). Значит, задача сводится к тому, чтобы найти индекс наибольшего числа Фибуначчи, не превосходящую число, данное в вводе.

736B - Налоги

Первый очевидный факт — для простых чисел ответ — 1 (Этот случай надо проифать в первую очередь). Если число не простое — то ответ по крайней мере — 2. А когда это возможно? Это возможно в двух случаях — когда число сумма двух простых или самый большой делитель числа — 2. Но если 2 делитель, то и n/2 тоже делитель отличные от n (n/2<=2 => n<=4 => n=4 — n не простое). По Гипотезе Гольбаха, которое проверено для чисел не превосходящих 10^9, каждое четное число является суммой двух простых чисел. А нечетное число может быть суммой двух простых чисел, если оно имеет вид 2+p, где p — простое. В обратное случаи, ответ равен — 3 (n=3+(n-3), (n-3) является суммой двух простых, так как оно четное).

736C - Остап и дерево

Во-первых хочу сказать спасибо albert96 и GlebsHP за то, что помогли с разбором. Во-вторых, хочу извиниться за опоздан ие.

Задача решается методом динамического программирования. Пусть dp[v][i][j] будет количество покрасить поддерево вершины v так, чтобы ближайшая черная вершина была на глубине i, а ближайшая белая — на глубине j (еще и смотрим dp[v][-1][j] и dp[v][i][-1] — случаи где нету черных и белых вершин в диапазоне k в поддереве v соответственно). Чтобы объединить две поддеревья, надо перебирать все пары (i,j) в обеих поддеревьев. Пусть имеем пары (a,c) в первом поддереве и (b,d) — во втором. Если min(a,c)+max(b,d)<=k, то обновляем значение в нынешней вершине.

Сложность алгоритма O(n*k^4), что вполне достаточно для данной задачи (n — количество вершин, k^4 перебор всех пар (a,b); (c,d))

736D - Перестановки

Эта задача состоит из трех идей. Идея 1: четность этого количества равна четности определителю матрицы, которая имеет 1 в позициях (ai,bi) и 0 — в других позициях (это — согласно определению). Идея 2: Если заменить одну единицу на нолик, но определитель будет меняться на величину, равную к алгебраического дополнения. То есть, если мы будем считать обратную матрицу то она будет отражать четности дополнений (B(m,n)=A'(n,m)/detA, мы знаем, что detA — нечетное). Идея 3: обратную матрицу можно найти за O(n^3), что медленно. Для этого мы будем перейти в алгебру по модулю 2, где мы умеем складывать числа с помощью XOR. Для этого мы в одном переменном храним не одно число а 32 — каждый бит один переменный. Тогда наша асимптотика будет O(n^3/32), что вполне нормально.

736E - Чемпионат

Допустим у нас есть множество (a1,a2,...,am) (уже дополненный список в неубывающем порядке). Тогда — оно является валидным, если множество {2m-2, 2m-4, 2m-6, ..., 0} мажорирует
множество {a1,a2,...,am}. Необходимость: top-n (n<=m) участников между собой играют n(n-1)/2 партий, в котором суммарно собирают 2 балла. В матчах с остальными они суммарно могут набирать 2*n(m-n) баллов (всего игр верхней части против нижней части 2n(m-n)). То есть баллов у них вместе взято будет не больше чем 2*(n(n-1)/2+n(m-n))=2*((m-1)+(m-2)+...+(m-n)) (легко проверить). Достаточность, конструкция примера: Давайте решим как играл чемпион, а потом опустим рекурсию (математически применяем метод математической индукции). Если количество баллов у чемпиона четно (например 2*(m-n) то мы допускаем, что он проиграл у участников занявшие места 2,3,4,...,n и выиграл у остальных). Если у чемпиона количество баллов нечетно (2*(m-n)-1, для некоторого n), то тогда мы предполагаем то же самое, только предполагая, что он играл вничью с (n+1)-ым. Легко проверять, что мажорация сохранится, то есть мы и в конце будем (в случаи n=1) будем иметь множество которая мажорируется множеством {0}, то есть {0} и задача будет решена. То есть алгоритм такой: Сначала доводим наше множество из n элементов к множеству из m элементов. Если это невозможно, то ответ — NO. В обратном случаи — ответ YES и надо конструктировать пример как описано. Асимптотика: O(m^2logm) (m раз мы вызываем рекурсию, каждый раз сортируем (это нам нужна потому что мы можем менять очередь из-за того, что результат игрока первого места может влиять на последовательность),и проходим на него линейно).

Доброго времени дня, сообщество Codeforces! С радостью объявляю, что 27 ноября в 19:35 по Москве состоится Codeforces Round #382 для участников из обоих дивизионов.

Автор этого раунда — я (albertg). Я из Армении, и пока единственный армянский автор раундов на данный момент. (Прошу прощения у Edvard) Этот раунд для меня является вторым и, надеюсь, не последним :) и последним. Как обычно, хочу сказать спасибо координатору Codeforces Глебу Евстропову (GlebsHP) за помощь при подготовке раунда, Михаилу Мирзаянову (MikeMirzayanov) за отличные платформы Codeforces и Polygon. Еще хочу благодарить super_azbuka за идею задачи.

Как обычно, участникам обоих дивизионов будет предоставлено 5 задач и 2 часа на сдачу решений. В этом раунде мы поможем Остапу Ибрагимовичу Бендеру добраться до Рио-де-Жанейро. Желаю всем удачи и удовольствия. Разбалловка будет объявлена незадолго до начала соревнования!

UPD1: Господа присяжные, заседание начинается! Разбалловка в div1 750-750-1500-2000-2500, в div2 500-1000-1750-1750-2500.

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

UPD3: Если у кого-то вопросы по решениям задач (хотя это видимо мало кого интересует) пишите, пожалуйста мне лично. Буду отвечать.

UPD4: Прошу читать этот пост

UPD5: Опубликован разбор задачи div2E/div1C.

493A - Вася и футбол

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

493B - Вася и борьба

Надо делать то, что сказано в условии. Хранить двe vector-ы, в одном из них очки первого борца, а во втором — очки второго. Еще две переменные — в первом сумма всех очков, что дано в вводе, а во втором — кто выполнил последний прием. Если Sum всех не 0, то выводить номер борца, иначе пройти над векторами и проверить — имеются ли неравные элементы. При равенстве выводить ответ зависимо от того, кто выполнял последний прием.

493C - Вася и баскетбол

Храним один большой массив pair-ов — дистанция бросков и кто это выполнил. Сортируем весь этот массив, потом предлагаем, что все броски — трехочковые. Потом пройдем над массивом, и зависимо от второго элемента на одно уменьшаем наши очки на единицу и сравниваем с наилучшим ответом и при необходимости меняем. В самом конце выводим ответ.

493D - Вася и шахматы

Заметим, что если n — нечетное, то черные могут сделать симметричные шаги относительно центральной линии — победив таким образом. А если n — четное, то белые могут ставить ферзь на поле (1;2) (что лексикографически наименьший возможный ход), никогда не входить в первую строку, и победить.

493E - Вася и многочлен

Рассмотрим две случая. 1) t!=1 и 2) t=1.

1) Если наша функция — разная от константа, то а больше всех коэффициентов, и в ответ может быть только представление числа b в а-ичной системе счисления. Еще и надо проверить — является ли константа решением?

2) при t=1 надо быть осторожнее:

при 1 1 1: ответ inf,

при 1 1 n: ответ 0

при 1 а, а^x(x-натуральное): ответ 1

при других случаях P(1) больше всех коэффициентов.

Здравствуйте!

Третьего декабря, в 18:00 по Москве состоится Codeforces Round #281 для Див. 2 участников. Традиционно Див. 1 участники могут участвовать вне конкурса.

Это мой первый Codeforces Round и надеюсь, что не последний :)

Большое спасибо Максиму Ахмедову (Zlobober) за помощь при подготовке раунда и MikeMirzayanov-у за платформы Codeforces и Polygon.

UPD1: Разбалловка будет динамической.

UPD2: Контест завершен. Спасибо всем, кто участвовал. Надеюсь, что контест всем нравилось.

UPD3: Разбор задач

UPD4: Top-5 участники. Поздравляю

1. ShiXingxing15

2. ganar27

3. Tim_LinYd

4. coolwyj

5. gaoyihan

Еще раз поздравляю gaoyihan — он единственный, кто решил задачу Е.

UPD5: Статистика взломов