Добрый день, уважаемые друзья!
Начиная с этого дня, в рамках подготовки к олимпиадам открывается курс алгоритмического самоспасения. На данный момент к нему присоединились 6 человек, однако количество мест не ограничено. Все определяется вашим желанием достичь успеха в олимпиадном программировании и приложить к этому максимум своих персональных усилий.
Каждый участник курса должен создать аккаунт на сайте codeforces.com, где будут проходить подготовительные соревнования в рамках специально созданной группы. Подавайте заявки на вступление прямо на сайте!
В качестве первого задания олимпийцам следует принять участие в завтрашнем контесте, прочитать разбор и дорешать нерешенные задачи. Также до воскресенья следует посмотреть две лекции Андрея Станкевича 1, 2, по темам которых в нашей группе будет проведен 3-часовой индивидуальный контест в воскресенье, 25 ноября в 12:00. Разбор задач будет опубликован под этом постом.
В качестве дополнительного задания следует зарегистрировать свою команду на онсайт-контест Proggy-Baggy, намеченный на субботу, 1 декабря, обнаружить его место проведения — офис Data-Art (предположительно в комплексе стадиона «Черноморец») и принять в нем активное участие.
Также следует зарегистрироваться на сайте topcoder.com и участвовать во всех личных контестах, проводимых там и на codeforces по мере их появления.
С 1 декабря объявляется бессрочный timus-марафон — личное соревнование по количеству сданных задач на платформе acm.timus.ru, промежуточные итоги которого будут проводиться ежемесячно. Для участия в нем следует создать аккаунт на тимусе и сообщить мне имя пользователя. Победителям, как водится, почет, слава и уважение.
Возникающие вопросы по задачам и командной тактике можно адресовать мне лично, либо выносить на обсуждение под постами данной тематики.
Соревнование завершено.
https://codeforces.com/group/lHcDBNiQRE/contest/233422/standings/groupmates/true
По его результатам:
Зиновьев Андрей 7 задач, штраф 899
Масальский Руслан 2 задачи, штраф 71
Бебик Владислав 2 задачи, штраф 102
Лозинский Дмитрий 1 задача, штраф 143
Еще двое заявленных студентов не смогли принять участие в соревновании. В любом случае, напоминаю, что основной формой обучения является добивание не решенных задач. За подсказками можно обращаться к Андрею, сдавшему на данный момент 8 задач контеста из 9. 9-ю пока никто не сдал, хотя это задача строго по лекции.
Нужно просто реализовать кучу и операции добавления, запроса минимума и удаления. Когда значение минимума не соответсвует запрошенному во вводе элементу, нужно либо такой элемент добавить, если он меньше текущего минимума, либо выталкивать элементы из кучи (и в конце добавить новый при необходимости), если найденный минимум меньше требуемого.
Ожидаю увидеть у всех шестерых участников к субботе по 9 сданных задач.
Очень рад, что продвигается обучение. Желаю дальнейших успехов. Наверное, имеет смысл упомянуть в группе Google факультатива об этом направлении.
Разбор. A. ЛНПП
Заметим, что при выборе лексикографически максимальной подпоследовательности следует всегда действовать жадно. Действительно, строка, начинающаяся на z будет всегда больше строки, начинающейся на y. Значит, наша подпоследовательность должна начинаться с максимальной буквы, содержащейся в строке. Из условий палиндромности следует, что и заканчиваться она должна самой большой буквой строки.
Теперь заметим, что если между двумя максимальными буквами затесалась какая-то не максимальная, то, выкинув ее, получим большую строку. Отсюда следует, что в нашу подпоследовательность должны входить только максимальные буквы строки и никакие другие. И их нужно собрать как можно больше — это тоже следует из определения лексикографического порядка.
Таким образом, достаточно собрать все буквы, равные максимальной букве строки. Сложность решения $O(n)$.
Разбор. B. Ранклист
В данной задаче требуется создать структуру «команда» и описать для нее компаратор, с помощью которого отсортировать все команды. Можно воспользоваться std::pair и хранить там пары вида {-problemsCount, time}, тогда можно сортировать стандартным компаратором. Дальше остается отсортировать команды и найти количество записей, в точности равных k-й. Сложность решения $O(n*log n)$.
Разбор. C. Вырезание массива
Для решения задачи будем подбирать такое максимально возможное число x, что из массива s можно собрать x одинаковых массивов t длины хотя бы k. Заметим, что если условие задачи выполняется для x = r, то оно выполняется и для x = r — 1. Для перехода от r к r — 1 можно просто выкинуть одну из копий массива t. То есть условие подходящести числа x монотонно по x. А значит задачу можно решать бинарным поиском по ответу.
Заметим, что при фиксированном x, число i может входить в массив t $[count_i / x]$ раз, где $count_i$ — число вхождений числа i в массив s. Действительно, если мы хотим поделить $count_i$ чисел на x равных групп и выкинуть остаток, то в одной из них не может быть больше, чем $[count_i / x]$ таких чисел. Значит, максимально возможная длина массива t в нашем случае равна $sum_i([count_i / x])$. В нашем бинарном поиске если для текущего x $sum_i([count_i / x]) < k$, мы сдвигаем границу поиска влево, иначе — вправо.
Сложность решения $O(n * log|A|)$, где A — диапазон поиска ответа.
Разбор. D. Покидая ферму
Сохраним только номера свободных комнат. Тогда очевидно, что нужно заселять коров и фермера в k+1 комнат, содержащихся в этом множестве подряд. Всего таких отрезков [roomfirst; roomlast] не более, чем n-k. Для каждого из них фермера нужно селить в комнату, максимально близкую к центру отрезка [roomfirst; roomlast], то есть к комнате с номером (roomfirst+roomlast)/2. Сама такая комната может быть занята, зато мы можем найти ближайшую к ней бинарным или тернарным поиском, а также с помощью техники двух указателей. В первом случае сложность алгоритма $O(n*log n)$, во втором — $O(n)$.
Разбор. E. Письма
Найдем для каждого общежития i сквозной номер последней квартиры $c_i$, находящейся в нем. Это можно сделать по формуле: $$c_1 = a_1$$ $$c_i = a_i + c_(i-1)$$ Тогда верно, что если $c_(i-1) < b_j <= c_i$, то квартира с номером $b_j$ находится в общежитии номер i и соответствует в нем квартире номер $b_j — c_(i-1)$. Находить подходящее значение i можно бинарным поиском или техникой двух указателей. Сложность алгоритма $O(n*log n)$ и $O(n)$ соответственно.
Разбор. F. Мафия
Заметим, что искомое число раундов не может быть меньше, чем $max(a_i)$. Кроме того, заметим, что если мы играем x раундов, то нам потребуется ровно x свободных человекораундов. Например, если x = 4, а a2 = 1, то у второго игрока есть целых 3 свободных человекораунда — он может в течение трех раундов быть ведущим.
Посчитаем суммарное число свободных человекораундов при фиксированном x. Оно равно $sum(x-a_i)=x*n-sum(a_i)$. Если это число не меньше x, то x — подходящее число раундов, в противном случае — нет. Здесь можно применить описанную выше технику бинарного поиска по ответу за $O(nlog n)$, либо продолжать анализировать.
Запишем условие для x: $$ x * n — sum(a_i) ≥ x$$ $$x*(n-1) ≥ sum(a_i)$$
$$x ≥ sum(a_i)/(n-1)$$
Таким образом, значение x можно вычислить по формуле. Сложность алгоритма $O(n)$
Разбор. G. Перевод заключенных
Данную задачу можно решать, реализовав очередь через два стека, как это было показано в лекции, с возможностью вычисления максимума в очереди за $O(1)$. Будем поддерживать в очереди ровно c преступников, добавляя и удаляя их по одному в порядке следования в шеренге. Тогда если максимум на этом отрезке нас удовлетворяет, увеличим ответ на 1, иначе ничего с ним не будем делать.
Сложность алгоритма $O(n)$
Разбор. H. Торжественный вечер
Для каждого символа входной строки найдем позиции первого и последнего вхождения этого символа. Первому вхождению поставим в соответствие открывающую скобку, а последнему — закрывающую, остальные символы просто проигнорируем. Если первое вхождение совпадает с последним, то добавим сначала открывающую, а потом тут же закрывающую. Теперь максимальное количество необходимых охранников равно максимальной глубине вложенности этой скобочной последовательности. Сложность алгоритма $O(n)$
Разбор. I. Операции с кучей
В данной задаче следует реализовать структуру данных двоичная куча и выполнять с ней описанные в условии операции. Для каждого запроса:
1) Если текущий минимум m равен ожидаемому в запросе x, то ничего дополнительно делать не надо.
2) Если $m > x$, добавим перед текущей операцией операцию добавления ожидаемого минимума x.
3) Если же m < x, то будем удалять из кучи минимум до тех пор, пока она не опустеет, либо пока минимум не станет больше либо равен x. После этого перейдем к пунктам 1-2.
Сложность алгоритма $O(n * log n)$