Поехали.
A. Автодополнение
В это задаче требовалось прочитать условие и решить как угодно. Одно из самых простых решение - считать строчку, считать последние страницы, отсортировать (хоть пузырьком - 1003 прекрасно укладывается, куб потому что надо еще сравнивать), а затем бежать с начала до конца и выводить первую строку, у которой префикс совпадает с нашей. Это проверяется if'ом на длину (чтобы не было RTE) и одним for'ом. Нашли строку - вывели и завершились. Они отсортированы, поэтому выведем то, что надо. Если не нашли - вывели исходную строку.
Из-за бага в GCC на этой задаче я потерял минут 25. В конце концов сдал решение на MSVC++.
Но это было отступление, теперь к делу.
Для начала давайте переберём одну сторону (ту, которая является степенью двойки). Так как сторон две, а писать два раза кусок кода не хочется, давайте сделаем внешний for от 1 до 2, и в релаксации ответа и проверке границ на втором шаге будем менять w и h местами. Это избавит нас от лишнего куска кода.
Итак, перебрали, положим, h=2x. Теперь надо найти такое w, что 0.8 <= h/w <= 1.25. Решим относительно w и получим, что h/1.25 <= w <= h/0.8. Т.к. w - целое, то оно может лежать в диапазоне от ceil(h/1.25) до floor(h/0.8) включительно. Т.к. надо максимизоровать площадь и h фиксированно, надо максимизировать w. Надо взять w=floor(h/0.8) и проверить, что оно подходит. Если да - прорелаксировать ответ.
Итого решение разботает за O(log2 h), что безповоротно вкладывается в TL.
Возможные косяки были:
Первое, что надо было заметить - n <= 10. Это значит, что решение экспоненцеальное, и можно перебирать какие-нибудь подмножества. Так и сделаем.
Давайте посчитаем динамику по подмножествам: d[m][subm] - количество способов сделать связанное дерево из подграфа m с тупиковыми вершинами subm. Ответ будет суммой по d[2n-1][x], где кол-во единичных бит в x = k.
Как пересчитывать: для пустого множества и множества из двух вершин (либо 0, либо 1) - очевидно. Одного тупика в дереве не бывает вообще. Теперь для большего: переберём i из subm - какой-нибудь тупик. Отрежем его от дерева по некоторому ребру в b (причём b не должно быть тупиком, иначе получится несвязный граф). Получаем дерево на меньшем множестве вершин и с либо уменьшенным на 1 множеством тупиков, либо с изменённым i на b (если у b было ровно два соседа) Добавляем к текущему ответу уже посчитанную динамику. В конце надо разделить на k - каждое дерево мы учли столько раз, сколько в нём тупиков (k).
C. Лягушонок
Вторая, как мне кажется, по сложности задача. Если вам сразу было неочевидно решение, можно было написать полный перебор всех перестановок с проверкой, запустить его для n=10 и увидить красивый ответ. Ответ такой: 1 n 2 (n-1) 3 (n-2) 4 (n-3) ... Как выводить: заведём два указателя - l и r. Первый вначале указывает на 1, второй - на n. На нечётных позициях выводим l, и увеличиваем его на 1, на нечётных - r, уменьшая его на 1. Всё это до тех пор, пока l <= r.
Доказать корректность тоже очень просто: каждый следующий прыжок строго короче, чем предыдущий.
Доказать корректность тоже очень просто: каждый следующий прыжок строго короче, чем предыдущий.
D. Физкультура
Задача, опять же - "бревно". Сначала научимся двигать элемент с номером x на место y (y < x). Как это сделать? Давайте сначала подвинем x на место x - 1 одной очевидной заменой. Еще одной заменой - на место x - 2. И так далее.
Теперь добъёмся a1=b1. Как это сделать? Очевидно, найти в b элемент, равный a1, и, как мы умеем, передвинуть его на первое место. Далее точно так же добъёмся a2=b2. Таким образом, у нас будет n шагов и в каждом мы делаем не более n-1 перестановки. Т.к. n<=300, то n(n-1)<=89700<106.
Теперь добъёмся a1=b1. Как это сделать? Очевидно, найти в b элемент, равный a1, и, как мы умеем, передвинуть его на первое место. Далее точно так же добъёмся a2=b2. Таким образом, у нас будет n шагов и в каждом мы делаем не более n-1 перестановки. Т.к. n<=300, то n(n-1)<=89700<106.
B. Фотография в блог
Из-за бага в GCC на этой задаче я потерял минут 25. В конце концов сдал решение на MSVC++.
Но это было отступление, теперь к делу.
Для начала давайте переберём одну сторону (ту, которая является степенью двойки). Так как сторон две, а писать два раза кусок кода не хочется, давайте сделаем внешний for от 1 до 2, и в релаксации ответа и проверке границ на втором шаге будем менять w и h местами. Это избавит нас от лишнего куска кода.
Итак, перебрали, положим, h=2x. Теперь надо найти такое w, что 0.8 <= h/w <= 1.25. Решим относительно w и получим, что h/1.25 <= w <= h/0.8. Т.к. w - целое, то оно может лежать в диапазоне от ceil(h/1.25) до floor(h/0.8) включительно. Т.к. надо максимизоровать площадь и h фиксированно, надо максимизировать w. Надо взять w=floor(h/0.8) и проверить, что оно подходит. Если да - прорелаксировать ответ.
Итого решение разботает за O(log2 h), что безповоротно вкладывается в TL.
Возможные косяки были:
- Считаете площадь либо в 32-битном типе, либо как: int w = ..., h = ...; long long s = w * h; В этом случае компилятор сначала посчитает w * h в 32-битном типе, а потом приведёт к long long. Лечилось так: s = (long long)w * h;
- floor(0.9999999999)=0. Функция floor не учитывает погрешность. Лечилось дополнительной проверкой, что разница между результатом floor и изначальным значением не превосходит 1 - eps.
- p.s. Функция floor работает до 8-9 раз дольше преобразования к int'у.
E. Тупики
Первое, что надо было заметить - n <= 10. Это значит, что решение экспоненцеальное, и можно перебирать какие-нибудь подмножества. Так и сделаем.
Давайте посчитаем динамику по подмножествам: d[m][subm] - количество способов сделать связанное дерево из подграфа m с тупиковыми вершинами subm. Ответ будет суммой по d[2n-1][x], где кол-во единичных бит в x = k.
Как пересчитывать: для пустого множества и множества из двух вершин (либо 0, либо 1) - очевидно. Одного тупика в дереве не бывает вообще. Теперь для большего: переберём i из subm - какой-нибудь тупик. Отрежем его от дерева по некоторому ребру в b (причём b не должно быть тупиком, иначе получится несвязный граф). Получаем дерево на меньшем множестве вершин и с либо уменьшенным на 1 множеством тупиков, либо с изменённым i на b (если у b было ровно два соседа) Добавляем к текущему ответу уже посчитанную динамику. В конце надо разделить на k - каждое дерево мы учли столько раз, сколько в нём тупиков (k).
У меня просто не хранятся все ответы, а релаксируются по очереди.
?
Could someone help me to explain why we can get correct/unrepeated answer if we add a new point linked by points which belong to the original graph and has number smaller than any leaf node?