CodeChef invites you to participate in the March Cook-off 2015 at http://www.codechef.com/COOK56.

Time: 22nd March 2015 (2130 hrs) to 23rd March 2015 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: http://www.codechef.com/COOK56/

Registration: Just need to have a CodeChef user id to participate.

New users please register here

- Problem Setter : Vitaliy Herasymiv
- Editorialist: Amit Pandey
- Problem Tester: Istvan Nagy
- Contest Admin: Praveen Dhinwa
- Russian Translator : Sergey Kulik
- Mandarin Translator: Gedi Zheng

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.

CodeChef invites you to participate in the August Cook-off 2014 at http://www.codechef.com/COOK49.

Time: 24th August 2014 (2130 hrs) to 25th August 2014 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: http://www.codechef.com/COOK49/

Registration: Just need to have a CodeChef user id to participate.

New users please register here

- Problem Setter : Vitaliy Herasymiv
- Problem Tester and Russian Translator : Sergey Kulik
- Editorialist: Constantin Sokol
- Mandarin Translator: Gedi Zheng & Minako Kojima

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.

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

289A - Пингвин Поло и отрезки

Краткое описание. Есть 10⁵ числовых отрезков, которые не пересекаются. За один шаг можно увеличить любой отрезок на 1 влево или вправо. Нужно найти минимальное количество шагов, после которых число целых чисел, принадлежащих отрезкам, будем делится на k.

Решение. Для начала нужно посчитать, сколько чисел изначально принадлежат заданным отрезкам. Поскольку они не пересекаются и даже не касаются (это следует из неравенства min(r_i, r_j) < max(l_i, l_j) для всех i, j), никакая точка не может принадлежать двум отрезкам одновременно. Поэтому изначально величиной множества есть число .

Если p делится на k, то ответом будет число 0 — не надо делать никаких шагов, все уже готово. Но если это не так, нужно подумать, за какое минимальное количество шагов из p можно сделать число, которое делится k. Можно увидеть, что за один шаг величину множества можно увеличить ровно на 1 (просто либо увеличив влево самый левый отрезок либо увеличив вправо самый правый), но на число больше 1 мы никогда его не увеличим. Тогда минимальное количество шагов будет равно минимальному числу t такому, что . Несложно убедится, что .

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

289B - Пингвин Поло и матрица

Краткое описание. Есть матрица n × m из целых чисел, а также число d. За один шаг можно увеличить или уменьшить любое из чисел матрицы (но только одно) ровно на d. Нужно найти минимальное количество шагов, после которых все элементы матрицы будут одинаковыми, или сообщить, что этого сделать невозможно.

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

Теперь можно свести задачу к несколько другому виду. Переведем все n × m чисел матрицы в одномерный массив b, по сортируем по не убыванию и пронумеруем элементы от 1 до k (тут k это тоже самое что n × m). Цель задачи и шаги, естественно, остаются такими же. Несложно заметить в хотя бы в одному оптимальном ответе, все числа сведены к одному из чисел данного массива. Но, кроме этого, одним из оптимальных ответов будет свести все числа к числу , то есть к медиане массива. Почему именно к медиане? Предположим, что свели не к медианному элементу с номером x. Тогда |x - (k - x)| > 1, то есть с одной стороны хотя бы на 2 элемента больше, чем с другой. Поэтому, передвинув число в сторону уменьшение абсолютной разницы, можно улучшить (или хотя-бы точно не уменьшить) результат.

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

Сложность такого решения: .

Примечание. Полным решением также является решение со сложностью O(n²m²).

288A - Пингвин Поло и строки

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

Решение. Решением этой задачи есть конструктивное построение нужной строки. Но для начала найдем такие параметры n и k, для которых не существует ответа. Естественно, что если k > n, то ответа не существует, так как не может быть k различных символов в строке длиной меньше k. Еще одним случаем есть случай когда k = 1, тогда если n > 1 ответа также не существует. Во всех остальных случаях ответ существует.

Теперь, когда мы знаем что ответ существует, нужно построить лексикографически минимальный. Предположим, что k = 2. Несложно понять, что оптимальным ответом здесь будет строка вида abababab.... Логично, что для k > 2 ответ будет точно лексикографически больше за ответ при k = 2, поэтому стоит как-то как можно правее что-то дописать к ответу для k = 2 так, что-бы он был ответом для k > 2. Минимальное что мы можем (и должны) сделать это переписать последние k - 2 символа строки на первые k - 2 символа алфавита, начиная с символа «c». Например, для n = 7, k = 4 у нас получается строка abababa, а после замены — ababacd.

Примечание. Не достаточно двух проверок k > n или k = 1, потому что для n = k = 1 есть ответ.

288B - Пингвин Поло и дома

Краткое описание. Нужно найти количество таких таких массивов p длины n из целых чисел от 1 до n, что-бы из первых k элементов можно дойти переходами вида x → p_x до 1, из последних n - k не можно было дойти до 1 и что-бы 1 был в цикле (т. е. можно дойти из 1 в 1 за положительное количество переходов).

Решение. Поскольку k ≤ 8, задачу можно решить перебором. То есть, нужно рекурсивно найти всевозможные варианты первых k чисел на табличках (очевидно, что все они будут в диапазоне 1..k). Всего таких вариантов будет k^k (при k = 8 это число равно 16 777 216). Также, для каждого варианта нужно убедится, что он правильный, то есть удовлетворяет все три условия. Это несложно сделать циклом: просто пройтись по всем переходам пока не зашли в цикл и убедится что дом номер 1 был посещен через ненулевое количество переходов.

Когда количество вариантов записи первых k найдены (пусть оно равно f(k)), осталось только найти количество вариантов табличек для остальных n - k домов. Поскольку не должно существовать пути из них в 1, то не должно и существовать пути из них в любую из вершин с номером не больше k (иначе за первым условием будет путь в 1). Из этого следует, что на табличках домов с номерами от k + 1 до n можно ставить только номера от k + 1 до n. Так как нас не интересует как именно они расставлены, всего таких вариантов будет (n - k)^n - k. Поэтому ответом будет f(k)(n - k)^n - k.

Примечание. Существует также решение с использованием динамического программирование, а также более аналитическое — формула для f(k). Более подробно об этом обсуждалось здесь, здесь и здесь.

288C - Пингвин Поло и операция XOR

Краткое описание. Нужно найти такую перестановку p чисел от 0 до n, для которой величина максимально возможная.

Решение. Так как нужно максимизировать ответ, нужно найти такую перестановку, при которой минимальное количество битов пропадут при операции xor, то есть что-бы было как можно меньше таких битов, что они одновременно равны 1 и в i и в p_i (потому что тогда ои ничего не прибавят к ответу). Оказывается, для любого n можно найти такую перестановку, при которой ни один бит не пропадет. Как именно строить такую перестановку? Будем решать задачу итерациями пока n > 0. На каждой итерации, найдем самый старший бит, который не равен 0 в двоичной записи n и обозначим его номер (при нумерации с права налево от 0) через b. Также нужно найти число m — минимальное число от 0 до n (включительно), в котором бит с номером b равен 1. После этого можно увидеть (смотри рисунок ниже), что при не пропадет ни один бит, при не пропадет ни один бит, ..., при не пропадет ни один бит. Поэтому, нам стоит именное такие числа присвоить перестановке (то есть p_m = m - 1 и p_m - 1 = m, p_m + 1 = m - 2 и p_m - 2 = m + 1 и так далее). После этого присвоим n значение m - (n - m + 1) - 1 и перейдем к следующей итерации.

Теперь, когда известно как можно построить перестановку так, что-бы ни один бит не пропадал, ответом будет .

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

288D - Пингвин Поло и дерево

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

Решение. Как всегда в подобных задачах, подвесим дерево за какую-то вершину, например за вершину с номером 1. Нужно выяснить, что будет, если есть какой-то фиксированный путь и надо найти количество способов выбрать другой. Очевидно, что после удаления всех вершин этого пути и инцидентных к ним ребер, дерево распадется на лес (тоесть на множество отдельных деревьев). Пусть их размеры (количество вершин) это числа c₁, c₂, ..., c_k, где k — их количество. Тогда нам с каждой из таких групп нужно выбрать пару чисел, то есть суммарное количество способов будет . То есть, если перебирать такие пути, достаточно воспользоватся этой формулой что-бы найти ответ. Но такой алгоритм — O(n²), поскольку нужно перебирать все пути. Нужно избавится от этого. Для этого dfs-ом обойдем граф и будем фиксировать одну из вершин пути (последнюю). Теперь нужно найти для всех других вершин сумму таких формул как описано выше. Можно здесь отдельно искать такое количество для вершин поддерева и остальных вершин (тех что первое ребро ведет вверх). Для вершин поддерева нужно делать следующим образом. Пусть у нас есть посчитаны ответы для всех вершин, в которые ведут ребра из текущей. Рассмотрим одну из этих вершин и прибавим к нашему ответу ответ из этой вершины. Но это еще не все — нужно добавить еще сумму всех по всем другим вершинам что выходят из текущей (но кроме той которой мы рассматриваем), умноженное на количество вершин поддерева (не всего текущего, а только того что выходит из ребра что перебираем). Это удобно реализуется, используя частичные суммы для оптимизации (что-бы все время не пересчитывать сумму). Для остальных вершин (тех что не в поддереве) все аналогично, но немножко сложнее. Тут можно, например, в dfs-е поддерживать параметр, который равен ответу для текущей вершины. Потом, когда по ребру спускаемся вниз по дереву, нужно обновить результат как это было и в первом случае, но уже с количество вершин равным n минус размер поддерева (тоесть те вершины что не в поддереве).

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

288E - Пингвин Поло и счастливые числа

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

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

Обозначим через a₁, a₂, ..., a_n все счастливые числа промежутка. Сначала нужно сделать следующее сведение задачи. Пусть в нас есть зафиксированная цифра (pos, d), то есть позиция (разряд) pos (начиная с 0 с права налево) и значение d (4 или 7). Тогда, для всех чисел a_i (1 ≤ i < n) таких что pos-я цифра равна d к ответу нужно добавить a_i + 1 × d × 10^pos. Теперь видно, что задача можно свести к следующей. Для каждой фиксированной цифры (pos, d) нужно найти сумму все a_i таких, что a_i - 1 на pos-й позиции имеет цифру d. Естественно, задачу можно решить отдельно для промежутка 1..l и 1..r, а потом отнять первое от второго — это и будет ответ.

Как искать такую сумму среди всех счастливых чисел такой-же длины как входное, но меньших за какое-то x? Опишем общую идею. Любое счастливое число (да и вообще любое) число, меньше за x будет сначала совпадать с ним, то есть иметь некоторый общий префикс, потом одна цифра станет меньше чем в x (то есть там где в x стоит 7 в новом числе стоит 4), а далее цифры будут располагаться произвольным образом. Таким образом, перебрав эту цифру, мы, учитывая произвольность остальных, можем, используя частичные суммы искать ответ для всех позиций и цифр.

Привет!

Завтра, в 19:30 по Москве состоится Codeforces Round #177. Надеюсь, что, несмотря на то что раунд был перенесен, вы все примете участие в нем и будете счастливы.

Помогает готовить раунд, как всегда, Gerald, условия переводит Delinur. Спасибо им.

Удачи!

Сегодня все стандартно:

Div1: 500 1000 1500 2000 2500

Div2: 500 1000 1500 2000 2500

Сегодняшние победители:

Div1:

1. wjmsbmr

2. peter50216

3. rng_58

4. XilinX

5. RAD

6. RomaWhite

7. eduardische

Div2:

1. alimiaomiao

2. yutaka1999

3. Alex.lap

4. zlqiszlq

Is starting right now.

259A - Маленький Слоник и шахматы

Очевидно, правильные строки это сроки вида WBWBWBWB и BWBWBWBW. Все что надо сделать это проверить, является ли каждая строка одной из этих строк.

259B - Маленький Слоник и магический квадрат

Так как все числа находятся на отрезке от 0 до 10⁵, можно просто перебрать все возможные варианты для a_1, 1, остальные клетки будут однозначно известны.

258A - Маленький Слоник и биты

Довольно очевидно что клетка которую нужно удалить — это первая нулевая клетка слева. А если такой нет — любая позиция с 1.

258B - Маленький Слоник и выборы

Первое что нужно придумать, это как найти c_i — количество чисел от 1 до m таких, что количество счастливых цифр в них равно i. Это решается довольно стандартной динамикой с состоянием [позиция][меньше ли число][сколько счастливых цифр]

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

Припустив, что у вас есть группа размером t, каждое присвоенное число которой должно содержать ровно l счастливых цифр. Довольно очевидно что ответ для такой группы будет (c_l) * (c_l - 1) * (c_l - 2) * ... * (c_l - t + 1).

258C - Маленький Слоник и НОК

Сложность решения — O(n * sqrt(n) * log(n)). Можно заметить, что условие lcm(b₁, b₂, ..., b_n) = max(b₁, b₂, ..., b_n) равно условию "все числа b₁, b₂, ..., b_n должны делится на max(b₁, b₂, ..., b_n). Можно перебрать это max(b₁, b₂, ..., b_n), пусть это будет m. Найдем все делители m и отсортируем их — p₁, p₂, ..., p_k. Для всех чисел i между 1 и m можно найти (используя несложное ДП) количество таких a_j что p_i ≤ a_j < p_i + 1 (если i = k то p_i + 1 = max(a₁, a₂, ..., a_n) + 1), обозначим это число как q_i. Тогда результат это 1^q₁ * 2^q₂ * 3^q₃ * ... * p^q_p, так как каждое из q₁ чисел имеет ровно один вариант выбора, каждое из q₂ чисел имеет ровно два варианты и так далее.

258E - Маленький Слоник и дерево

Очень удобно в этой задаче просто упорядочить все вершины в порядке DFS (perorder). После этого любое поддерево может быть представлено как некоторая подпоследовательность (последовательных) вершин. Учитывая это, пусть у нас есть некоторая фиксирована вершина v. Которые вершины мы должны учитывать в c_v? Очевидно, если на пути от корня к вершине v был хоть один запрос, то мы должны учесть все вершины которые есть в поддереве вершины v, но так как мы теперь работаем с некоторым промежутком [l_v, r_v], мы просто считаем что каждая вершина с отрезка [l_v, r_v] должна быть включена в c_v. Более формально, обозначим каждое поддерево через промежуток [l_i, r_i]. Тогда если на i-й операции у нас есть две вершины a и b, мы добавляем промежуток (l_b;r_b) к вершине a, а также (l_a;r_a) вершине b. Также для каждой вершины i (i = 1..n) нужно добавить промежуток (l_i;r_i). После этого можно увидеть, что если мы объединим все промежутки всех вершин от корня к вершине v, мы получим ответ c_v.

Теперь нам нужно структуру данных, которая должна поддерживать операции добавить(l, r), отнять(l, r), посчитать(l, r). Первая должна добавлять 1 ко всем числа на позиция от l к r, включительно. Вторая должна отнимать 1 от всех чисел на позиция от l до r. Последняя должна считать количество ненулевых элементов отрезка. Все эти операции можно сделать с помощью всем известного дерева отрезков.

Всем привет,

А знаете ли вы, что завтра состоится Codeforces Round #157? Его автором являюсь я, и это мой седьмой раунд на CF. Помогает мне его строить Gerald, спасибо ему за это.

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

Желаю вам удачи!

Top-7 Div1:

1. ftiasch
2. rng_58
3. shangjingbo
4. gawry
5. sandytea
6. Petr
7. peter50216

Top-4 Div2:

1. guliashvili
2. --Pavel--
3. HighFlow
4. mohammadrdeh

Спасибо за участие.

Hi!

I'm glad to invite you to my short contest on codechef.com on Sunday, 18th. (Check your time zone here.) I also want to note that Anton_Lunyov help my a lot in preparing of the contest, thanks to him.

In order to take part in the contest you should be registrated on the site, you don't need a separate registration for the contest. The competition will consist of 5 problems for 2.5 hours, using the standard ACM-ICPC rules.

After the contest you can discuss problems here and public all your wishes for the next contests.

Good Luck!

P. S. Please also note that CodeChef is now using much faster judging server!

221A - Маленький Слоник и функция

В этой задаче все что нужно заметить это то, что ответ всегда имеет следующею форму: n, 1, 2, 3, ..., n-1. При такой перестановке не трудно заметить, что после полого выполнения алгоритма перестановка будет отсортирована.

221B - Маленький Слоник и числа

Нужно найти все делители числа n. Это можно сделать простым перебором от 1 до sqrt(n). После этого нужно написать функцию, которая умеет определять, существуют ли две одинаковые цифры в паре чисел. Это тоже можно сделать простым перебором по цифрам.

220A - Маленький Слоник и проблема

Существует несколько решений этой задачи. Например, можно найти максимальное x такое, что существует y (минимальное возможное) такое, что (y < x) и A_x < A_y. После этого остается проверить ровно два варианты — либо менять местами x-е и y-е числа, либо не делать ничего.

220B - Маленький Слоник и массив

Задачу можно решить за O(NsqrtN), но я опишу решение за O(NlogN).

Будем решать задачу в оффлайне, тоесть сначала считаем все запросы, а потом будем давать ответы. Для каждого x (0 ≤ x n) мы должны держать все запросы, концами которых есть x. Будем перебирать x от 0 до n - 1. Также нам нужно поддерживать массив чисел D такой, что для текущего x ответом на запрос [l;x] будет число D_l + D_l + 1 + ... + D_r. Для правильной поддержки массива, перед тем как обрабатывать запросы для текущего x, нудно обновить D. Пусть t — текущее число, тоесть A_x, а вектор P — список индексов всех вхождений числа t (до позиции x), нумерация с 0. Тогда, если |P| ≥ t, нам нужно добавить 1 до D_{P[|P| - t]}, так как эта позиция теперь переломной — после нее будет не меньше чем t вхождений числа t. Потом, если |P| > t, нужно отнять 2 от D_{P[|P| - t - 1]}, для того что-бы закрыть текущий интервал (после этой позиции количество вхождений t будет превосходить t), а также отменить предыдущий. И наконец, если |P| > t + 1, нужно еще добавить 1 к D_{P[|P| - t - 2]} для того что-бы отменить закрытие предыдущего интервала.

220C - Маленький Слоник и сдвиги

Each of the shifts can be divided into two parts — the right (the one that starts from occurrence 1) and the left (the rest of the elements). If we could keep minimal distance for each part, the minimal of these numbers will be the answers for the corresponding shift. Lets solve the problems of the right part, the left will be almost the same.

Let we have some shift, for example 34567[12] and the permutation A is 4312765 and B is 2145673, then shifted B is 4567321. Let we keep two sets (S1 and S2). The first will keep all the distances from integers in current left part to the corresponding positions in A (for the example above, it is [2, 4]). When you come to the next shift, all integers in S1 should be decreased by 1 (that is because all distances are also decreased by 1). But now some integers in set may be negative, when any negative integer occures (it always will be -1) you need to delete it from S1 and put 1 to the S2. Also after shifting to the next shifts, all integers in S2 must be increase by 1. After that, for any shift, the answer will be minimum from the smallest numbers in S1 and S2.

It was very useful to use standart "set" in C++.

220D - Маленький Слоник и треугольник

Давайте переберем все возможные точки нашей плоскости и предположим что это первая точка тройки. Пусть это будет точка (x;y). Пусть вторая и третья точки это (x1;y1) и (x2;y2). Тогда удвоенная площадь равна |(x1 - x)(y2 - y) - (x2 - x)(y1 - y)|. Нам нужно что-бы это число было четным, а также ненулевым. Для начала найдем количество троек, которые образуют четную площадь, а потом отнимем количество точек с нулевой площадью.

Первая подзадача. Так как мы знаем x и y и нам нужно проверить четность, давайте еще переберем все возможные 2⁴ варианты четности x1, y1, x2 и y2 (пусть это d0, d1, d2 и d3, соответственно). Потом проверим будет ли такая тройка чисел формировать 0 после подстановки в формулу площади и взятии по модулю 2. Если это так, тогда нужно добавит к ответу число cx_d0cy_d1cx_d2cy_d3, где cx_d равно количеству целых чисел в промежутке [0..n] таких, что они по модулю 2 равны d. Аналогично для cy_d, только в промежутке [0..m].

Теперь нужно отнять плохие тройки — такие, что треугольник, который они создают, имеет нулевую площадь. Это значит, что тройка точек формирует отрезок (или точку). Так как это отрезок, давайте переберем dx = |x1 - x2| и dy = |y1 - y2|, вместо перебора всех 4 координат. Количество таких отрезков на плоскости равно (n - dx + 1)(m - dy + 1). Также для подсчета количества троек, что формируют такой отрезок, нужно искать количество точек с целыми координатами на плоскости, которые лежат на этом отрезке. Это известная задача — это количество равно gcd(dx, dy) + 1.

Это дает нам, с еще некоторыми оптимизациями, решение за O(nm).

220E - Маленький Слоник, а также инверсии

В этой задачи нужно использовать метод двух указателей. Также нужно использовать RMQ. Если вы не знакомы со структурой данных RMQ, почитать о нем можно здесь.

Для начала, уменьшим все числа, не меняя их относительное значения, тогда все числа будут в переделе от 0 до n - 1. Нужно поддерживать два RMQ, каждое размером n. Пусть первое RMQ это Q1, а второе — Q2. Q1_i будет содержать количество чисел i в текущему левом подмассиве, а Q2_i — в правом. Для начала нужно добавить все n чисел в левое RMQ. После этого будем идти указателем r от n - 1 до 1, при этом поддерживая l — максимальный индекс такой, что пара (l;r) содержит не более чем k инверсий (в начале l равно n - 1). Количество инверсий, очевидно, нужно поддерживать, используя RMQ (используя операцию "сумма на отрезке").

В такой реализации время выполнения алгоритма равно O(NlogN).

Завтра, 31-го августа, за 4 с половиной часа до конца лета (по Москве) будет проходить Codeforces Round #136. Автором этого контеста буду я, это уже мой 6-й контест на CF.

Помогает строить раунд мне Геральд Агапов (Gerald), задачи переведет, как я предполагаю, Мария Белова (Delinur). Спасибо всем.

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

Спасибо за участие. К сожалению, большинство моих контестов не пользуются особым интересом, судя по системе "Вклад", но надеюсь все-таки нашлись те, кому он понравился :)

В первом дивизионе ровно 7 участников решили все задачи, они и попадут на главную:

1. peter50216
2. yeputons
3. winger
4. rng_58
5. RAD
6. al13n
7. KADR

В то время Топ-4 во втором дивизионе выглядит следующим образом:

1. blue.boy
2. de_troit
3. lxyxynt
4. ilona

На данный момент есть только разбор на английском.

205A - Маленький Слоник и Роздол

Это была самая простая задача из набора. Нужно просто отсортировать все расстояния (при этом поддерживая индексы) и, если первые два расстояния равны, вывести "Still Rozdil", иначе вывести индекс первого элемента.

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

205B - Маленький Слоник и сортировка

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

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

205C - Маленький Слоник и промежуток

Естественно, для того что-бы решить задачу нужно написать функцию F(x) которая будет решать задачу на промежутке 0..x, тогда ответом будет F(r) - F(l - 1).

Опишем реализацию функции F(x). Если x < 10, результатом будем сам x. Пусть len — длина числа x, а x' — число x без первой и последней цифр, а x_i — i-я цифра числа x (от 0 слева направо). Переберем первую цифру d (она и будет последней) и длину того что внутри (пусть это будет i). Тогда если i < len - 2 или (i = len - 2 и d < x₀), к ответу нужно добавить 10ⁱ. Иначе, если i = len - 2 и d = x₀ то к ответу нужно добавить x', а если еще и i = len - 2, d = x₀ и x_len - 1 ≥ d то нужно добавить еще 1 к ответу.

Также эту задачу можно было решить используя ДП.

205D - Маленький Слоник и карточки

Эту задачу можно удобно решить используя структуру map, но можно и обойтись без нее (используя сортировку и бинарный поиск). Давайте переберем цвет-кандидат который и приведет к веселости набора, для каждого цвета узнаем минимальное количество переворачиваний (если возможно вообще) и выберем минимум. Если никакой цвет не подходит, ответ "-1". Для того чтобы найти минимальное количество переворачиваний нам нужно узнать два числа — количество карточек которые изначально лежат текущим цветом вверх, а также количество карточек у которых сзади есть текущий цвет (при этом сверху какой-то другой). Пусть это числа a и b. соответственно. Пусть m = (n + 1) / 2 — минимальное количество одинаковых карточек необходимых для того, что-бы сделать набор веселым. Тогда текущий цвет может сделать набор веселым только если a + b ≥ m. Если a ≥ m, то ничего переворачивать не надо, то есть ответ 0, иначе ответ равен m - a.

205E - Маленький Слоник и Фурик и Рубик

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

Пусть у нас текущий символ в первой строки с номером i (всюду 1-нумерация). Сначала решим задачу за O(N²). Переберем все позиции j левее i (или равные i) такие что B_j = A_i. Тогда для какой-то позиции нужно найти количество возможных пар строк таких, что в них именно эти два символы A_i и B_j совпали. Это количество будет равно j(n - i + 1) (j возможных символов слева и (n - i + 1) справа, поэтому общее количество это их произведение). Это будет O(N²). Так как все это — сумма, то ответ будет равен S_i(n - i + 1), где S_i — сумма всех позиций j таких, что B_j = A_i. Массив S можно несложно посчитать за линейное время. Аналогичным образом нужно обработать все индексы что правее i.

После того как количество пар подстрок в которых i-й символ первой строки имеет совпадение найдено (пусть это count), к ответу нужно добавить count / total, где total — полное количество возможных исходов, его можно найти циклом или несложной формулой.

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

204D - Маленький Слоник и ретро строки

Для начала нам нужно решить следующую подзадачу: для каждого префикса найти количество его заполнений таких, что он не содержит подстроки длиной k состоящую только из букв B. Пусть это будет F(x), где x это номер последнего символа префикса. Давайте присвоим F(x) = F(x - 1) * cnt, где cnt = 2, если S_x = 'X', 1 иначе. После такого присвоения в результат могли быть включены некоторые способы такие, что блок из k есть в конце префикса (они могли быть включены только если в подстроке S_{x - k + 1..x} нет букв W, а символ S_x - k не есть B), а это плохо. Поэтому (если такое могло произойти) нужно от F(x) отнять F(x - k - 1), это уберет все плохие варианты.

Аналогичное ДП нужно посчитать для для суффиксов (или, иначе говоря, для реверсовной строки S), только здесь нужно избегать блоков из W.

Теперь подумаем как организовать все что-бы не появилось повторов. Давайте переберем позицию, в которой будет заканчиваться первый слева блок из k подряд идущих букв B. При этом будем перебирать эту позицию справа налево. Используя ранее подсчитано ДП мы можем найти количество вариантов заполнить все буквы левее так, что-бы там не образовался блок. Если писать решение за O(N²), то мы можем перебрать позицию, в которой будет начинаться первый справа блок из k букв W, аналогичным образом найти количество способов заполнить все правее что-бы там не образовался блок, а символы между левым и правым блоками мы, очевидно, можем заполнять как-угодно. Но, так как мы идем справа налево, мы можем по ходу поддерживать сумму этих количеств. Это обеспечит нам линейность решения.

204E - Маленький Слоник и строки

Для решения данной задачи воспользуемся свойствами суффиксного массива. Болле подробно о суффиксном массиве можно почитать здесь:

http://e-maxx.ru/algo/suffix_array

Для начала нужно конкатенировать все строки в одну, при этом разделяя их какими-то символами которые не встречаются в строках. Например, три строки abc, a, ab можно склеить в одну следующего вида: abc#a@ab. Теперь нам нужно построить суффиксный массив по новой строке, это позволит нам отсортировать все циклические сдвиги строки. При этом первый символ каждого циклического сдвига это либо вспомогательный символ, либо символ какой-то входной строки.

Заметим теперь что для того что-бы найти результат нам нужно для каждого циклического сдвига, начало которого принадлежит какой-то входной строке, найти максимальную длину его префикса такую, что этот префикс является подстрокой как минимум k входных строк. Это число можно искать бинарным поиском, но для этого нужно какую-то функцию которая бы отвечала на вопрос: а сколько есть различных входных строк которые содержат префикс длины len циклического сдвига номер x (Пусть это функция F(x, len)).

Как же сделать функцию F(x, len)? Рассмотрим все циклические сдвиги, префикс длины len которых ровен префиксу длины len x-го сдвига. Заметим что, так как все сдвиги отсортированы лексикографически, набор таких сдвигов будет представлен каким-то промежутком [l;r] (1 ≤ l ≤ x ≤ r). Как же найти этот промежуток? Для каждой пары соседних сдвигов можно найти их наибольший общий префикс. Тогда l, например, можно найти используя RMQ — для этого нужно найти самую правую пару соседних сдвигов (левее x) таких, что их наибольший общий префикс меньше len. Аналогично можно найти r. После этого у нас есть промежуток [l;r] и нужно найти количество различных строк которые соответствуют этим сдвигам (иными словами, найти количество различных чисел в подмассиве). Но, заметим, что самое количество различных нас не интересует, а интересует только не меньше ли оно за k или нет. Тогда пусть L[i] равно максимальному j (j ≤ i) такому, что количество различных чисел в помассиве [j;i] ровно k. Тогда если L[r] ≥ l то, логично, что и в промежутке [l;r] также будет не меньше k различных чисел.

Осталось заполнить массив L. Это довольно просто сделать используя структуру set (можно также использовать RMQ). Будем идти слева направо и в сете поддерживать индексы самых правых k различных чисел. Тогда если поступает какое-то число, то (если оно встречалось раньше) его прежнее вхождение нужно удалить из сета (если оно еще осталось) и вставить текущее. При этом если размер сета превышает k нужно извлекать минимальный элемент. Тогда если в какой-то позиции i размер сета есть k (после описанных выше изменений), это означает, что L[i] ровно минимальному элементу сета.

Так как мы O(N) раз используем бинарный поиск, а функция F(x, len) работает за O(logN), финальная асимптотика решения равна O(Nlog²N).

Привет!

Вот и пришло время очередного раунда Codeforces, а именно раунда номер 129. Он состоится 11.07.2012 в 19:30 (по Москве). В этот раз задачи для Вас готовил я. В далеком прошлом я уже был 4 раза автором задач для Codeforces, тогда задачи были в основном о счастливых числах. Но ничего не вечно, поэтому в этот раз не будет задач о счастливых числах и тематика задач будет различной.

Помогал мне готовить задачи Геральд Агапов (Gerald), Александр Куприн (Alex_KPR), Аксёнов Виталик (Aksenov239), а традиционно задачи перевела Мария Белова (Delinur), за что им всем спасибо.

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

Держитесь!

Спасибо всем за участие. Результаты оказались следующими:

Div1:

1. tourist (теперь tourist первый в мире таргет Codeforces, с чем его поздравляем)
2. winger
3. RAVEman
4. rng_58
5. RAD
6. bmerry
7. Shik

Div2:

1. xiaoshua2
2. ahm.kam_92
3. HanzhongBall_Quanling
4. daidailanlan

Разбор задач можно найти здесь.

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

Рад пригласить Вас принять участие в моем первом кратком соревновании на codechef.com, в воскресение, 20:00 по Москве. Раньше я уже давал несколько задач для длинных контестов, но это первый полный контест, все задачи которого подготовлены мной. Стоит также отметить, что контест мне помогал и помогает готовить Anton_Lunyov, за что ему отдельное спасибо.

Для участие в соревновании Вам достаточно зарегистрироваться на сайте, дополнительной регистрации на соревновании не нужно. Контест пройдет за стандартными правилами ACM-ICPC, Вам нужно будет решить 5 задач за 2,5 часов. Первые 10 участников получают призы от организаторов.

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

Удачи!

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

Завтра, 22-го января в 11:00 (Московское время), состоится Codeforces Round #104! Автором задач являюсь я, Герасимов Виталий (witua). Большое спасибо Артему Рахову (RAD) за помощь в подготовке задач и Марии Беловой (Delinur) за перевод условий на английский язык.

Надеюсь все пройдет хорошо и всем понравится.

До встречи на раунде!

Разбалловка задач:

DIV1: 500-1000-1500-2500-2500

DIV2: 500-1000-1500-2000-2500

Спасибо всем за участие, вот и результаты:

Дивизион 1:

1. tourist
2. dzhulgakov
3. PavelKunyavskiy
4. wuzhengkai
5. shangjingbo
6. ilyakor
7. Gerald

Кто-нибудь знает что случилось с практис румами SRM-ов с номерами от 200 до 300 и когда они будут доступными? Есть ли какая-то альтернатива тестирования задач со старых SRM-ов, кроме как ручного тестирования?

Всем привет!

Вот и опять пришло время раунда, в этот раз это Codeforces Beta Round #91! Автором задач являюсь я, Герасимов Виталий (witua). Большое спасибо Артему Рахову (RAD) за помощь в подготовке раунда и Марии Беловой за перевод условий. Надеюсь задачи всем понравятся.

Приятного раунда!

Спасибо всем за участие! А вот и победители:

Дивизион 1:

1. tourist
2. 2222
3. PavelKunyavskiy
4. Petr
5. vepifanov
6. dzhulgakov
7. e-maxx

Всем привет!

Div.2 – A. Football

В этой задаче достаточно просто найти самую длинную подстроку из одинаковых цифр и проверить или ее длина является не менее 7.

Div.2 – B. Lucky Numbers - 2

Если длина входного числа является нечетным, то, очевидно, искомое число имеет длину на 1 большую и выглядит так: 4444 ... 7777, то есть сначала L / 2 четверок, затем L / 2 семерок, где L - длина входного числа + 1. Если число имеет четное количество цифр, то, возможно, число-результат будет иметь такое же количество цифр, или на 2 больше. То есть, длина результата будет не более чем на 2 длиннее, чем число N. Это означает, что мы можем легко рекурсивно сгенерировать все счастливые числа длиной до 10, выбрать из них очень счастливые числа, среди них найти наименьшее, не меньше N.

Div.1 – A, Div. 2 – C. Hockey

Заведем массив B. Для каждого слова из словаря найдем все вхождения в строке S, для кожного из них B [i] обозначим true, где i лежит в [Li, Ri], где Li - номер самого левого символа следующего вхождения, Ri - самого правого . Теперь для каждого i, для rоторого B[i] = true, сделаем следующее:

•          Если S[i] = letter і letter = ‘a’, тогда S[i] = ‘b’
  
•          Если S[i] = letter і letter != ‘a’, тогда S[i] = ‘a’
  
•          Если S[i] != letter, тогда S[i] = letter.
  

Очевидно, что это удовлетворяет условию и гарантирует максимальное количество letter и ее лексикографическая минимальность. Также нужно аккуратно различать большие и маленькие латинские буквы.

Div.1  - B. Lucky Number

Сначала смотри Div.2 – B

Заметим, что ответ будет примерно таким: к какой-то позиции результат будет совпадать с N (эта часть будет счастливым число), следующая цифра увеличится, а затем будет идти как угодно. Переберем все такие возможные позиции. Чем больше номер такой позиции, тем меньше будет число. Возможные позиции будут в промежутке [0, lucky_prefix], где lucky_prefix - размер наибольшего префикса строки (числа N), который является счастливым. Пусть мы рассматриваем позицию i. Если цифра в ней меньше 4, мы можем установить ее 4, при этом можем как угодно менять все цифры правее. Так же, если цифра меньше 7 (только в случае если она больше или равна 4) - установим ее 7. При этом некоторые позиции могут нам не подойти. Для того чтобы позиция подошла, нужно чтобы абсолютная разница между количеством четверок и семерок к позиции i (включая i, включая замену) была меньше или равна размера части справа от i. Теперь пусть позиция i подошла нам (и она является самой правой возможной), тогда нужно заполнить правую часть. Ее следует заполнять следующим образом слева направо: если на какую позицию мы поставим 4 и дальше сможем заполнить число так, чтобы количество четверок и семерок была равной (т.е. abs (c4 + 1- c7) <= n-j-1, j - текущая позиция которую рассматриваем, c4, c7 - количество 4-ок и 7-ок в позиции j, включая заменены цифры), то поставим 4, иначе 7. Если позиции i не существует, то ответ - число в форме 4444 ... 7777, здесь количество четверок = количеству семерок = (n +2) / 2.

Div.1 - C, Div.2 - D. Volleyball

Сначала в этой задаче нужно найти минимальный путь между всеми парами вершин. Так как их количество до 1000, то обычные кубические алгоритмы по времени вкладываться не будут. Для этого нужно было написать алгоритм Дейкстры за O (N * (N + M) * logN), подробнее об этом можно прочитать здесь: http://e-maxx.ru/algo/dijkstra_sparse. Следующей частью решения задачи является составление новой матрицы, для которой G[i][j] = C[i], если D[i][j] <= T[i], иначе G[i][j] = INF. Здесь D[i][j] - минимальный путь между вершинами i и j, G[i][j] - стоимость такого пути. Теперь нужно просто найти минимальный путь между вершинами X и Y используя G, что можно выполнить используя простой алгоритм Дейкстры за O (N * N + M).

Div.1 – D, Div.2 – E. Horse Races

Традиционно напомню, что ответ будет Результат (0 .. R) - Результат (0 .. L-1).

Пусть у нас есть заполненный массив DP[x][y][z] - количество чисел длины x если последняя счастливая цифра в нем была на позиции y и boolean z (0 or 1) - была уже пара счастливых цифр на расстоянии не больше K. Ответ теперь будем строить так. Пусть s - строка, которая является числом N, F (x, y, z) - результат для префикса к позиции x, y - последняя счастливая цифра, z (0,1) - была пера счастливых цифр на расстоянии не более K. Очевидно, что если мы в какой позиции поставим меньшую цифру чем в строке, то все цифры справа мы можем выставлять как угодно (если только все цифры слева от этой позиции совпадают с лентой). Переберем возможные цифры, которые поставим в текущей позиции. Если эта цифра меньше чем s [x], тогда к результату для F (x, y, z) добавим DP [n-x-1] [yy] [zz]. Здесь y и z возможно изменится и перейдут в yy и zz, если цифра которую мы устанавливаем является счастливой. Если эта цифра равна s[x], тогда к результату прибавим F (x+1, yy, zz) - опять, y и z изменится, если s [x] является счастливой цифрой. DP заполняется тривиально. Пусть из состояния (x, y, z) мы ставим на позицию x какую цифру d. Из состояния (x, y, z) мы можем перейти в состояние (x+1, yy, zz). y перейдет в yy и z в zz при тех же условиях что и выше.

Сложность - O (T * |N|).

Div.1 – E. Lucky Country.

Пусть все A[i] - посортированы размеры различных компонент связанности, C[i] - количество компонент размером A[i]. Сумма по всем C[i]*A[i] равна N. Размер массива A будет O (sqrt (N)).

Пусть все C [i] = (2^k) -1. Разложим его следующим образом 1 + 2 + 4 + 8 + ... + 2^(k-1). Очевидно, что если выбирать из такого множества какое-то подмножество (его стоимость будет равна ее размера), можно представить любое число от 0 до C[i]. То есть мы свели задачу к следующей. Для каждого A[i]  есть log (C [i]) вещей, каждая из которых имеет стоимость и может быть использована или не использована. Это уже стандартная задача о рюкзаке (почитай http://ru.wikipedia.org/wiki/Задача_о_рюкзаке). Сложность такого решения O (N * S), где S - сумма по всем log (C [i]). Если же C[i] не является степенью двойки, то нужно найти наибольшее k для которого (2 ^ k) -1 <= C[i] и добавить в множество C[i]-((2^k)-1).