Обозначим персонажей по первой букве имени. Очередь имеет вид: Ш-Л-П-Р-Г, через 5 баночек: Ш-Ш-Л-Л-П-П-Р-Р-Г-Г, еще через 10 баночек: Ш-Ш-Ш-Ш-Л-Л-Л-Л-П-П-П-П-Р-Р-Р-Р-Г-Г-Г-Г.

Закономерность ясна, и решение очень простое: будем итерироваться по p - найдем такое минимальное p, что 5· 2^p > n (при этом, если это число меньше или равно, то вычтем из n его), тогда мы знаем, что у нас сначала стоят 2^p Шелдонов, потом 2^p Леонардов и так далее.  И теперь мы можем легко ответить, кто же взял баночку номер n (а именно это был человек с номером n / 2^p в массиве Ш-Л-П-Р-Г (в 0-индексации).

Для решения нам понадобится следующий важный факт: допустим элементы v и u находятся в одном множестве, тогда в любой из n· (n - 1) / 2 последовательностей из входных данных, где встречается v обязательно встречается u. А также, если v и u --- в разных множествах, то существует такая последовательность, в которой есть v, но нет u. Тогда можно ввести отношение эквивалентности для всех элементов всех множеств --- два элемента эквивалентны, если не существует последовательности, где один элемент встречается, а другой нет. Классы эквивалентности и есть искомые множества.

Считать ответ можно было следующим алгоритмом: выпишем для каждого числа список номеров последовательностей, где встречается это число, и объединим два числа, если эти списки равны. Этот алгоритм можно реализовать за O(n² * log(n)), впрочем, решение за O(n³)

тоже проходит все тесты с большим запасом времени.

Особый случай - это тест с n = 2. Именно этот тест использовался для большого количества взломов.

Сначала оценим сверху максимальное время, к которому все дивизии доберутся до столицы - очевидно, для этого требуется не более n дней. Поэтому ограничения вполне позволяли промоделировать движения дивизий. Ключевой момент решения - будем всегда рассматривать дивизии в порядке приоритета. Тогда в каждый день рассмотрим список тех дивизий, кто еще не дошел до столицы, и в порядке приоритета будем сажать на нужный поезд. Если поезд уже заполнен, то дивизия остается в текущем городе, иначе изменим ее положение, и в день, когда дивизия доберется до столицы запишем ответ. Итого: всего дней, которые нужно промоделировать, не более n, и каждый день мы передвигаем не более n дивизий. Значит, наше решение имеет асимптотику не более O(n²). 

Решения, использующие различные структуры данных (сеты, очереди с приоритетами и т.д.), работают за O(n²· log(n)), и это не всегда укладывалось в TL.

Задача решается динамическим программированием. Рассмотрим состояние (i, j), означающее, что в текущей очереди стоит человек номер i, а также все люди от j до n включительно. Любая очередь, достижимая из начальной, может быть представлена соответствующим состоянием. Количество состояний - O(n²), количество переходов - всего 3, то есть O(1). Значит, итоговая асимптотика - O(n²).

Эта задача имеет несколько решений, основанные на различных методах поиска площади объединения фигур на плосткости. Одним из таких методов является метод вертикальной декомпозиции (подробнее Вы можете почитать в различных статьях), а также можно было заметить, что среди фигур не существует трех, имеющих ненулевое пересечение, и поэтому достаточно было научиться находить общую площадь двух фигур. Для этого также можно было использовать различные методы, например, авторское решение основано на алгоритме отсечения выпуклого многоугольника полуплоскостью. Авторами предполагалось решение за O(n²).