By MikeMirzayanov, 9 years ago, In Russian

522A - Reposts

Для решения этой задачи надо было проитерироваться по записям о репостах и поддерживать для каждого пользователя длину цепочки, которая заканчивается в нем. Здесь удобно воспользоваться ассоциативным массивом из строки (имени пользователя) в целое число (длину цепочки). Например, для С++ такой структурой данных будет просто map<string,int>. Назовем такую структуру chainLengths, тогда при обработки строки вида <<a reposted b>> надо просто выполнить присвоение chainLengths[a] = chainLengths[b] + 1. В качестве ответа надо вывести максимальное из значений chainLengths, что можно подсчитывать на лету.

Пара тонкостей: в начале надо занести chainLengths["polycarp"] = 1;, а всюду при работе со строками приводить их к нижнему регистру (или верхнему), чтобы сделать сравнение строк нечувствительным к регистру букв.

Пример такого решения: 10209456.

522B - Photo to Remember

В этой задаче для каждого i фактически надо было найти:

  • Wi, равное сумме всех заданных wj без wi,
  • и Hi, равное максимуму всех hj без hi.

Для подсчета первой величины достаточно найти сумму s всех значений wj, тогда Wi = s - wi.

Для подсчета второй величины достаточно заметить, что либо искомое значение есть просто максимум по h, либо (если hi совпало с максимумом) это второй максимум (т.е. предпоследний элемент при сортировке по неубыванию). Второй максимум, как и максимум ищется за один проход по массиву.

В таком случае, для нахождения как Wi, так и Hi требуется O(1) действий, то есть O(n) суммарно на всё решение.

Пример решения: 10193758.

522C - Chicken or Fish?

Для решения задачи необходимо заметить, что при наличии недовольных пассажиров (т.е. тех, для кого ri = 1), существенную роль играет только первый из них, так как остальные вполне могут быть недовольными именно тем блюдом, которое не хватило первому из таковых.

Пусть массив b — это массив максимальных возможных количеств порций каждого из блюда на момент старта обслуживания Поликарпа. То есть просто массив b надо заинициализировать массивом a, а каждый раз, когда ti отлично от 0, то делать b[ti] = b[ti] - 1 (уменьшать количество порций блюда). Кроме того, пусть unknown — это количество пассажиров, про которых неизвестно какие точно блюда им достались (то есть для них ti = 0). Пусть величина unknownBeforeUpset — это такое же количество, но до первого недовольного.

Таким образом, есть два основных случая:

  • недовольных пассажиров нет вообще, тогда блюдо i могло закончится тогда и только тогда, когда b[i] ≤ unknown (жадно отдаем это блюдо всем пассажирам, для кого их точное блюдо неизвестно),
  • недовольный пассажир есть, этот случай разберем подробнее.

Каким блюдом мог быть недоволен первый из таких пассажиров? Очевидно из списка кандидатов надо выкинуть все такие блюда, которые упоминаются не раньше него (значит, что они закончится до него не могли). Из оставшегося набора блюд достаточно перебрать все блюда и проверить могли ли они закончиться до этого пассажира. То есть блюдо i могло быть тем блюдом, что привело в недовольство первого недовольного, если одновременно верно:

  • это блюдо i не упоминается на этом пассажире или позже,
  • это блюдо i такое, что b[i] ≤ unknownBeforeUpset.

Для всех таких блюд, очевидно, в ответе должно стоять Y (они могли закончится к Поликарпу). Кроме того, из всех таких блюд наибольшую степень свободы дает блюдо с наименьшим расходом (количеством порций b[i]). Выберем именно такое блюдо и в остаток пассажиров с неизвестным блюдом restUnknown = unknown - b[minFirstFinished] попробуем поместить все вхождения каждого из других блюд. То есть блюдо j могло закончится до Поликарпа тогда и только тогда, если для него b[j] ≤ restUnknown (то есть закончилось то блюдо, что расстроило первого из недовольных, а следом — j-е).

Такое решение работает за O(m + k).

Пример решения: 10212686.

522D - Closest Equals

Воспользуемся тем, что задача задана в офлайн-формулировке, то есть все запросы можно считать до нахождения ответов на них.

Пройдем слева направо по массиву и составим новый массив b, записав в b[j] расстояние до ближайшего слева парного j-му элементу значения, то есть a[j - b[j]] = a[j]. Если такового нет, то запишем в ячейку бесконечность.

Эти значения соответствуют расстояниям между парными элементами и записаны они в позициях правых элементов в этих парах.

При рассмотрении запроса на отрезке [l, r] нам не нужны вообще такие пары, что начинаются левее l, а минимум надо искать среди пар, что заканчиваются не правее r.

Отсортируем все запросы по l слева направо. Тогда при прохождении по запросам можно поддерживать, что для запроса [l, r] в массиве b установлены бесконечности для всех пар, в которых левый элемент левее l. Для этого просто предподсчитаем для каждого элемента ближайший справа парный next[i] (то есть верно, что b[next[i]] = next[i] - i), и при покидании ячейки i будем записывать в b[next[i]] значение бесконечность.

В таком случае, для ответа на запрос [l, r] надо просто найти минимум на префиксе до индекса r включительно по массиву b. Это можно делать быстро разными способами (дерево отрезков, дерево Фенвика).

Асимптотическая временная сложность такого решения составляет .

Пример решения: 10192075.

  • Vote: I like it
  • +35
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

English translated version of D (in case anyone wants to refer to it but refrains due to language :) )

We will use the fact that the task is set in an offline wording, that is, all requests can be counted until answers to them are found.

We will go through the array from left to right and compose a new array b, writing in b [j] the distance to the nearest left jth element of the value, that is, a [j — b [j]] = a [j]. If there is none, then we write infinity into the cell.

These values correspond to the distances between paired elements and they are recorded in the positions of the right elements in these pairs. When considering a request on the segment [l, r], we don’t need at all such pairs that begin to the left of l, and we must look for the minimum among the pairs that end not to the right of r.

Sort all queries by l from left to right. Then, when passing through queries, it can be maintained that for query [l, r] in array b infinities are set for all pairs in which the left element is to the left of l. To do this, we simply calculate for each element the next pairwise next [i] on the right (that is, it is true that b [next [i]] = next [i] — i), and when leaving cell i we will write in b [next [i]] meaning infinity.

In this case, to answer the query [l, r], you just need to find the minimum on the prefix to the index r inclusively in the array b. This can be done quickly in different ways (tree of segments, Fenwick tree). The asymptotic time complexity of such a solution is.