https://codeforces.me/contest/1858/problem/B "Прогулка по Аллее" Эта задача изначально показалась сложной, но разобравшись, я понял, что она не такая уж и сложная. Решение: Будем жадно удалять каждую палатку по одной. Для начала заведем переменную res, которая будет хранить результат массива, когда все палатки на месте.

Теперь рассмотрим пример: палатки [3, 5, 8]. Чтобы понять, что произойдет при удалении палатки, введем фиктивные палатки в начале и конце: 1-d и n+1. Почему именно 1-d? Об этом чуть позже.

Если удаляем первую палатку, границы предыдущей и следующей палатки «сливаются». Например, удаляя 3, границы -1 и 5 сольются: изначально было -1 3, 3 5, после удаления 3 — -1 5.

Формула для пересчета: res — (a[i] — a[i-1] — 1)/d — (a[i+1] — a[i] — 1)/d + (a[i+1] — a[i-1] — 1)/d — 1 Пояснение:

(r-l-1)/d — количество «прыжков» длиной d между границами.

Вычитаем 1, так как мальчик гарантированно съест вафлю на текущей позиции.

Для всех палаток считаем этот ответ, сохраняем в мапе, затем берём минимум — это и будет финальный результат.

https://codeforces.me/contest/1857/problem/E "Мощность точек" Задача кажется математической. Решение: Ответ не зависит от исходной расстановки, поэтому удобно отсортировать массив.

Для каждого элемента строим формулы для крайних и промежуточных элементов, используя префиксные (pref) и суффиксные (suff) суммы.

Формулы:

Для крайнего элемента: suff[i] — n*a[i]

Для другого крайнего: (a[i]+2)*n — pref[i]

Для промежуточных элементов: (suff[i] — (n-i)*a[i]) + ((a[i]+2)*(i+1) — pref[i]) — 1

Сохраняем ответы в мапе и выводим результат для исходного массива.

https://codeforces.me/contest/1850/problem/G "The Morning Star" Решение: Нужно найти пары точек, которые показывают на север, юг, восток, запад или их комбинации.

Север/Юг: пары с одинаковой координатой x.

Восток/Запад: пары с одинаковой координатой y.

NE/NW: если b-a == b'-a' или a+b == a'+b'.

Для оптимизации создаём 4 мапы: по a, b, b-a, a+b. Ответ: ((x-1)*x/2)*2 для всех значений в мапах.

https://codeforces.me/contest/1817/problem/A "Почти возрастающая последовательность" Решение: Используем жадный подход.

Определяем «плохие» точки: a[i-1] >= a[i] >= a[i+1].

Создаем префиксные суммы special[i], чтобы быстро считать их на отрезках.

Для запроса [l,r]:

ответ = (r-l+1) — (pref[r-1] — pref[l]) Если r-l+1 <= 2, просто возвращаем r-l+1, так как отрезок слишком короткий для подсчета плохих элементов.

https://codeforces.me/contest/1814/problem/C "Параллельный поиск" Решение: Нужно оптимально распределить числа от 1 до n.

Создаем массив пар (a[i], i+1) и сортируем по a[i].

Жадно распределяем элементы в два массива.

Используем формулу: if (s1*(1+cnt1)*ans[i].first <= s2*(1+cnt2)*ans[i].first) -> выбираем первый массив Обновляем cnt1 и cnt2 соответственно. Выводим два массива как ответ.