Сначала в общих чертах о раунде.
Моими задачами в этом раунде были задачи A-div2, B-div2, C-div2/A-div1, E-div2/C-div1, D-div1. Сначала я хотел провести на них контест исключительно для второго дивизиона. Однако затем мы решили провести общий раунд. MikeMirzayanov подготовил задачу про молоко, anonymous предоставил задачу E-div1. Кроме того, по напутствию RAD были усложнены Аземблер и Флаги.
По-моему, получилось неплохо для первого раза (кроме небольшого фейла с рамочками). Во всяком случае, мне понравилось. Правда, я не ожидал, что Аземблер и Флаги решит так мало народу.
А теперь разбор.
Задача A (div.2) - Восстановление пароля
Текст задачки был актуален чуть более года назад, когда свирепствовал вирус piggy.exe :) Но в то время у меня не было возможности где-либо опубликовать эту задачу.
Пароль восстанавливался достаточно просто. Достаточно перебрать в нем все группы по 10 символов, и, если какая-то группа совпадает с одним из кодов для цифр, вывести эту цифру и перейти к следующей группе.
Вот пример решения: http://pastebin.com/hMV0NcjN
Задача B (div.2) - Друзья
Возможно, некоторых смутила формулировка утверждения. Однако именно так оно звучит в книжке, из которой я его нагло скопировал :)
Построим граф, где вершинами будут люди, а ребрами - отношения между людьми. Обозначим ребра, соответствующие знакомству, красными, а ребра, соответствующие незнакомству - черными. Тогда "трое попарно знакомых" в нашем графе будут представлены циклом длины 3, состоящим только из красных ребер, а "трое попарно незнакомых" - циклом длины 3, состоящим только из черных ребер.
Т.к. вершин в графе всего 5, достаточно написать 3 вложенных цикла for (каждый цикл соответствует одной вершине графа) и проверить, что ребра между этими вершинами имеют одинаковый цвет.
Пример решения: http://pastebin.com/gswaxGmM
На самом деле ответ FAIL будет лишь в одном случае - когда в графе ровно 5 ребер и они образуют цикл длины 5 (как в тесте 2). Вот шуточное решение на эту тему: http://pastebin.com/09T0ixrJ
Задача A (div.1) / C (div.2) - Рамочки
Задача сама по себе довольно простая, но возможностей ошибиться было довольно много, что участники успешно продемонстрировали :) Было решено не устраивать
Beta Round 60, а добавить все сложные случаи в претесты.
Итак, давайте разберемся в задаче. Во-первых, заметим, что ответ всегда не превосходит 3, т.к. любое множество подряд идущих папок можно разбить на 3 прямоугольника (возможно, пустых). В первый прямоугольник мы поместим конец первой строки, во второй - все, кроме конца первой строки и начала последней (это будет прямоугольник с шириной
m), а в третий - начало последней строки.
Самый простой способ решить задачу --- проверить, что ответ 1 или 2, а иначе вывести 3. Давайте рассмотрим, в каких случаях ответ меньше 3.
Итак, пусть ответ - единица. Значит, все требуемые папки можно выделить за одно движение мышкой. Вот эти случаи (в скобках показан тест для этого случая):
- первая и последняя папки находятся в одной и той же строчке (21 5 7 9);
- первая папка находится в самом левом столбце, а последняя - в самом правом (21 5 1 15), этот случай покрывает случай m = 1;
- первая папка находится в самом левом столбце, а последняя имеет номер n (21 5 6 21). Сюда же относится тот случай, когда надо выделить вообще все папки.
Теперь рассмотрим все случаи, когда ответ равен 2:
- первая и последняя папки находятся в соседних строчках (21 5 8 14);
- первая папка находится в самом левом столбце (21 5 6 13);
- последняя папка находится в самом правом столбце (21 5 4 15);
- последняя папка имеет номер n (21 5 4 21);
- столбец, в котором расположена первая папка, находится непосредственно справа от столбца, в котором расположена последняя папка (21 5 3 12). Мне кажется, это самый хитрый случай в задаче.
Если ни одно из этих условий не выполняется, то ответ равен 3.
Пример решения: http://pastebin.com/8QRytzzF
Еще эту задачу можно было писать сжатием координат и перебором, но психов среди нас нет :)
Задача B (div.1) / D (div.2) - Окончание сессии
Задача решается жадным алгоритмом. Нужно последовательно пробовать переливать из каждой бутылки молоко в любую кружку, которая для этого подойдет и в максимально возможном количестве.
В ходе процесса надо помнить, сколько молока находится в каждой кружке и каждой бутылке, а также из каких бутылок наливали в каждую кружку и куда переливали из каждой бутылки. Эта информация нужна, чтобы определять, а можно ли перелить из конкретной бутылки в конкретную кружку или нет.
Остается это просто написать - ничего сложного, как мне кажется. Единственный момент - сравнивать вещественные числа надо, используя EPS. Без этого можно получить WA на тесте 12 (50 1000 49), где из-за неправильного сравнения программы некоторых участников выдавали NO, тогда как решение существует.
В обсуждении ниже показано, что ответ можно считать в целых числах, если взять объем бутылки, равный mn. А при выводе будем делить на mn и умножать на w. Ни одно из трех решений жюри до этого не додумались :)
Пример решения: http://pastebin.com/HG5Nrxne (оно уже не такое красивое, как предыдущие, но понять, как мне кажется, можно)
Задача C (div.1) / E (div.2) - Аземблер
Меня удивило маленькое количество сабмитов по этой задаче. Достаточно маленькие ограничения на n и большое ограничение по времени явно намекали на перебор. Кроме того, интуитивно понятно, что максимальный ответ находится в районе 5.
Для получения решения необходимо хранить (например, в векторе) текущие значения регистров и перебирать всевозможные новые значения, получаемые из текущих, а затем рекурсивно запускаться с новым набором чисел в регистрах. Попутно можно сохранять и саму программу.
Чтобы при этом не возникло TLE, надо хранить максимальную глубину рекурсии (собственно, это первое число в ответе), в которой мы достигли ответа, и не ходить глубже. Также не следует ходить в те состояния, где мы получаем число, большее n. Если же мы получили ровно число n, и наша глубина рекурсии меньше минимальной, запомним ответ и скопируем его в безопасное место, чтобы потом вывести.
Еще есть улучшение, которое состоит в том, чтобы перебирать числа по убыванию (так работает быстрее), но ограничения в 5 секунд хватало, чтоб перебирать числа как угодно.
Были и другие подходы к решению этой задачи: поиск в ширину и перебор для конкретного ответа.
Вот два решения: обычный перебор (http://pastebin.com/Z6ZF36st) и перебор для конкретного ответа (http://pastebin.com/viiYF9CB).
Задача D (div.1) - Флаги
Сначала я расскажу, как считать ответ для одного числа (т.е. L = R), а потом переделаю решение для общего случая. Дело в том, что изначально задумывалась как раз формулировка с конкретным числом полос N, и только потом мы было принято решение усложнить задачу. Мое решение не сильно оптимально (задачи все-таки не "фиолетовые", как оказалось, а некоторые решения - "фиолетовые" :) ). Я видел коды других участников, и у них все попроще.
Итак, задача для фиксированного N.
Обозначим за число флагов с N полосами, считая симметричные флаги разными. Посмотрим, как, имея эту информацию, получить ответ на задачу.
На первый взгляд, достаточно поделить на 2. Но, посмотрев повнимательнее, можно обнаружить, что это верно только для флагов, не являющихся палиндромами. Например, флаги-непалиндромы WBWB и BWBW симметричны, и надо учитывать только один из них --- здесь деление на 2 законно. А вот флаги-палиндромы, такие, как WBW, симметричны сами себе, поэтому деление на 2 для них приведет к ошибке.
Посмотрим, что можно сделать. Во-первых, заметим, что при четном N корректных флагов-палиндромов вообще не существует, т.к. иначе в центре встретились бы 2 полосы одного цвета, что невозможно, поэтому для четных N формула верна.
Для нечетных
N корректна формула
, где
--- количество флагов-палиндромов длины
N. Но каждый флаг-палиндром нечетной длины
N однозначно определяется своими первыми
полосами, и количество таких флагов-палиндромов равно
(здесь, разумеется, симметрию учитывать не надо).
Итак, мы свели нашу задачу к нахождению числа флагов с
N полосами, причем симметричные флаги считаются различными. Заметим, что для того, чтобы пририсовать очередную полосу к флагу так, чтобы он остался корректным, нам необходимо знать лишь последнюю и предпоследнюю его полосы.
Применим динамическое программирование. В качестве состояния возьмем вектор
из 8 чисел, каждая компонента которого будет содержать количество флагов c общим количеством полос
N и определенными корректными последней и предпоследней полосами (как раз 8 вариантов). Сумма всех компонент этого вектора даст нам общее количество флагов с
N полосами, т.е.
.
База динамики --- вектор
, содержащий ровно 8 единиц (они соответствуют всем разрешенным парам цветов). Давайте подумаем, как можно найти вектор
, зная вектор
.
Оказывается, существует такая матрица
A, что
. Элементы этой матрицы можно посчитать даже вручную, из следующих соображений. Например, пусть мы имеем комбинацию последних двух полос WB. Тогда можно справа дописать белую или желтую полосу, что будет соответствовать BW и BY. Поэтому в столбце матрицы, соответствующему WB, мы поставим единички в строках, соответствующих BW и BY. Все это займет не более минуты.
И последний шаг. Очевидно, что
. А возведение в степень можно проводить быстро, за логарифмическое время. Принцип в том, что, если
N четное, то нам достаточно вычислить
и возвести эту матрицу в квадрат. А если
N --- нечетное, то
N - 1 - четное, и для степени
N - 1 можно снова применить этот прием.
Осталось не забыть, что при
N = 1 все это неприменимо, зато можно сразу сказать, что ответ равен
4.
А теперь проапгрейдим это решение для случая отрезка
.
У меня есть два способа это сделать. Первый способ состоит в том, что в векторе состояний добавляется одна координата, а в матрице - новая строка и столбец. Эта новая координата в векторе состояний будет хранить сумму на отрезке
(с
L = 1 разберемся if-ом). Останется подогнать матрицу
A, что делается довольно несложно. Попробуйте сами (подсказка: я умножал ее слева еще на одну, почти единичную матрицу).
Второй способ мне понравился больше. Так же, как и ранее, разделим задачу на две: на палиндромы и непалиндромы. Научимся находить ответ для флагов без учета симметрии на отрезке
. В вышеприведенных обозначениях ответ равен
. Покажем, как можно быстро и просто находить сумму
E + A + ... + AN.
Пусть
b --- такая максимальная степень двойки, что
2b - 1 ≤ N. Разобьем нашу сумму следующим образом:
.
Оказывается, первая часть этого выражения легко считается:
. Вы можете сами убедиться в справедливости этого равенства. А сумма в скобках второй части выражения из предыдущего абзаца что-то напоминает... Разберетесь сами :)
Ответ для палиндромов считается таким же способом. Будем полагать для удобства, что
L и
R - нечетные (если это не так, то к
L можно прибавить единицу, а от
R - отнять). Тогда
.
Вот и все. Остается не ошибиться, после каждой операции брать модуль и внимательно рассматривать крайние случаи.
Вот решение вторым способом:
http://pastebin.com/wHu1tPgdНаверное, можно все сделать куда проще. Пишите свои разборы, чем их больше - тем лучше!
Задача E (div.1) - ЛостборнЭта задача решается формулой включений и исключений. Только многие получили TLE, т.к. они почему-то не прогнали максимальный тест на своем компьютере (да, прогоняйте макс. тесты на своем компьютере!).
А остальные почувствовали, что что-то тут не так, и запоминали ответы для небольших N и конкретного ai в массив, чтобы в дальнейшем их не считать. Например, можно посмотреть решение победителя турнира rng_58, там все очень четко и понятно написано. Вот еще один пример такого решения: http://pastebin.com/4kcfJdAi
Более подробно об этой задаче написал ее автор anonymous вот в этом посте: http://mirror.codeforces.com/blog/entry/2216. У него есть решение, укладывающееся в ограничение по времени при N ≤ 1015, что, скорее всего, не сделало бы ни одно из решений, отправленных во время контеста. Это решение можно посмотреть в дорешивании.