Как говорится, лучше поздно, чем никогда. Ниже публикуется разбор тренировочного соревнования, прошедшего ранее.
Разбор представлен в виде описания идей решения задач, код предлагается написать самостоятельно. Рекомендуемый язык для решения предложенных задач — C++.
A. Катя и сборы
Для решения данной задачи достаточно вывести комбинаторную формулу, позволяющую вычислить количество различных наборов одежды. У Кати (с учётом надетой во время поездки одежды) есть $$$n+1$$$ футболок и $$$m+1$$$ джинсов. Тогда, в соответствии с правилом умножения, у неё есть $$$(n+1)*(m+1)$$$ наборов одежды. Дальше остаётся только проверить при помощи условного оператора, превосходит ли число дней сборов $$$k$$$ данную величину и вывести соответствующий ответ.
B. Пополнение гардероба
В этой задаче у участников проверялись навыки работы со структурами данных. В связи с тем, что ограничения на входные значения были достаточно "добрыми", подходила практически любая структура данных.
Решение 1. Самым простым вариантом было использовать структуру данных "множество" (std::set в C++): а именно, завести (изначально пустое) множество номеров футболок и затем идти по номерам футболок слева направо и осуществлять проверку на то, находится ли текущий номер футболки во множестве. Если да — выводить "0", иначе выводить "1" и добавлять футболку в множество.
Решение 2. Вторым вариантом было использование числового массива. Общая идея состоит в том, что изначально массив пуст, а затем в него добавляются номера уже рассмотренных футболок (как и в первом решении, футболки рассматриваются слева направо). Для проверки, встречалась ли футболка с номером, равным текущему, необходимо пройти по заполненной части массива (для $$$i$$$-й рассматриваемой футболки необходимо рассмотреть первые $$$i-1$$$ элементов) и определить, находится ли там хотя бы одна футболка с нужным номером (например, при помощи флага: https://ru.wikipedia.org/wiki/Флаг_(компьютерная_техника) ). Вместо обычного массива так же можно было использовать динамический массив (или std::vector в C++).
Решение 3. Наиболее необычным вариантом решения было использование структуры данных, позволяющей оптимально по памяти хранить набор битовых значений: например, такой структурой является std::vector< bool > в C++. Суть идеи состоит в том, чтобы заполнить изначально все элементы нулями, а затем ставить единицу по индексу, соответствующую номеру текущей футболки. Для проверки того, встречалась ли футболка ранее, достаточно предварительно проверить, находится ли в этой ячейке 0 или 1. Оптимальность по памяти в данном случае подразумевает, что для хранения одного битового значения расходуется 1 бит памяти в противоположность 1 байту памяти (что было бы, например, при использовании в C++ обычного массива типа bool): благодаря этому, такое решение использует лишь около 120 MB памяти даже при ограничении на номера футболок $$$1 \leq a_i \leq 10^9$$$.
C. Ваня и тетради
В данной задаче использовались идеи сортировки и жадного алгоритма. Общая мысль такова: расположим все тетради (из всех магазинов) в порядке роста цены, а затем будем покупать их по очереди, начиная с самой дешёвой (пока не закончатся деньги).
Решение 1. Воспользоваться любым алгоритмом сортировки, работающим за $$$O(n*log(n))$$$ (например, сортировкой слиянием), для набора магазинов. При этом сортировка должна быть реализована таким образом, чтобы сравнение магазинов происходило на основании цены в магазине $$$a_i$$$, но при этом при сортировке сохранялась информация о количестве $$$b_i$$$ тетрадей в этом магазине, т.е. сортировались пары $$$(a_i, b_i)$$$. В частности, в C++ можно было воспользоваться структурой данных std::vector<std::pair<int, int>> и применить к ней std::sort. Далее остаётся только идти по магазинам в порядке роста цен в них и покупать максимально возможное количество тетрадей, обновляя количества купленных тетрадей и оставшихся монет.
Решение 2. Второй вариант решения состоит в использовании идеи сортировки подсчётом. Заведём массив целых чисел размера $$$10^6$$$ — по ячейке на каждый возможный вариант цены одной тетради, заполним его нулями, а затем просто будем увеличивать значение соответствующей ячейки при рассмотрении по очереди всех магазинов. Зная количество тетрадей каждой возможной стоимости, просто пройдём по нашему массиву в порядке роста стоимости, покупая максимально возможное количество тетрадей на каждом шаге.
Так же стоит отметить, что для решения задачи в ряде мест необходимо было использовать целочисленные переменные, поддерживающие работу с числами до $$$10^{18}$$$ (например, long long int в C++).
D. Тыквенная магия
К этой задаче есть два принципиально разных подхода.
Решение 1. Заметим, что если из тыквы некоторого размера можно получить тыкву размера $$$m$$$ путём применения заклинаний, то можно составить так же и набор заклинаний (позволяющий добиться того же самого), в котором все заклинания "увеличить в $$$k$$$ раз" находятся перед заклинаниями "увеличить на $$$p$$$" (т.е. сначала применяются только заклинания одного вида, а потом только второго). Доказательство этого факта такое: рассмотрим некоторую цепочку заклинаний, содержащую хотя бы одно заклинание увеличения на $$$p$$$. Оказывается, что эта цепочка эквивалентна другой цепочке, из которой удалено это заклинание, но добавлено применение в конце $$$k^s$$$ заклинаний увеличения на $$$p$$$, где $$$s$$$ — количество заклинаний увеличения в $$$k$$$ раз, находившихся после удалённого заклинания. Из этого очевидным образом вытекает конструктивный алгоритм получения цепочки описанного выше вида.
Далее, оказывается, что возможно быстро (за $$$O(1)$$$) проверить, можно ли из тыквы одного заданного размера получить тыкву другого (не меньшего) заданного размера, пользуясь лишь заклинанием увеличения на $$$p$$$: достаточно сравнить остатки от деления размеров на $$$p$$$ (они равны тогда и только тогда, когда переход возможен).
Пользуясь этими двумя фактами, приходим к решению: будем брать каждую тыкву по очереди и увеличивать её в $$$k$$$ раз до тех пор, пока её размер не окажется большим $$$m$$$. Перед каждым увеличением так же будем проверять, можно ли из тыквы текущего размера получить тыкву размера $$$m$$$, пользуясь только заклинаниями увеличения на $$$k$$$. Асимптотика решения — $$$O(n*log(m))$$$.
Решение 2. Воспользуемся идеями динамического программирования. Пусть $$$dp[i]$$$ равно 1, если из тыквы размера $$$i$$$ можно получить тыкву размера $$$m$$$ и равно 0 в противном случае. Тогда имеем базу динамики вида $$$dp[m]=1; dp[k]=0, \forall k>m$$$. Формула перехода может быть записана как $$$dp[i]=max(dp[i+p], dp[i*k])$$$.
Итого, достаточно предварительно вычислить значения динамики для всех возможных $$$i$$$ и затем за $$$O(1)$$$ выводить ответ для каждой тыквы. Общая асимптотика — $$$O(m+n)$$$.
E. Ваня и параллельные миры
Данная задача является обобщением задачи C, однако обладает изменёнными ограничениями. В следствие этого, в ней неприменима идея сортировки подсчётом в рассмотренном виде (т.к. увеличено верхнее ограничение $$$a_i$$$; тем не менее, её использование возможно при использовании аналога std::map C++ вместо массива, что однако не рассматривается далее), а общая стоимость всех тетрадей во всех магазинах может достигать $$$4*10^{18}$$$ (что по-прежнему укладывается в long long int).
Решение 1. Воспользуемся идеями префиксных сумм и бинарного поиска. Отсортируем магазины по росту стоимости тетради, затем посчитаем префиксные суммы (а именно, суммарную стоимость всех тетрадей в магазине от первого до текущего включительно, а так же суммарное количество тетрадей в магазине от первого до текущего) для всех магазинов. Далее будем для каждого количества монет при помощи бинарного поиска (например, std::upper_bound в C++) находить максимальную из префиксных сумм (суммарных стоимостей), не превосходящую имеющегося количества монет. Тогда ответом для текущего количества монет будет сумма соответствующей префиксной суммы (числа тетрадей) и количества тетрадей, которое мы можем приобрести в следующем после крайнего в префиксной сумме магазина (если он существует).
Асимптотика решения: $$$O((n+m)*log(n))$$$.
Решение 2. Воспользуемся идеей двух указателей: один будет двигаться по количествам монет, а второй — по магазинам. Отсортируем магазины по росту стоимости тетради, отсортируем количества монет в порядке возрастания, поставим оба указателя на начала получившихся массивов, а затем будем двигаться по количествам монет слева направо и на каждом шаге сдвигать указатель в массиве магазинов вправо до тех пор, пока мы можем купить все тетради в текущем магазине (при этом поддерживая количество оставшихся монет, увеличивая его при сдвиге по массиву числа монет и уменьшая при сдвиге по массиву магазинов). Ответ для каждого числа монет при этом может быть получен путём суммирования числа тетрадей во всех рассмотренных магазинах (его так же необходимо поддерживать при сдвиге указателей) и числа тетрадей в следующем магазине, которое возможно приобрести на остаток монет.
Для восстановления порядка ответов, возможно, например, сортировать не массив количеств монет, а массив пар (количество монет; индекс в исходном массиве).
Асимптотика решения: $$$O(m*log(m)+n*(log(n))$$$ (при этом часть после сортировок займёт лишь $$$O(n+m)$$$).
Стоит так же отметить, что (в обоих вариантах решения) при вычислении числа тетрадей, которое можно приобрести в крайнем магазине, следует пользоваться делением, а не циклом (в противном случае, возможен TL).
F. Айландлэнд
Последняя задача контеста связана со структурой данных СНМ (системой непересекающихся множеств) и является обобщением упрощённого варианта задачи динамической связности оффлайн. Решение удобно изложить в терминах этой структуры данных.
Элементами наших множеств являются острова, а связи между ними определяются мостами. Для того, чтобы решить задачу, необходимо поддерживать для каждого острова информацию о том, есть ли на нём жители (достаточно массива bool), а так же для каждого множества островов (это удобно хранить у представителя множества) информацию о количестве населённых в этом множестве островов (для того, чтобы отсекать множества, на которых никто не живёт).
Таким образом, решение сводится к написанию модифицированного СНМ, в котором:
1) При донесении первого вида происходит объединение двух множеств (если мостом соединяются острова из разных множеств).
2) При донесении второго вида происходит только обновление информации о населённости островов и количества населённых во множествах островов (тут есть некоторый подвох: а именно, в донесении может прийти информация про переселение с пустого на пустой остров).
3) После донесения любого вида сообщается количество множеств, в каждом из которых есть хотя бы один заселённый остров (эта информация так же должна поддерживаться при каждом обновлении СНМ).
При этом ограничения в задаче таковы, что достаточно написать СНМ хотя бы с асимптотикой $$$O(log(n))$$$ на запрос (т.е. достаточно применения одной из двух классических эвристик). В то же время, в ряде языков потребуются действия, направленные на ускорение ввода (например, вызов ios::sync_with_stdio(0) в начале программы в случае работы с потоками ввода-вывода в C++).
Так же эту задачу представляется возможным решить другими подходами. Например, при помощи корневой декомпозиции: рассматривать острова и мосты как граф, разбить запросы на блоки примерно по $$$\sqrt{q}$$$, решать задачу внутри каждого блока при помощи DFS или BFS, а в конце блока перестраивать граф, сжимая каждую компоненту связности в одну вершину (в то время как применение DFS или BFS без корневой декомпозиции непременно привело бы к TL). Тем не менее, подобное решение выглядит чрезмерно сложным и не рассматривается в качестве сравнимого альтернативного решения данной задачи (и, в том числе, не было до конца продумано и реализовано авторами).
На этом разбор можно считать законченным. Спасибо всем за участие в контесте!
