Анализ на задача grader67
Преди да разгледаме решенията на подзадачите, нека докажем следното твърдение: "Проверката за точките на една редица се проверява за О(N) при наличие на най-оптималната редица с N елемента"
Доказателство: Ако имаме най-оптималната редица, единственото нещо от нея което ни трябва е разликата на максималния и минималният елемент. 
Дали има поне два различни елемента в една редица и да намерим сумата на числата в редица са съвсем интуитивни и познати неща, които правим лесно за O(N).
С това доказателство променяме задачата: "Намерете разликата на максималният и минималният елемент в най-оптималната редица с N елемента".
Минаваме към решенията:

Първа подзадача: N<=6,7
Това решение позволява да използваме методът на "грубата сила". 
Разглеждаме всички възможни редици от числа и намираме тази с най-малка разлика на максималния и минималният елемент. Това ни е достатъчно да решим подзадачата.

Втора подзадача: N<=30
Тези ограничения биха ни ориентирали към решение N^4. Тук започва първата съществена стъпка към решението на задачата: Да направим dp.
Как биха изглеждали стейтовете на това dp? Едно примерно dp би било със стейтове {до кой елемент сме}{сумата досега mod n}{разлика на елементи}{имаме ли поне две различни числа}
и всеки елемент в него е pair и съдържа най-голямото и най-малкото число досега в оптималната редица до този елемент. Преходът е интуитивен и не мисля, че има нужда от обяснение.
Само да изясним защо сложността е N^4. Освен обикалянето на всички елементи се изисква още едно фиксиране на текущия елемент.

Трета подзадача: N<=100
Можем да оптимизираме решението от миналата подзадача. Не ни е нужно да поддържаме разликата на елементите. Тя е просто разликата на двата елемента в стойността на всеки елемент.
Така махаме един ненужен цикъл и сложността пада до N^3.

Четвърта подзадача: N<=1067
Тази подзадача няма фиксирано решение.

Пета подзадача: N<=1e5+67
Реално тук е същинската идея на задачата. Нека докажем следното грандиозно наблюдение:
За всяко N най-оптималната редица винаги има разлика на максималният и минималният елемент 2.
Ако сте изследвали отговорите от някои от миналите dp-та, или дори си направите редиците с backtracking, вие може да направите това наблюдение не прекалено трудно. Нека го докажем по един простичък начин:
Нека имаме редица от N единици (като цяло няма значение, може да е всяко число). Това според първото условие не е валидна редица. Ако искаме да я направим валидна, можем да добавим 1 към някоя единица и да извадим едно от друга единица. 
Така си гарантираме минимална разлика, защото няма как да намалим само едно число с едно или да увеличим само едно число с едно, защото се променя сумата. Интуитивно е, че можете да приложите тази идея за всяко N.

Изводи: Задачата на пръв поглед изглежда като класическо dp, но втория поглед разкирва алчността на пълното решение, което първоначално не беше предвидено и от авторите.

Автор и решения: Димитър Шапатов
Анализ и решения: Кирил Зашев