Привет, Codeforces!

25 декабря 2015 года в 18:00 MSK состоится четвертый учебный раунд Educational Codeforces Round 4 для участников из первого и второго дивизионов. С прошлого учебного раунда в этот раз прошло всего ничего. Несмотря на то, что проведение раунда мы спланировали ещё в понедельник, мы почему-то забыли включить его в расписание, поэтому в расписании раунд только появился. Таким образом, это уже четвертый и последний в этом году учебный раунд.

<Эти два абзаца может быть никогда не изменятся>

О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.

Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.

</Эти два абзаца может быть никогда не изменятся>

Подготовкой задач в этот раз занимался только я (Эдвард Давтян). Пока благодарю, только MikeMirzayanov мы вместе придумывали задачи. Через некоторое время здесь появится благодарность тестеру. Также заранее благодарю Машу Белову Delinur, которая вычитает английские тексты условий, когда они появятся :-)

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

Поздравляю всех с наступающим новым годом!!!

Good luck and have fun!

UPD 1: Первая фаза соревнования закончена, ломайте решения соперников!

UPD 2: Опубликован полный разбор задач.

Этот раунд был немного необычным: некоторые из задач были ранее подготовлены студентами и сотрудниками Саратовского ГУ для прошедших олимпиад, одна из задач была подготовлена участником dalex для одного из регулярных (неучебных) раундов Codeforces, но не использована там.

609A - USB Flash Drives

Отсортируем массив по невозрастанию. Тогда ответом на задачу будет несколько первых флешек. Будем идти по массиву слева направо пока не наберем сумму m. Количество взятых элементов и будет ответом на задачу.

Асимптотическая сложность решения: O(nlogn).

609B - The Best Gift

Пусть cnt_i — количество книг i-го жанра. Тогда ответом на задачу будет величина равная . В первой сумме мы считаем непосредственно количество хороших пар книг, а во втором из общего количества пар книг вычитаем количество плохих пар.

Асимптотическая сложность решения: O(n + m²) или O(n + m).

609C - Load Balancing

Пусть s — сумма элементов массива. Если число s делится на n, то сбалансированный массив будет состоять из n чисел . В этом случае разность между минимальным и максимальным будет равна 0. Легко видеть, что в любом другом случае ответ будет больше 0. С другой стороны массив, состоящий из чисел и чисел является сбалансированным с разницей минимального и максимального равной 1. Обозначим этот сбалансированный массив b. Чтобы получить массив b давайте сначала отсортируем массив a по невозрастанию, а после этого попарно сопоставим элементы массивов a, b друг другу. Таким образом некоторые числа в a придется увеличить до соответствующих чисел в b, а некоторые уменьшить. Поскольку за одну операцию мы сразу уменьшаем где-то значение, а где-то увеличиваем, то ответ равен .

Асимптотическая сложность решения: O(nlogn).

609D - Gadgets for dollars and pounds

Заметим, что если Нура может купить k гаджетов за x дней то за x + 1 день она тоже сможет их купить. Таким образом, функция возможности покупки является монотонной. Значит, мы можем найти минимальный день с помощью бинарного поиска. Пусть lf = 0 — левая граница бинарного поиска, а rg = n + 1 — правая. Будем поддерживать инвариант, что в левой границе мы не можем купить k гаджетов, а в правой можем (будем считать, что в n + 1 день мы гаджеты стоят 0). Теперь зафиксируем некоторый день d и поймем можем ли мы купить k гаджетов за d дней. Введем функцию f(d), которая равна 1, если мы можем купить k гаджетов за d дней и 0 в противном случае. Каждый раз в качестве d будем выбирать значение . Если f(d) = 1, то нужно двигать правую границу бинарного поиска rg = d, иначе левую lf = d. По завершении бинарного поиска нужно проверить если lf = n + 1, то ответ  - 1, иначе ответ равен lf. Для вычисления функции f(d) предварительно образуем 2 массива стоимостей гаджетов, продающихся за доллары и фунты, и отсортируем их. Теперь заметим, что мы можем покупать гаджеты за доллары в день i ≤ d когда доллар стоит меньше всего и день j ≤ d, когда фунт стоит меньше всего. Пусть теперь мы хотим купить x гаджетов за доллары и соответственно k - x за фунты. Конечно мы будем покупать самые дешевые из них (для этого мы и отсортировали заранее массивы). Будем перебирать x от 0 до k и одновременно поддерживать сумму стоимостей долларовых гаджетов s₁ и фунтовых s₂. Для x = 0 эту сумму легко посчитать за O(k), для всех остальных x эту сумму можно пересчитать за O(1) из суммы для x - 1 добавлением очередного долларового гаджета и выкидываением фунтового.

Асимптотическая сложность решения: O(klogn).

609E - Minimum spanning tree for each edge

Задача была предложена участником dalex.

Эта задача является очень стандартной задачей на знание минимальных покрывающих деревьев и умение построить некоторую структуру данных на дереве, для вычисления некоторой функции. Построим любое минимальное покрывающее дерево любым быстрым алгоритмом (например алгоритмом Краскала). Для всех ребер вошедших в MST мы уже нашли ответ — это просто вес MST. Теперь рассмотрим любое другое ребро (x, y). В MST существует единственный простой путь от вершины x к вершине y. Найдем на этом пути самое длинное ребро, выкинем его и добавим ребро (x, y). Согласно критерию Тарьяна, получившееся дерево является минимальным покрывающим, содержащим ребро (x, y) (это не является утверждением критерия Тарьяна, но из него следует).

Теперь рассмотрим техническую сторону решения. Для того, чтобы быстро находить самое длинное ребро на пути между двумя вершинами в дереве подвесим дерево за любую вершину (например за первую). Теперь обозначим l = lca(x, y) — наименьший общий предок вершин (x, y). lca(x, y) можно искать с помощью метода двоичного подъема, одновременно поддерживая самое тяжелое ребро.

Конечно такую задачу можно решать и более сложными структурами данных, например с помощью Heavy-light decomposition или Linkcut tree.

Асимптотическая сложность решения: O(mlogn).

609F - Frogs and mosquitoes

В этой задаче нужно было реализовать все, что написано в условии, но за хорошую асимпотику. Будем поддерживать множество пока не съеденных комаров (например с помощью set} в C++ или TreeSet в Java) и обрабатывать приземления комаров по очереди. Также будем поддерживать множество отрезков (a_i, b_i), где a_i — положение i-й лягушки, а b_i = a_i + l_i, где l_i — длина языка i-й лягушки. Пусть очередной комар приземлился в точке x. Выберем среди отрезков (a_i, b_i) отрезок с минимальным a_i таким, что b_i ≥ x. Если окажется, что a_i ≤ x, то этот отрезок и будет соответствовать лягушке, которая съест комара. Иначе комара никто не съест и его нужно добавить в множество несъеденных. Если комара съест i-я лягушка, то нужно удлинить её язык на размер комара и обновить отрезок (a_i, b_i) в структуре данных. После этого нужно в множестве несъеденных комаров брать ближайшего к лягушке справа и если возможно есть этого комара (это можно сделать с помощью например метода lower_bound в C++). Возможно лягушка сможет съесть несколько комаров, в этом случае их нужно по очереди есть.

Отрезки (a_i, b_i) можно хранить например в динамическом дереве отрезков по правому концу b_i, а значениями хранить a_i. Либо то же самое можно делать с помощью декартова дерева. Но это слишком сложно можно написать более простое решение. Будем хранить в обычном дереве отрезков для каждого левого конца a_i (левые концы не меняются никогда) правый конец b_i. Теперь можно например бинарным поиском найти минимальный префикс максимум на котором больше либо равен x. В этом случае получаем решение за O(nlog²n). Но это решение можно улучшить. Для этого нужно просто спускаться по дереву отрезков: если в левой половине максимум больше либо равен x идем влево иначе вправо.

Асимптотическая сложность решения: O((n + m)log(n + m)).

Code

Привет, Codeforces!

19 декабря 2015 года в 18:00 MSK состоится третий учебный раунд Educational Codeforces Round 3 для участников из первого и второго дивизионов. С прошлого учебного раунда прошло немало времени. В основном это связано с тем, что 6 декабря в Санкт-Петербурге состоялся NEERC и многие из вас (в том числе и я) в нём участвовали. Думаю дальше учебные раунды станут более частыми и регулярными.

<Эти два абзаца не менялись с прошлого раза>

О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.

Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.

</Эти два абзаца не менялись с прошлого раза>

Подготовкой задач в этот раз занимался не только я (Эдвард Давтян). Во-первых, большое спасибо Алексею Дергунову dalex, который поделился своей задачей, которую он раньше хотел дать на раунд, а она оказалась немного подбояненной. Во-вторых, хочу поблагодарить Александра Фролова fcspartakm RW, Виталия Кудасова kuviman АЁ и Артура Свечникова ikar за помощь в подготовке задач. Придумывать задачи нам помогал MikeMirzayanov. Также большое спасибо Маше Беловой Delinur, которая вычитывала мой RussianEnglish.

На сегодняшнем раунде вам будет предложено шесть задач. Надеюсь они вам понравятся.

Good luck and have fun!

UPD1: Первая часть соревнования завершена, надеюсь всем понравились задачи. Теперь можете ломать соперников :-)

UPD2: Разбор готов.

UPD3: Раунд закончился. Решения протестированы на дополненном наборе тестов. Результаты окончательные.

UPD4: 6725 rows affected :-)

600A - Выделение чисел

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

600B - Запросы о количестве не превосходящих элементов

Давайте отсортируем числа первого массива. Теперь будем идти по второму массиву и для текущего числа b_j найдем бинарным поиском индекс первого большего числа в первом массива. Этот индекс и будет являться ответом.

Другим подходом в этой задаче было следующее: отсортируем оба массива сохранив при этом индексы чисел (например можно сортировать пары <значение, позиция>). Теперь будем идти по второму массиву и хранить переменную p — указатель на первый элемент a_p такой, что он больше текущего b_j. Поскольку оба массива отсортированы указатель можно не сбрасывать на каждой итерации, а просто двигать его дальше вправо.

Асимптотическая сложность решения: O(nlogn).

600C - Сделай палиндром

Давайте посчитаем для каждого символа c сколько раз он встречается в s. Обозначим эту величину cnt_c. Рассмотрим нечетные cnt_c. В палиндроме нечетных cnt_c может быть не больше одного. Пусть a₁, a₂...a_k — это символы с нечетным cnt_c в алфавитном порядке. Заменим любой символ a_k символом a₁, символ a_k - 1 символом a₂ и так далее пока не дойдем середины. Теперь у нас имеется имеется не более одного нечетного символа. Если нечетный символ есть поставим его в середину ответа. А в первую половину возьмем от всех букв cnt_c / 2 в алфавитном порядке. Например, если s = aabcd мы сначала заменим d на b, после этого поставим символ c в середину и после перестановки остальных символов получим строку abcba.

Асимптотическая сложность решения: O(n).

600D - Площадь пересечения двух кругов

Давайте сразу отбросим случай когда круги не пересекаются, в это случае ответ равен 0. Это можно проверить в целых числах, сравнив квадрат расстояния между центра с квадратом суммы радиусов. Также отбросим случай, когда один круг полностью лежит внутри другого, в этом случае ответ есть площадь маленького круга. Это тоже можно проверить в целых числах, сравнив квадрат расстояния между центра с квадратом разности радиусов. Отлично теперь можно рассмотреть общий случай. Ответ будет складываться из некоторого сегмента первого круга и некоторого сегмента второго круга. Для того, чтобы определить угол первого сегмента рассмотрим треугольник, образованный центрами кругов и одной из точек пересечения. В этом треугольнике мы знаем все три стороны, значит по теореме косинусов может определить угол сегмента. Значит мы можем определить площадь сектора. Теперь остается вычесть из этого площадь треугольника образованного одним из центров и точками пересечения кругов. А это можно сделать, посчитав площадь как половина модуля псевдовекторного произведения. Таким образом получаются следующие формулы: ,

где d — расстояние между центрами. И соответственно тоже самое нужно сделать для первого круга, поменяв индексы 1 ≤ ftrightarrow2.

Асимптотическая сложность решения: O(1).

600E - Lomsat gelral

Название этой задачи является анаграммой к Small to large. И это не спроста :-) Авторское решение по этой задаче использует классическую технику пересчета множеств на дереве. Простейшим решением этой задачи является следующее: давайте для каждой вершины поддерживать один map<int, int> — для каждого цвета, сколько раз он встречается, один set<pair<int, int>> — пары количество повторений и цвет, и число sum являющееся суммой самых частых символов. Для того, чтобы посчитать эти величины для вершины v нужно сначала посчитать их для всех сыновей, а потом просто сливать эти значения. Такой подход правильный, но медленный (сложность получится O(n²logn)). Но давайте немного улучшим это решение, каждый раз когда нам надо склеить 2 map-а a и b, будем клеить меньший из них (просто итерируясь по нему) к большему (это и есть small to large). Давайте теперь рассмотрим цвет какой-нибудь вершины: каждый раз, когда он будет перекидываться из одного map-а в другой размер другого будет как минимум вдвое больше. Таким образом, это цвет поперебрасывается не более logn раз. Каждой перебрасывание делается за O(logn). Просуммировав это по всем вершинам получаем сложность O(nlog²n).

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

600F - Раскраска ребер двудольного графа

Введем обозначение d — наибольшая из степеней вершин в графе. Утверждение: ответ равен d. Докажем это утверждение, построив конструктивный алгоритм (он и будет решением задачи). Давайте красить ребра по очереди в любом порядке. Пусть текущее ребро (x, y). Если сейчас существует цвет c, который свободен и в вершине x и в вершине y, мы просто красим ребро в цвет c. Если такого цвета нет обязательно существует пара цветов c₁, c₂ такая, что c₁ есть в x но нет в y, а цвет c₂ есть в y но нет в x. Давайте освободим вершину y от цвета c₂. Рассмотрим другой конец ребра исходящего из вершины y цвета c₂. Пусть это вершина z. Если у вершины z цвет c₁ свободен мы можем покрасить ребра x, y в цвет c₂, а ребро y, z перекрасить в цвет c₁. Таким образом мы проведем чередование. Если же у вершины z цвет c₁ занят посмотрим на следующую вершину по цвету — w. Если это вершина не содержит ребра цвета c₂ мы снова можем провести чередование. И так далее. Поскольку граф двудольный мы обязательно сможем найти чередующуюся цепочку. Поиск цепочки можно сделать обходом в глубину. Длина цепочки порядка O(n). Поэтому окончательно имеем:

Сложность решения: O(nm).

Привет, Codeforces!

27 ноября 2015 года в 18:00 MSK состоится второй учебный раунд Educational Codeforces Round 2 для участников из первого и второго дивизионов.

О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.

Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.

Подготовкой раунда занимался я, Эдвард Давтян. Идеи задач были снова придуманы совместно с MikeMirzayanov.

На сегодняшнем раунде вам будет предложено шесть задач. Надеюсь они вам понравятся.

Good luck and have fun!

UPD: Большое спасибо PrinceOfPersia за тестирование задач, а также за Delinur за проверку моего плохого английского.

UPD2: Первая часть соревнования завершена, надеюсь всем понравились задачи. Теперь можете ломать соперников :-)

UPD3: На этапе взломов было выяснено, что верные решения многих участников оказались численно неустойчивы к большим ограничениям. В том, числе решения которые использовали тип double, а не long double ошибаются в ответе в девятом знаке. В связи с этим было принято решения ослабить требования на точность от 10^- 9 до 10^- 6. Вскоре все решения и взломы будут перетестированы. Это никак не повлияет на правильные решения они как и раньше будут получать Accepted.

UPD4: Разбор готов.

UPD5: Раунд закончился. Решения протестированы на дополненном наборе тестов. Результаты окончательные.

Привет, Codeforces!

13 ноября 2015 года в 18:00 MSK состоится первый учебный раунд Educational Codeforces Round #1 для участников из первого и второго дивизионов.

Учебные раунды Codefores — это новый формат соревнований основной целью, которого является помощь в развитии у участников базовых (и не только) навыков и знаний, которые необходимы при решении олимпиадных задач по программированию. В учебных раундах вы встретите не только старые добрые идеи и алгоритмы, которые многие знают, но также и некоторые расширенные темы, которые неизвестны многим участникам, в том числе и из первого дивизиона. Сложность задач будет сравнима с обычными раундами для участников из второго дивизиона, хотя многое может пригодиться и участникам из первого дивизиона. На мой взгляд первый раунд получился несколько проще того на что мы ориентировались.

Учебные раунды будут нерейтинговыми (мы продолжаем обсуждать этот вопрос). Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест. Подробнее об учебных раундах написано здесь.

Подготовкой учебных раундов занимаюсь я, Эдвард Давтян из команды Saratov SU Daemons. Идеи задач были придуманы совместно с MikeMirzayanov. Спасибо моему сокоманднику danilka.pro за тестирование и вычитывание условий и MikeMirzayanov за системы Codeforces, Polygon и идею учебных раундов.

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

Good luck and have fun!

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

UPD2: Пожалуйста не используйте недетерменированные генераторы. Например не стоит писать в языке С++ srand(time(NULL)) и потом использовать функцию rand(). Ваш генератор должен всегда генерировать один и тот же тест.

586A - Alena's Schedule

Задачу подготовил adedalic.

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

586B - Laurenty and Shop

Задачу подготовил Oleg_Smirnov.

Назовем путь i-м (0 ≤ i ≤ n - 1), если мы, выходя из дома, сначала i раз идем налево, потом переходим проспект и снова n - 1 - i раз идем налево. Введем обозначение d_i — время, которое нам придется ждать на светофорах на i-м пути. Если рассмотреть путь из магазина домой с конца, то получится пути из дома в магазиг, поэтому искомый путь есть два разных пути из дома в магазин. Значит ответом на задачу является сумма наименьшего и второго по величине значения d_i. Значение d_i легко пересчитывается из значения d_i - 1, таким образом все d_i можно посчитать за один проход.

Асимптотическая сложность решения: O(n).

585A - Gennady the Dentist

Задачу подготовил Neon.

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

Асимптотическая сложность решения: O(n²).

585B - Phillip and Trains

Задачу подготовил IlyaLos.

В задаче требовалось просто промоделировать игру. Это можно сделать с помощью обхода в глубину, ширину или динамического программирования. Состоянием является пара чисел x, y — позиция Филиппа в туннеле, а значением или в зависимости от того, можем ли мы попасть из стартовой позиции в x, y. Положения поездов в каждый момент времени определяются однозначно.

Асимптотическая сложность решения: O(n).

585C - Alice, Bob, Oranges and Apples

Задачу подготовил Edvard.

Поймем для начала, что означает процесс описанный в условии. Если нарисовать дерево переходов по буквам и , то получится дерево Штерна-Броко. Пусть апельсины это значения знаменателя дроби, а яблоки — числителя. На каждом шагу у нас есть две дроби (изначально ) и мы заменяем либо первую дробь на их медианту, либо вторую. Таким образом, первая дробь есть первый предок влево от медианты, а вторая — первый предок вправо. Таким образом, искомый процесс это просто процесс поиска дроби в дереве Штерна-Броко, который завершается тем, что текущая медианта совпадает с дробью, которую мы ищем (момент окончания игры, описанный в условии). Значит, числа x, y заданные в условии это просто дробь, которую мы ищем. Отсюда следует, что ответа не существует, если x не взаимнопросто с y (поскольку таким дробей нет в дереве Штерна-Броко). Пусть теперь мы хотим найти дробь в дереве. Понятно, что если x > y, то мы сначала перейдем в правую ветку. Более того мы можем считать, что теперь ищем дробь и никуда не спускались. Если же x < y, то нам нужно спуситься в левую ветку и можно считать, что мы ищем дробь и пока никуда не спускались. Эти рассуждения легко формализовать, чтобы получить строгое доказательство. Таким образом, решение задачи сводится к выполнению алгоритма Евклида для пары чисел x, y. Как известно время работы алгоритма Евклида O(logn) (дольше всего алгоритм Евклида работает на двух последовательных числах Фибоначчи), значит длина ответа тоже растет как логарифм.

Асимптотическая сложность решения: O(logn).

585D - Lizard Era: Beginning

Задачу подготовил danilka.pro.

Для решения этой задачи воспользуемся приемом . А именно переберем для первых (первая половина) заданий с какими спутницами главный герой будет путешествовать. Пусть при этом симпатия первой спутницы оказалась равна a, второй — b, а третьей c. Пусть существует способ выбрать спутниц для последующих (вторая половина) заданий так и пусть симпатии при этом будут равны a', b', c'. Тогда, чтобы по всем заданиям суммы симпатий были одинаковы необходимо и достаточно, чтобы a - b = b' - a' и b - c = c' - b'. Теперь для решения задачи достаточно перебрать первую половину и сохранить в некоторой структуре данных тройки чисел a - b, b - c, a (третье число нужно для максимизации ответа в случае равенства). Далее нужно перебрать вторую половину и найти в структуре данных значения b' - a', c' - b', m, где m — максимальное третье значение которое есть в структуре данных. В качестве структуры данных можно использовать map < pair < int, int > , int >  в языке C++, первые два числа это значение a - b, b - c, а третье — максимальное a соответствующее первым двум. Также можно все тройки сложить в один большой массив, отсортировать его и бинарным поиском находить необходимые значения.

Асимптотическая сложность решения: , где logC — константа, появляющаяся вместе со структурой данных.

585E - Present for Vitalik the Philatelist

Задачу подготовил gridnevvvit.

Пусть мы хотим посчитать количество подмножеств с НОД равным 1 — число A. Посчитаем это количество с помощью формулы включений-исключений: сначала скажем, что все подмножества нам подходят. Таких подмножеств 2ⁿ. Теперь вычтем подмножества с НОД кратным 2. Количество таких множеств 2^cnt₂ - 1, где cnt_i — количество чисел, делящихся на i. Далее вычитаем 2^cnt₃ - 1. Подмножества с НОД кратным 4 мы учли вместе с двойкой. Далее вычитаем 2^cnt₅ - 1. Теперь заметим, что подмножества с НОД кратным 6 мы вычли уже дважды: сначала с двойкой, затем с тройкой, поэтому давайте прибавим количество таких подмножеств 2^cnt₆ - 1. Продолжая этот процесс получаем, что для числа d, к ответу нужно прибавить величину μ(d)(2^cnt_d - 1), где μ(d) равно 0, если d делится на полный квадрат, 1, если количество простых в факторизации d четно и  - 1 в противном случае. Значит числа, делящиеся на полный квадрат мы можем не суммировать, поскольку они входят с коэффициентом 0. Для подсчета значений cnt_i достаточно факторизовать все числа и для каждого за 2^k перебрать делитель, со значением μ(d) ≠ 0. Теперь легко понять, что количество подмножеств с НОД большим 1 равно B = 2ⁿ - A. Теперь для решения задачи давайте переберем марку, которую купит Виталик a_i. Пересчитаем число B так, как если бы числа a_i не было в множестве. Для этого нужно просто вычесть те слагаемые на которые повлияло число a_i. Это можно сделать за 2^k, где k — количество простых в факторизации числа a_i (снова нужно перебрать делители a_i со значением μ(d) ≠ 0). Теперь поймем какие подмножества дадут НОД равный 1 вместе с выбранной маркой. Понятно это те подмножества НОД которых больше 1, но при этом не делится ни на один делитель a_i. Для этого снова воспользуемся формулой включений-исключений. Для каждого делителя d числа a_i вычтем из B значение μ(d)(2^cnt_d - 1). Таким образом, мы получим количество способов B_i выбрать подмножество c НОД большим 1, но при это взаимнопростым с a_i. Ответом на задачу является сумма всех B_i. Наибольшее количество простых в факторизации числа не превосходящего 10⁷ равно 8. Факторизацию чисел можно выполнить с помощью линейного алгоритма поиска минимального делителя чисел от 1 до n, либо с помощью решета Эратосфена за время O(nloglogn).

Асимптотическая сложность решения: O(C + n2^K), где , а K — наибольшее количество простых в факторизации чисел a_i.

585F - Digits of Number Pi

Задачу подготовил Edvard.

Расмотрим все подстроки строки s длины . Сложим все эти строки в бор, посчитаем суффиксные ссылки и построим автомат по цифрам. Это можно сделать за линейное время с помощью алгоритма Ахо-Корасик. Теперь для решения задачи посчитаем динамику z_{i, v, b1, b2, b} в котором состояние описывается пятеркой чисел: i — количество цифр которые мы уже поставили в искомом числе, которое встречается , v — в какой вершине бора мы находимся, b₁ — равен ли префикс числа, которое мы набираем префиксу числа x, b₂ — равен ли префикс числа, которое мы набираем префиксу числа y, b — находится ли некоторая подстрока длина на уже набранном префиксе в боре (значения b₁, b₂, b — равны либо 0, либо 1). Значением динамики является количество способов набрать префикс с заданным набором свойств. Для того, чтобы сделать переход нужно перебрать цифру, проверить что мы не вышли за границы отрезка [x, y], перейти от вершины v к следующей вершине по автомату и заданной цифре. Ответом является сумма по всем v, b₁, b₂ z_{b, v, v1, v2, 1}.

Асимптотическая сложность решения: O(nd²).

Привет, Codeforces!

12 октября 2015 года в 12:00 MSK состоится очередной раунд Codeforces #325 для участников из первого и второго дивизионов. Обратите внимание на необычное время начала раунда!

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

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

Процесс подготовки задач был интересным: мы много раз переделывали условия, переписывали решения, добавляли тесты, изменяли ограничения, даже успели поменять полностью готовую задачу (пришлось останавливать конвейер типографии, который уже печатал условия :-)). Поблагодарим всех кто готовил, помогал готовить задачи, вычитывал условия, писал перекрестные решения: Адилбек adedalic Далабаев, Роман Roms Глазов, Владимир vovuh Петров, Олег Oleg_Smirnov Смирнов, Алексей Perforator Рипинен, Максим Neon Мещеряков, Илья IlyaLos Лось, Виталий gridnevvvit Гриднев, Данил danilka.pro Сагунов, Александр fcspartakm Фролов, Павел HolkinPV Холкин, Игорь Igor_Kudryashov Кудряшов, Елена elena Рогачева, Дмитрий Nerevar Матов, Виталий kuviman Кудасов. Председателем жюри олимпиады является Михаил MikeMirzayanov Мирзаянов (также автором некоторых задач из комплекта). Я же (Эдвард Edvard Давтян) готовил некоторые задачи и координировал работу авторов. Вот такая большая команда авторов получилась (надеюсь я никого не забыл)!

Также, конечно, поблагодарим Максима Ахмедова (Zlobober), Того-Чьё-Имя-Пока-Нельзя-Называть (если не ошибаюсь он/она прямо сейчас пишет дополнительные решения по задачам раунда) за помощь в подготовке задач, Марию Белову (Delinur) за перевод условий на английский язык и снова Михаила Мирзаянова (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено шесть задач и два часа на их решение. Разбалловка будет объявлена незадолго до начала раунда. Всем высокого рейтинга! Good luck and have fun!

P.S.: Также хочется пожелать удачи участникам четвертьфинала чемпионата мира по программированию южного региона, который пройдет в эту среду.

По техническим причинам раунд перенесен на 10 минут

UPD: По задаче Subway roller в наборе тестов присутствовали тесты с поездами длины 1. В данный момент проводится обсуждение того, насколько сильно это повлияло на результаты раунда. Приносим извинения всем участникам, которых затронула эта проблема. В скором времени будет сделано объявление о принятом решении.

UPD2: При подготовке задачи Subway Roller у одного из авторов было ошибочное понимание условия. Из-за этого валидатор допускал существование поездов длины 1, а так же присутствовали тесты с поездами длины 1. Жюри приняло решение, что если участник посылал в течении контеста верное решение, то оно должно быть ему зачтено. Для этого у каждого участника было выбрано первое отправленное решение, проходящее итоговый тестсет (если таковое решение имелось), а остальные решения были пропущены. Так же баллы за все взломы во время соревнования остались без изменения, включая ситуацию, когда взломанное решение считается правильным на новом тестсете (в этом случае взломщик получает свой балл, а решение участника считается полным). Контест будет признан рейтинговым, однако если вы считаете, что данная проблема сильно повлияла на ваш результат, напишите мне в течении 24 часов и мы рассмотрим возможность сделать его нерейтинговым лично для вас.

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

Доброго времени суток!!!

Когда-то давно на Codeforces шло обсуждение link-cut tree в котором подняли вопрос о том, что делать в случае если операции делаются на ребрах, а не на вершинах (как в обычном link-cut tree). Если не ошибаюсь Burunduk1 единственным ответил на этот вопрос, сказав что посередине каждого ребра можно добавить фиктивную вершину и ей сопоставлять ребро. Этот хак выручает в случае операций на изменение в точке (т.е. когда за раз изменяется значение только на одном ребре). Но это никак не спасает в случае если нужно делать изменение на пути ребер (Heavy-light decomposition без проблем с этим справляется). Кому-нибудь известен способ сделать это, не сильно меняя саму (не меняя совсем) структуру link-cut tree?

Hi Codeforces!

Today while solving problem F from Zepto-cup I need an array of linked lists of size about 6·10⁵ and I decided to use std::stack. But I got ML cause that array has a size of about 350MB. Then I replaced std::stack by std::list and got AC. Anyone know why std::stack use so lot of memory?

#include <stack>
#include <cstdlib>
#include <iostream>

using namespace std;

const int N = 600 * 1000 + 3;

stack<int> z[N];

int main()
{
	z[rand()].push(rand());
	cout << z[rand()].size() << endl;
	return 0;
}
=====
Used: 420 ms, 352524 KB

#include <list>
#include <cstdlib>
#include <iostream>

using namespace std;

const int N = 600 * 1000 + 3;

list<int> z[N];

int main()
{
	z[rand()].push_back(rand());
	cout << z[rand()].size() << endl;
	return 0;
}
=====
Used: 0 ms, 4704 KB

Доброго времени суток Codeforces!

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

Поздравляю всех с наступившим 2015 годом!!! Надеюсь все его встретили на веселе и желаю достижения всех целей поставленных на этот год!

Завтра в 3 часа дня по Москве состоится очередной SRM. Добавил напоминалку поскольку в расписании до сегодняшнего дня вроде ничего не было, а сейчас появилось.

Удачи всем участникам!!!

Добрый день!

Интересует оценка на величины значений x, y получающиеся алгоритмом Евклида. Много раз сдавал задачи с a, b <= 10^9 полагаясь на то, что ничего не переполнится в int и вроде так и есть (ну а если a, b <= 10^18 в long long вроде все норм). Но хочется знать это слабые тесты или есть какая-то точная оценка/худший тест.

Добрый день!

Перед тем как задам вопрос напомню, что статические локальные переменные это практически глобальные переменные, только у них ограничена область видимости. Их использование очень удобно например потому, что многие переменные (особенно в олимпиадном программировании) хочется называть одинаково. Статические локальные переменные позволяют например в каждой функции объявить свой массив cur и с одной стороны это будет глобальная переменная (ей выделится из статическая память), а с другой стороны ее не будет видно вне функции.

Вопрос заключается в следующем: есть какие-нибудь существенные минусы static-переменных? Например медленная работа, медленное выделение памяти и т.д. Мне просто вспоминается как я однажды избавлялся от них из-за каких-то проблем и не могу вспомнить из-за каких.

Заранее спасибо всем кто отпишется.

P.S.: картиночку добавил, чтобы пост смотрелся лучше)

Upd: только, что обнаружил что если объявить большой массив static local, то код медленно компилится (g++). С global быстрее.

Доброго утра!

Только, что прошел очередной СРМ, а поста до сих пор нету( Вот я и решил что настало мое время написать пост про СРМ. Интересно как решать Hard.

P.S.: Кажется у KADR а 2999 рейтинга facepalm. Удачи в следующем раунде :-)

P.S.2: Систесты оказались мгновенными.

Hi everyone!

Today I've got to know that there is a nice algorithm for online MST problem.

The problem looks like this: we have an undirected weighted graph and queries to change the weight of edge, after each query need to find the weight of MST.

I've heard that exist an O(n logn) algorithm for this problem. Can anyone give me some link to the article? Or any book in which I can read about it. Thanks in advance.

Hi!

Anyone know where I can download samples for this problem?

Link from problem is not available

Всем доброго времени суток!

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

1. При включении русского языка текст становится ужасно расплывчато-прозрачным и его совсем не видно (в сети вроде пишут про pscyr, но я его так и не смог установить его и не очень уверен, что он поможет).

2. С помощью библиотечки geometry я поставил пейзажный вид и кастомные отступы и теперь у меня съехал верхний колонтитул вправо (текст должен быть именно с таким отступом как сейчас). Как его подвинуть влево?

3. Хочется как-нибудь поставить поменьше отступ от колонтитула до текста.

Выглядит это так:

Вот весь исходник:

\documentclass[12pt]{article}

\usepackage[russian,english]{babel}

\usepackage[landscape, left=0.7cm, right=0cm, top=1.5cm, bottom=0.4cm]{geometry}

\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{Left}
\fancyhead[R]{Right}
\fancyheadoffset{-0.5cm}

\begin{document}
\selectlanguage{russian}

Hello world!

Привет мир!

\end{document}

Заранее спасибо всем кто ответит.

Всем доброго времени суток!

Много раз при решении задач на деревья (n ≤ 5000) я сдавал динамики в которых квадрат состояний и линия переходов, но если поставить нужный отсек, то динамика работает очень быстро. К примеру нужно нам посчитать количество деревьев таких, что ровно k вершин обладают нужным нам свойством. Я обычно пишу динамику (v, cnt) — решаем задачу для поддерева вершины v при k = cnt. Тупой переход в такой динамике делается за O(cnt) — заводим еще одну динамику по сыновьям и для текущего сына перебираем какое ncnt ≤ cnt мы отдадим ему. Так вот грубая оценка такой динамики O(nk²). Но на деле если поставить отсечение в переборе ncnt ≤ количество вершин в поддереве, то такая динамика будет работать очень быстро. Я слышал, что на самом деле асимптотика здесь O(nk). Умеет это кто-нибудь доказывать? Аналогичный вопрос если делать отсечение по количеству листьев в поддереве.

Всем привет!

Интересует такой вопрос: есть ли какие-нибудь альтернативы писанию в eclipse на финале (для языка C++)? Может есть что-то похожее на far или просто удобный редактор кода (vim не предлагать удобным его трудно назвать :-( ).

Если альтернатив нет, то как нормально копировать шаблонный проект? Я кое-как (спасибо e-maxx у) научился воспроизводить последовательность действий, которая приводит к правильному результату, но если хоть что-то сделать не так, то все ломается.

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

P.S.: Кто-нибудь научился ставить финальную Ubuntu с флешки на ноут?

Всех с прошедшими праздниками!

Всем привет!

Соревнование проходило 24 ноября 2012 года в городе Ульяновске, а теперь доступно в тренировках.

Соревнование было подготовлено AlexErofeev и ArtemKadeev. Сайт соревнования — http://vtcloud0.ulstu.ru/en.

Удачи!

Всем привет!

В тренировки добавлена V и VI Международная Жаутыковская олимпиада по информатике. Жаутыковские олимпиады последних лет добавить не смог потому, что нет исходников чекеров (также авторских решений). В тренировку объединены 2 дня соревнования, всего 6 задач.

Good luck!

Всем привет! Пишу я не по теме спортивного программирования и алгоритмов. Делая некоторые шаманства (слияние и создание разделов диска), я обнаружил, что у меня не загружается комп. Погуглив достаточно долго я смог сделать флешку которая запустила винду, но без нее винда по прежнему не грузится. Проблема то ли в загрузчике Windows, то ли в mbr (хотя может это одно и то же). В общем как восстановить и то и другое если у меня нет Live CD с Windows 7? Утилиту Bootrec.exe я долго искал в сети и для Windows 7 x64 не нашел.

Всем привет!

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

Ну и конечно вопрос: как можно скомпилировать программу, чтобы не было ограничения на память?

P.S.: Компилирую я все под GNU (но есть MVС компилятор) и под виндой.

Всем привет!

Сегодня завершился ВКОШП 2012. Поздравления победителям и призерам первенства.

Победителями стали команды:

1. Нижегородская область: Николай Калинин, Дмитрий Кузьмичев, Ирина Огнева

2. Мозырь, Клуб юных пожарных #1: Сергей Кулик, Ионас Пакальнишкис, Вячеслав Лукьяненко

3. СПб, Сборная: Петр Смирнов, Даниил Клюев, Дмитрий Томп

Полные результаты и материалы доступны по ссылке.

Соревнование доступно в Тренировках.