652A - Gabriel and Caterpillar
Задача предложена пользователем Ali Ibrahim C137.
Заметим, что если есть пара соседних не взаимнопростых чисел, то мы обязаны между ними вставить какое-нибудь число. С другой стороны мы всегда можем вставить число 1.
Сложность: O(nlogn).
652B - z-sort
Задача предложена пользователем Srikanth Bhat bharsi.
В этой задаче нужно было сделать ровно то, что написано в условии. Никаких хитростей и подвохов.
Сложность: O(n).
652C - Foe Pairs
Задача предложена пользователем Mohammad Amin Raeisi Smaug.
Назовём отрезок [l, r] хорошим если в нём не более k ноликов. Заметим, что если отрезок [l, r] хороший, то отрезок [l + 1, r] тоже хороший. Таким образом, можно воспользоваться методом двух указателей: один указатель это l, а второй это r. Будем перебирать l слева направо и двигать r пока можем (для этого нужно просто поддерживать количество ноликов в текущем отрезке).
Сложность: O(n + k).
