221A - Маленький Слоник и функция

В этой задаче все что нужно заметить это то, что ответ всегда имеет следующею форму: n, 1, 2, 3, ..., n-1. При такой перестановке не трудно заметить, что после полого выполнения алгоритма перестановка будет отсортирована.

221B - Маленький Слоник и числа

Нужно найти все делители числа n. Это можно сделать простым перебором от 1 до sqrt(n). После этого нужно написать функцию, которая умеет определять, существуют ли две одинаковые цифры в паре чисел. Это тоже можно сделать простым перебором по цифрам.

220A - Маленький Слоник и проблема

Существует несколько решений этой задачи. Например, можно найти максимальное x такое, что существует y (минимальное возможное) такое, что (y < x) и A_x < A_y. После этого остается проверить ровно два варианты — либо менять местами x-е и y-е числа, либо не делать ничего.

220B - Маленький Слоник и массив

Задачу можно решить за O(NsqrtN), но я опишу решение за O(NlogN).

Будем решать задачу в оффлайне, тоесть сначала считаем все запросы, а потом будем давать ответы. Для каждого x (0 ≤ x n) мы должны держать все запросы, концами которых есть x. Будем перебирать x от 0 до n - 1. Также нам нужно поддерживать массив чисел D такой, что для текущего x ответом на запрос [l;x] будет число D_l + D_l + 1 + ... + D_r. Для правильной поддержки массива, перед тем как обрабатывать запросы для текущего x, нудно обновить D. Пусть t — текущее число, тоесть A_x, а вектор P — список индексов всех вхождений числа t (до позиции x), нумерация с 0. Тогда, если |P| ≥ t, нам нужно добавить 1 до D_{P[|P| - t]}, так как эта позиция теперь переломной — после нее будет не меньше чем t вхождений числа t. Потом, если |P| > t, нужно отнять 2 от D_{P[|P| - t - 1]}, для того что-бы закрыть текущий интервал (после этой позиции количество вхождений t будет превосходить t), а также отменить предыдущий. И наконец, если |P| > t + 1, нужно еще добавить 1 к D_{P[|P| - t - 2]} для того что-бы отменить закрытие предыдущего интервала.

220C - Маленький Слоник и сдвиги

Each of the shifts can be divided into two parts — the right (the one that starts from occurrence 1) and the left (the rest of the elements). If we could keep minimal distance for each part, the minimal of these numbers will be the answers for the corresponding shift. Lets solve the problems of the right part, the left will be almost the same.

Let we have some shift, for example 34567[12] and the permutation A is 4312765 and B is 2145673, then shifted B is 4567321. Let we keep two sets (S1 and S2). The first will keep all the distances from integers in current left part to the corresponding positions in A (for the example above, it is [2, 4]). When you come to the next shift, all integers in S1 should be decreased by 1 (that is because all distances are also decreased by 1). But now some integers in set may be negative, when any negative integer occures (it always will be -1) you need to delete it from S1 and put 1 to the S2. Also after shifting to the next shifts, all integers in S2 must be increase by 1. After that, for any shift, the answer will be minimum from the smallest numbers in S1 and S2.

It was very useful to use standart "set" in C++.

220D - Маленький Слоник и треугольник

Давайте переберем все возможные точки нашей плоскости и предположим что это первая точка тройки. Пусть это будет точка (x;y). Пусть вторая и третья точки это (x1;y1) и (x2;y2). Тогда удвоенная площадь равна |(x1 - x)(y2 - y) - (x2 - x)(y1 - y)|. Нам нужно что-бы это число было четным, а также ненулевым. Для начала найдем количество троек, которые образуют четную площадь, а потом отнимем количество точек с нулевой площадью.

Первая подзадача. Так как мы знаем x и y и нам нужно проверить четность, давайте еще переберем все возможные 2⁴ варианты четности x1, y1, x2 и y2 (пусть это d0, d1, d2 и d3, соответственно). Потом проверим будет ли такая тройка чисел формировать 0 после подстановки в формулу площади и взятии по модулю 2. Если это так, тогда нужно добавит к ответу число cx_d0cy_d1cx_d2cy_d3, где cx_d равно количеству целых чисел в промежутке [0..n] таких, что они по модулю 2 равны d. Аналогично для cy_d, только в промежутке [0..m].

Теперь нужно отнять плохие тройки — такие, что треугольник, который они создают, имеет нулевую площадь. Это значит, что тройка точек формирует отрезок (или точку). Так как это отрезок, давайте переберем dx = |x1 - x2| и dy = |y1 - y2|, вместо перебора всех 4 координат. Количество таких отрезков на плоскости равно (n - dx + 1)(m - dy + 1). Также для подсчета количества троек, что формируют такой отрезок, нужно искать количество точек с целыми координатами на плоскости, которые лежат на этом отрезке. Это известная задача — это количество равно gcd(dx, dy) + 1.

Это дает нам, с еще некоторыми оптимизациями, решение за O(nm).

220E - Маленький Слоник, а также инверсии

В этой задачи нужно использовать метод двух указателей. Также нужно использовать RMQ. Если вы не знакомы со структурой данных RMQ, почитать о нем можно здесь.

Для начала, уменьшим все числа, не меняя их относительное значения, тогда все числа будут в переделе от 0 до n - 1. Нужно поддерживать два RMQ, каждое размером n. Пусть первое RMQ это Q1, а второе — Q2. Q1_i будет содержать количество чисел i в текущему левом подмассиве, а Q2_i — в правом. Для начала нужно добавить все n чисел в левое RMQ. После этого будем идти указателем r от n - 1 до 1, при этом поддерживая l — максимальный индекс такой, что пара (l;r) содержит не более чем k инверсий (в начале l равно n - 1). Количество инверсий, очевидно, нужно поддерживать, используя RMQ (используя операцию "сумма на отрезке").

В такой реализации время выполнения алгоритма равно O(NlogN).