[Базовый олимпиадный курс] Занятие 1. Сложность алгоритмов, сортировка и поиск

Добрый день, уважаемые друзья!

Начиная с этого дня, в рамках подготовки к олимпиадам открывается курс алгоритмического самоспасения. На данный момент к нему присоединились 6 человек, однако количество мест не ограничено. Все определяется вашим желанием достичь успеха в олимпиадном программировании и приложить к этому максимум своих персональных усилий.

Каждый участник курса должен создать аккаунт на сайте codeforces.com, где будут проходить подготовительные соревнования в рамках специально созданной группы. Подавайте заявки на вступление прямо на сайте!

В качестве первого задания олимпийцам следует принять участие в завтрашнем контесте, прочитать разбор и дорешать нерешенные задачи. Также до воскресенья следует посмотреть две лекции Андрея Станкевича 1, 2, по темам которых в нашей группе будет проведен 3-часовой индивидуальный контест в воскресенье, 25 ноября в 12:00. Разбор задач будет опубликован под этом постом.

В качестве дополнительного задания следует зарегистрировать свою команду на онсайт-контест Proggy-Baggy, намеченный на субботу, 1 декабря, обнаружить его место проведения — офис Data-Art (предположительно в комплексе стадиона «Черноморец») и принять в нем активное участие.

Также следует зарегистрироваться на сайте topcoder.com и участвовать во всех личных контестах, проводимых там и на codeforces по мере их появления.

С 1 декабря объявляется бессрочный timus-марафон — личное соревнование по количеству сданных задач на платформе acm.timus.ru, промежуточные итоги которого будут проводиться ежемесячно. Для участия в нем следует создать аккаунт на тимусе и сообщить мне имя пользователя. Победителям, как водится, почет, слава и уважение.

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

Олег Петров

Software Engineer at Snap Inc.
Los Angeles, California

11 thoughts on “[Базовый олимпиадный курс] Занятие 1. Сложность алгоритмов, сортировка и поиск

  1. Соревнование завершено.
    https://codeforces.com/group/lHcDBNiQRE/contest/233422/standings/groupmates/true
    По его результатам:
    Зиновьев Андрей 7 задач, штраф 899
    Масальский Руслан 2 задачи, штраф 71
    Бебик Владислав 2 задачи, штраф 102
    Лозинский Дмитрий 1 задача, штраф 143

    Еще двое заявленных студентов не смогли принять участие в соревновании. В любом случае, напоминаю, что основной формой обучения является добивание не решенных задач. За подсказками можно обращаться к Андрею, сдавшему на данный момент 8 задач контеста из 9. 9-ю пока никто не сдал, хотя это задача строго по лекции.

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

    Ожидаю увидеть у всех шестерых участников к субботе по 9 сданных задач.

  2. Очень рад, что продвигается обучение. Желаю дальнейших успехов. Наверное, имеет смысл упомянуть в группе Google факультатива об этом направлении.

  3. Разбор. A. ЛНПП

    Заметим, что при выборе лексикографически максимальной подпоследовательности следует всегда действовать жадно. Действительно, строка, начинающаяся на z будет всегда больше строки, начинающейся на y. Значит, наша подпоследовательность должна начинаться с максимальной буквы, содержащейся в строке. Из условий палиндромности следует, что и заканчиваться она должна самой большой буквой строки.

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

    Таким образом, достаточно собрать все буквы, равные максимальной букве строки. Сложность решения $O(n)$.

  4. Разбор. B. Ранклист

    В данной задаче требуется создать структуру «команда» и описать для нее компаратор, с помощью которого отсортировать все команды. Можно воспользоваться std::pair и хранить там пары вида {-problemsCount, time}, тогда можно сортировать стандартным компаратором. Дальше остается отсортировать команды и найти количество записей, в точности равных k-й. Сложность решения $O(n*log n)$.

  5. Разбор. 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 — диапазон поиска ответа.

  6. Разбор. D. Покидая ферму

    Сохраним только номера свободных комнат. Тогда очевидно, что нужно заселять коров и фермера в k+1 комнат, содержащихся в этом множестве подряд. Всего таких отрезков [roomfirst; roomlast] не более, чем n-k. Для каждого из них фермера нужно селить в комнату, максимально близкую к центру отрезка [roomfirst; roomlast], то есть к комнате с номером (roomfirst+roomlast)/2. Сама такая комната может быть занята, зато мы можем найти ближайшую к ней бинарным или тернарным поиском, а также с помощью техники двух указателей. В первом случае сложность алгоритма $O(n*log n)$, во втором — $O(n)$.

  7. Разбор. 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)$ соответственно.

  8. Разбор. 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)$

  9. Разбор. G. Перевод заключенных

    Данную задачу можно решать, реализовав очередь через два стека, как это было показано в лекции, с возможностью вычисления максимума в очереди за $O(1)$. Будем поддерживать в очереди ровно c преступников, добавляя и удаляя их по одному в порядке следования в шеренге. Тогда если максимум на этом отрезке нас удовлетворяет, увеличим ответ на 1, иначе ничего с ним не будем делать.

    Сложность алгоритма $O(n)$

  10. Разбор. H. Торжественный вечер

    Для каждого символа входной строки найдем позиции первого и последнего вхождения этого символа. Первому вхождению поставим в соответствие открывающую скобку, а последнему — закрывающую, остальные символы просто проигнорируем. Если первое вхождение совпадает с последним, то добавим сначала открывающую, а потом тут же закрывающую. Теперь максимальное количество необходимых охранников равно максимальной глубине вложенности этой скобочной последовательности. Сложность алгоритма $O(n)$

  11. Разбор. I. Операции с кучей

    В данной задаче следует реализовать структуру данных двоичная куча и выполнять с ней описанные в условии операции. Для каждого запроса:
    1) Если текущий минимум m равен ожидаемому в запросе x, то ничего дополнительно делать не надо.
    2) Если $m > x$, добавим перед текущей операцией операцию добавления ожидаемого минимума x.
    3) Если же m < x, то будем удалять из кучи минимум до тех пор, пока она не опустеет, либо пока минимум не станет больше либо равен x. После этого перейдем к пунктам 1-2.

    Сложность алгоритма $O(n * log n)$

Добавить комментарий