# Разбор задач 2021 года
Если Вы не знали, как решать какую-то задачу, и Вам было лень разбираться в коде на Pascal, то это пост специально для Вас.
:::warning
Убедительная просьба не копировать коды и не пересылать их. Помните -- Вы решаете задачи для себя!
:::

## [1. Покупка подарков](https://codeforces.com/group/skz9fIV5Hq/contest/351464/problem/A)
:::spoiler Разбор
:::info
Аккуратно напишем, что просят в условии задачи. Нужно не забыть учесть выход за границы линии из коробок.
Пример алгоритма:
Из первого пройдем вправо, потом обратно. Поставим одну коробку. Будем повторять, пока не все коробки лежат на первом месте. В других случаях будем ходить влево, а потом назад. Не забудьте про случаи, когда n = 1
:::

## [2. Первое имя](https://codeforces.com/group/skz9fIV5Hq/contest/351464/problem/B)
:::spoiler Разбор
:::info
Одна из самых интересных задач соревнования.

Давайте поймем, какую строку следует приписать на текущей иттерации. Если осталось одна строка, то очевидным образом можно выполнить действие.

Если есть 2 и более строки:
Тогда из двух строк $a$ и $b$ будет идти раньше:
$a$, если $a + b$ < $b + a$
$b$, иначе.

Теперь можно отсортировать слова.

В чем логика?

Очевидно, что итоговое слово должно начинатся на минимальную букву.
Что делать, если таких слов несколько?

Какую из двух строк выгоднее поставить первой. Ту, которая при соеденении(a + b, b + a) дает
меньшую(лексикографически) строку. Тогда можно найти минимальную строку, которую следует поставить на
первую позицию. Для остальных позиций аналогично.

Как реализовать?
Можно написать компоратор для сортировки $O(n*log(n))$. Есть константа длины строк 50, т.е. $O(n*log(n)*50)$.

Можно написать спуск по бору $O(n)$. Есть константа 26(количество букв) и длины строк 50, т.е. $O(n*26*50)$.

Из практики, оба решения работают одиннаково по времени(очевидно, быстрее написать сортировку).
:::

## [3. Навигация](https://codeforces.com/group/skz9fIV5Hq/contest/351464/problem/C)
:::spoiler Разбор
:::info
Основная идея в том, чтобы перебирать момент времени, после которого корабль сможет доплыть до финиша. Это можно сделать, т.к. смещение корабля ветром и его движение суммируются. Давайте промоделируем первые $i$ дней. Тогда, чтобы можно было добраться до финиша достаточно условия $abs(tech.x - fin.x) + abs(tech.y - fin.y) \leq i$.
:::

## [4. Украшение ландшафта](https://codeforces.com/group/skz9fIV5Hq/contest/351464/problem/D)
:::spoiler Разбор
:::info
[BaluconisTima](https://codeforces.com/profile/BaluconisTima)
Давайте использовать бинарный поиск по ответу. Значит, теперь нам надо теперь решить следующую задачу:

У нас есть n чисел. Нам надо изменить максимум m из них так, чтобы разница между числами была не более mid.
Эта задача решается методом динамического программирования, где dp[i] - сколько чисел можно не изменять до i так, чтобы выполнялось нужное нам свойство.

переходы достаточно просты: Мы знаем точный ответ для dp[i]. Попробуем найти с помощью него ответ для dp[j], где j > i.
Представим, что мы изменим все между ними. В таком случае, мы можем сделать переход, если abs(a[i] - a[j]) <= mid * (j - i), тогда dp[j] = max(dp[j], dp[i] + 1);

К примеру, mid = 2, i = 1, j = 4.
1 500 135 2143 9

В таком случае заменим числа между ними подобным образом:
1 3 5 7 9
То есть, если число меньше, то мы отнимаем по mid, пока оно не станет равным, иначе добавляем.
:::