Анализ на задача permutation

Задачата ни въвежда в типична encode-decode задача - слагаме -1 в пермутация и после трябва да я върнем в оригиналното й състояние. Идеята е, че колкото повече -1 слагаме, ще е 
толкова по-добре за точките, които се смятат по формула, спрямо най-доброто решение. Както знаем не можем да използваме глобална памет, което леко затруднява нещата.
Нека преминем към решенията на подзадачите:

1. Пермутацията, която се подава в encode е подредена в нарастващ ред - тоест във вида 1, 2, 3..n:
Решението е доста интуитивно - можем да сложим -1 на всяко число от пермутацията, защото ние реално знаем каква пермутация е подадена в encode. Основната идея на тази подзадача е
да получим feedback от системата, че всичко е наред и че сме разбрали условието.

2. n <= 16-17:
Тази задача позволява използването на методът на "грубата сила".

3. Оптималното решение поставя единствено една -1:
При тези ограничения можем просто да сложим -1 при единицата в пермутацията на encode и после при decode да я заменя с едно.
Това работи, защото както е казано в условието, -1 се заменя с първото неизползвано число от 1 до n, следователно като имаме само едно -1 ще получим верен отговор.

4. Няма ограничения
Пълното решение се базира на следната идея: При encode да заменим с -1 числата, които са най-малките
неизползвани до момента. Тоест, слагаме -1 при последователните срещания на числата от 1 до n. Например ако имаме пермутацията 1 3 2 4 5 ние единствено ще можем да сложим -1
на 1 и 2, защото като стигнем при 3, още не сме изполвали 2, а когато стигнем до 4 и 5 още не сме използвали 3. Това е greedy подходът на тази задача и той гарантира оптимално
слагане на -1.


Наблюдения на авторите:
Когато си мислихме, че сме направили успешно първата ни encode-decode задача, се оказа, че на някои тестове получаваме грешни отговори.
На някои тестове получавахме верен отговор, на други ни показваше, че decode пермутацията е само с нули. Тогава Митко направи наблюдението, че системата не разпознава
една от жизнено важните папки за encode-decode задачите - manager. Причината за това е, че оценяващата система на eJOY е стара (от 2021), когато още не е поддържала encode decode задачи
(или въобще не са съществували като цяло). Митко успя да заблуди системата и вместо да има manager папка, той вкара всичко в грейдъра. Но и това си има последици. Реално задачата
със сегашния grader може да се изчийти - вижте permutation_cheat_100p.cpp. Но това може да се случи само ако знаете как работи грейдъра, но това просто не е възможно по време на състезание :).
И понеже решихме, че трика, който използвахме в грейдъра е доста интересен...


Анализ на грейдъра на задача permutation
При задачите от тип encode-decode ролята на мениджъра е да пуска програмата на състезателя два отделни пъти - за енкод и декод. Целта на това е следната: дори и да има глобална памет, която
да споделят двете функции, тя става безполезна, защото при всяко пускане на програмата се вика само едната функция. 
Проблемът е, че тази версия на системата не поддържа мениджър програми. Трябва по някакъв начин да се напише програма (грейдър), която се компилира с друг файл (решението) и 
проверява дали има глобална памет, която се използва от двете функции. Разбира се, в тази ситуация не може да се предотврати напълно използването на глобална памет.
Грейдъра, който реализирахме, използва грийди стратегия за проверяване на глобалната памет. Функцията encode се вика 2 пъти - веднъж с оригиналната редица и веднъж с произволна редица
(в случая същата редица с N+1 накрая). 
Нека разгледаме три чийт решения и как работят с грейдъра:

1. При викане на енкод си запазваме редицата в глобална памет и връщаме редица с N -1ци, за да получим максимални точки по формулата за оценяване. При декод просто връщаме запазената редица.
Това решение не работи, защото при второто извикване на енкод от грейдъра редицата в глобалната памет се презаписва и декод няма да я върне правилно.

2. Връщаме същата редица в енкод и декод.
Според формулата за оценяване това решение просто не е вярно, т.е. не запълва редицата с никакви -1ци.

3. Решението в permutation_cheat_100p.cpp: за всяко извикване на енкод се запазва редицата в списък от редици в глобалната памет и връща N -1ци. При декод получаваме редица,
която съдържа само -1ци и единствения ни показател коя е тя е размера й. Просто обхождаме всички запазени редици и търсим тази с размер N.
Това решение тръгва за пълни точки, но състезателите биха могли да го измислят единствено ако знаят, че енкод се вика два пъти и втория път редицата е с различен размер.
Това на практика просто не е възможно.

В крайна сметка всичко стана перфектно и чийт реално е невъзможен от страна на състезателите.


Идея, решения, анализ, условие: Кирил Зашев
Решения и грийди грейдър: Димитър Шапатов