Я условия не знаю, в Gold были задачи Large Banner, Haybale Restacking, Cows in a Skyscraper. И, да, формально еще кто-то мог начать писать в 16:00 по Москве, поэтому начало обсуждения лучше перенести на 19:00.

Если это та про цветы, то в голову приходит только максимальный поток минимальной стоимости. Но учитывая, что N до 100 и дивизион — silver, скорее всего какая-то жадность должна быть.
Все-таки не та про цветы, я про Landscape подумал.

Решать двумя указателями. Сделать сжатие координат по икс. Далее для каждого икса выписать максимальный и минимальный игрек. Далее перебираем начало отрезка ответа, а конец подбираем указателем. Чтобы быстро проверять, можно двигать указатель или нет, нужно хранить сет текущих игреков.

Можете пояснить, как это тут применить? Я написал перебор всех взаимно простых пар чисел и возьму свои пару тестов от силы.

Расшифруй, о, Математик! UPD: прочитал выше

Я прооптимизировал тупое решение. Для этого надо быстро научиться считать сумму и количество чисел x<=N, взаимно простых с y. Делается тупо формулой включений-исключений.

Можно соптимизировать в 2 раза. На асимптотику не влияет, но по времени работы заметно: когда перебираем подмаски невзятых коров сразу берем самую первую единицу и перебираем в 2 раза меньше подмасок.

Да ну? Я когда отсылал, сымитировал на сэмпл-тесте тест из 18 чисел, у меня не затлилось. Сколько у тебя локально работает?

У меня локально под виндой работало около 1,5 сек.

Оптимайзил так: если можно взять всю маску, то брал ее, если переход — убрать одну корову, то не делал его. Так отсекается много состояний.

Научимся решать задачу для линии. Заметим, что если не делать лишних действий, то всё однозначно. Как заметить: уберём сложную операцию, добавим простую "переложить из одной в соседнюю" ценой 1. Ничего не поменялось. Теперь посмотрим на самую левую кучку. В/из неё надо переложить понятно сколько. Переложили, убрали. Аналогично с остатком. Получается формула вида |c₁| + |c₁ + c₂| + ... (где c_i = b_i - a_i)

Теперь тупой вариант для кольца: перебираем, сколько переложили в/из первой в последнюю. Пересчитали ашки, прорелаксировали ответ. Наблюдение: по сути, мы перебираем, на сколько "сдвинуть" a₁ (последнее слагаемое всегда ноль, потому что суммы равны). Теперь заметим, что оно одинаково влияет на все слагаемые и тут прекрасно сработает троичный поиск (aka бинпоиск по производной).

Пусть d_i = b_i - a_i Теперь рассмотрим величины x_i — сколько стогов сена(или чего там) мы перешлем из кучи i-1 в кучу i(если пересылаем в обратном направлении, то x_i < 0). Теперь получаем систему уравнений вида x_0 — x_1 = d_0, x_1 — x_2 = d_1, ..., x_{n — 1} — x_0 = d_{n — 1}. Нужно найти решение этой системы, минимизирующее сумму модулей x_i. Ясно, что все решения отличаются друг от друга прибавлением константы ко всем x. Тогда найдем любое решение(например положив x_0 = 0), отсортируем получившиеся x, и прибавим такое число, чтобы занулилось x_{n / 2}. Доказательство оптимальности тут такое же, как у точки, минимизирующей сумму расстояний до данных точек на прямой.

Какой-то полный атас с техом и курсивом, но вроде основная идея понятна.

а как ты решал задачу problem 2. connect ?

Может, кто осилит найти ошибку здесь? А то 2 теста по WA не прошло, непонятно, как такое может быть

а O(3^n) проходили полный балл?

как не странно, но у меня прошло вот такое решение. перебирая все маски, пытался как можно оптимальнее заполнить каждый лифт. в итоге получил O(N * 2^N)