Разбор задач 8-9 января, 2013 г.Петропавловск

Задача А Очередь в кассу

Постановка задачи Есть очередь из n человек и одна касса Каждую минуту в каждой кассе обслуживается 1 человек Каждые m минут открывается новая касса и из последней в нее переходит половина людей Через сколько минут уйдет последний человек

Как решать? Пусть cur – количество людей в последней очереди Если m >= cur, то новая касса откроется после ухода последнего клиента. res += cur. Иначе до открытия новой кассы уйдет m человек. res += m, cur -= m, cur /= 2. Но очевидно, что если в очереди остался 1 человек, действие cur /= 2 не нужно. Поэтому этот случай стоит проверить отдельно.

Задача B Покраска дорог

Постановка задачи Дан граф, в каждую вершину которого входит ровно одно ребро. Сколько потребуется цветов для раскраски ребер, чтобы ребра одинакового цвета не пересекались в вершинах.

Как решать? В данном графе компонента сильной связности либо вершина, либо цикл. Доказательство: очевидно, что в обратном графе КСС не поменяются. По ребрам обратного графа из каждой вершины мы можем ходить только в одну вершину. Значит, если мы можем из какой-то вершины A прийти в вершину B и из B в A, то A и B лежат на цикле. Для цикла нечетной длины понадобится 3 цвета. Пусть d[i] – степень вершины i, тогда ответом будет max(d[1],…,d[n], (3, если есть цикл нечетной длины))

Задача С Номер перестановки

Постановка задачи Дана перестановка чисел от 1 до n Определить ее номер

Как решать? Стандартная задача на восстановление номера по объекту. Рассмотрим суть решения. Пусть текущее число перестановки a[i]. Очевидно, что к ответу нужно прибавить все перестановки вида (a[0], a[1], a[2]…a[i-1], b), где b < a[i] и среди a[o]..a[i-1] нет чисел, равных b. Пусть количество возможных b = cnt, тогда к ответу нужно прибавить (n – i - 1)! * cnt. Научимся определять cnt.

Решение за O(n*n) Заведем массив u[], где будем отмечать числа, которые мы уже использовали. Тогда для определения cnt можно пройтись по массиву до a[i] и посчитать это количество.

Решение за O(nlogn) Воспользуемся предыдущей идеей, но для хранения массива u[] заведем, например, дерево Фенвика(или дерево отрезков). Тогда чтобы отметить то, что число использовалось нужно вызвать update(a[i], +1), а чтобы получить количество тех, которые можно использовать a[i] - get(1, a[i]).

Задача D Стоянка

Постановка задачи Есть стоянка, на которой n мест и n машин Для каждой машины известно сколько стоит для нее каждое место Стоянка разбита на 2 части, в первой части m мест Приезжают машины и занимают первое свободное место либо в первой части, либо во второй Увеличить прибыль стоянки, то есть распределить машины так, чтобы сумма, которую суммарно они заплатят будет максимальной

Как решать? Рассмотрим решение методом динамического программирования. Пусть dp[i][j][k] – максимальная сумма, чтобы расставить первые i машин так, чтобы в первой части было занято j, во второй k мест. Но заметим, что тогда общее количество состояний n*n*n, что для данной задачи много. Также заметим, что если мы знаем 2 из этих параметра, то третий мы можем восстановить из соотношения j+k=i

Как решать?(продолжение) Оставим первые 2 параметра: количество расставленных машин и количество занятых мест в первой части. Разберем переходы: Ставим i-ую машину в первую часть: dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + cost[i][j]); Ставим i-ую машину во вторую часть: dp[i][j] = max(dp[i][j], dp[i - 1][j] + cost[i][m i - j]); Ответ находится в dp[n][m]

Задача E Лампочки

Постановка задачи Даны 2 типа лампочек: обычная и энергосберегающая Каждая лампочка задается тремя параметрами: её цена, сколько за нее платить в месяц, срок её службы в месяцах. В комнате должно висеть n лампочек в течение m месяцев. Если какая-то лампочка перегорает, ее меняют на такую же. Определить сколько денег уйдет на освещение помещения и сколько каждого типа лампочек нужно купить. При равных ценах вывести тот вариант, где обычных меньше.

Как решать? Оптимальное решение: либо все простые лампочки, либо все энергосберегающие. Доказательство: предположим, что это не так. То есть по крайней мере одну лампочку одного типа выгодно заменить на другой тип. Но тогда и остальные лампочки первого типа выгодно заменить на второй тип. Выберем оптимальное из двух решений.

Задача F Паук Паркер

Постановка задачи Дано n точек. Посчитать сумму манхэттенских расстояний между каждой парой точек(такое расстояние считается по формуле: |x2-x1|+|y2-y1|).

Как решать? Решение за O(n*n) - перебрать каждую пару точек. Нужно более быстрое решение. Посчитаем отдельно для X и отдельно для Y. Пусть в массиве a[] лежат значения соответствующей координаты. Отсортируем его. Теперь для каждого a[i] нужно найти сумму (a[i]- a[0])+(a[i]-a[1])+…+(a[i]-a[i-1]). Преобразуем в: i*a[i]-(a[0]+a[1]+…+a[i-1]) Для быстрого подсчета второго слагаемого будем в переменной cur поддерживать сумму всех элементов от (0 до i-1). Ответ на задачу – сумма ответов для X и Y, сложность O(nlogn).

Задача G Поклейка обоев

Постановка задачи Даны 2 массива строк. В каждом массиве n строк по m символов. Найти наименьший циклический сдвиг второго массива, чтобы превратить его в первый(при одном циклическом сдвиге все строки второго массива сдвигаются вправо, последний элементы становятся первыми).

Как решать? Будем перебирать все сдвиги, пока массивы не совпадут. Сравнение строк происходит за m действий, общая асимптотика O(n*m*m), что для данных ограничений получит TL. Чтобы этого избежать можно воспользоваться КМП или хешами, причем для удобства все строки второго массива можно удвоить(то есть если есть ab, то станет abab).

Задача H Счастливые цифры

Постановка задачи Для каждой цифры от 0 до 9 вывести сколько раз она встречается на счастливых билетах длины 2n

Как решать? Воспользуемся методом динамического программирования Будет представлено 2 решения, 1 из которых работает на максимальном тесте около 20 секунд, но используя его можно предпросчитать все ответы в виду маленького n, второе решение асимптотически будет лучше, поэтому можно обойтись без предпросчета.

Решение 1 Пусть dp[i][j][k][z] – количество таких чисел длины i, что сумма цифр в нем j и цифра k встречается z раз. Рассмотрим переходы для состояний Переберем цифру, которую хотим поставить на позицию i. Пусть она равна d. Если d = k: dp[i][j][k][z] += dp[i-1][j-d][k][z-1] Иначе: dp[i][j][k][z] += dp[i-1][j-d][k][z] Восстановление ответа для цифры: переберем все суммы, s; количество раз, которое эта цифра встречается в билете в левой части, L, и в правой части, R, тогда ans[digit] += (L+R)*dp[n][s][digit][L]*dp[n][s][digit][R]. Количество состояний n*9n*10*n, каждое из которых считается за 10 действий. То есть общая асимптотика O(900*n 3 ).

Решение 2 Посчитаем 2 динамики: dp1[i][j] – количество чисел длины i и суммой цифр j dp2[i][j][k] – количество раз, которое цифра k встречается в числах длины i с суммой цифр j Переходы: Переберем цифру d, которую поставим на позицию i: dp1[i][j] += dp1[i-1][j-d] Научимся пересчитывать dp2[i][j][k]. Очевидно, что цифра k добавится ко всем числам длиной i-1 и суммой цифр j-k, то есть dp2[i][j][k] += dp1[i-1][j-k] Теперь нужно учесть все остальные вхождения этой цифры в нужные нам числа. Переберем цифру d, которую поставим на позицию i: dp2[i][j][k] += dp2[i-1][j-d][k]

Решение 2(продолжение) Восстановление ответа для цифры digit: Переберем сумму цифр в числе s. К каждому числу левой части, у которых общее количество цифры digit равно dp2[n][s][digit] мы дописываем все числа с суммой цифр s, их количество dp1[n][s]. Аналогично для правой части, то есть: ans[digit] += 2 * dp1[n][s] * dp2[n][s][digit] Понятно, что асимптотика складывается только из второй динамики, общее количество состояний в ней: n*9n*10, пересчет каждого из них производится за 10 действий, то есть общая асимптотика O(900*n 2 ), что укладывается в 2 секунды.

Разбор: Бережко Герман Авторы решений: Бережко Герман(задачи A-H) Ергожин Нуржан(второе решение задачи H)

Спасибо за внимание! Вопросы?