Втората задача от миналогодишния ни конкурс изискваше добре написан backtracking. Смятахме с втората задача от този кръг да провокираме някои от участниците да опитат отново тази често критикувана, но не лека, а за някои задачи и единствено възможна алгоритмична техника. “Да провокираме”, защото задачата предполага и друго, много по-различно решение. Искаше ни се да сравним скоростта на два от възможните подхода за решаване на задачата. Провокацията се състоя само донякъде, защото повечето от участниците предпочетоха да използват мощната техника динамично оптимиране. Затова ще започнем този коментар с решението на задачата чрез динамично оптимиране.

Нека с P означим произволен правоъгълник, които може да бъде контур на търсената ограда. С L_P да означим периметъра на този правоъгълник, т.е. дължината на търсената ограда, а с L*_P - дължината на оградата, която може да се построи след отрязване на всички дървета извън правоъгълника P. Ако L*_P>=L_P, тогава с отрязването на всички дървета извън правоъгълника оградата може да бъде построена и цената на оградата ще бъде цената на всички дървета, намиращи се извън правоъгълника, независимо от това необходими ли са или не. Ако L*_P<L_P, тогава дори с отрязването на всички дървета извън правоъгълника не може да бъде построена ограда на останалите дървета. Налага се да отрежем допълнително поне едно от дърветата, намиращо се вътре в правоъгълника, за да можем да покрием разликата L_P-L*_P. Това, разбира се, трябва да се направи с колкото може по-малка цена и това ни довежда до една от класическите задачи, решавани с динамично оптимиране - задачата за раницата в неприятния и вариант “0-1 раница”: дадени са R обекта, всеки с дължина li и цена ci; да се намери подмножество от обекти с минимална сумарна цена, такова че сумата от дължините на обектите в подмножеството да е поне L_P-L*_P.

Няма да се спираме в подробности на решението на задачата за раницата с динамично оптимиране (читателят, който не познава техниката трябва да направи справка в някоя от многобройните книги по алгоритми или да потърси съответна страница в Интернет). Читателите, които познават подхода са забелязали, че има две алтернативи за използване на динамично оптимиране:

Допълнителното условие на задачата - при равни минимални сумарни цени да се предпочете решението с по-малък брои отрязани дървета, прави втората алтернатива по-неудобна.

Решението на задачата ще бъде този правоъгълник P, който минимизира L*_P. А, при равни стойности на L*_P за два правоъгълника, избира този с по-малък брой отрязани дървета. Сложността на този алгоритъм се получава като произведение на броя на възможните правоъгълници и сложността на задачата за раницата. За броя на правоъгълниците са важни не размерите M иN, а броят на дърветата К, тъй като е достатъчно да се разглеждат само такива правоъгълници, на всяка страна на които лежи поне по едно дърво. Затова броят на правоъгълниците е O(K⁴). За задачата за раницата имаме сложност О(К.S), където S e сума от максималната възможна дължина на ограда (800) и максималната възможна дължина на ограда, която се получава от едно дърво (също 800, а не зададения в задачата максимум 1000, защото излишните 200 единици не могат да се използват). Т.е. макар и с не малка стойност S е константа и задачата за раницата се решава със сложност O(K). Окончателно, сложността на описаното решение е O(K⁵).

Естествено желание е сложността на решението да бъде сведено до O(K⁴). Подобна идея се среща в решението на Милослав Средков. Той разглежда едновременно (в рамките на една раница) всички правоъгълници с еднаква лява страна, като решава задачата за раницата върху най-големия, а след това започва да придвижва дясната страна на правоъгълника наляво, като прави само необходимите промени в построената вече таблица.

Колкото до решение с backtracking, ще резюмираме описанието на такъв алгоритъм написан доста бързо от миналогодишния победител от задочните кръгове Петър Петров. Дърветата се подреждат по “перспективност”, като освен класическа оценка, която се изчислява като цената която ще платим за единица дължина на ограда ако отрежем дървото, е допълнена с разстоянието на дървото от центъра на тежестта на множеството от дървета. След това, започваме класическо търсене с връщане. За всяко дърво, по реда на перспективност, се пробват две възможности - или се отрязва или не, като първо се пробва да не се отреже. Изчисляването на минималния обхващащ правоъгълник (оградата) за не отрязаните дървета се ускорява чрез използването на multi-set от STL - в тях всички операции са с логаритмична сложност, а намирането на минималния и максималния елемент е с константна сложност. В повечето случаи, най-доброто решение се намира още от първия път, но липсата на предварително зададено времево ограничение за работа на програмата довежда до това, че дори при намерено и “flush”-вано правилно решение, тестът не приключва успешно поради надвишаване на времевото ограничение.

Трима участника имат максимален брой точки в този кръг на конкурса - Валентин Цеков (В.Търново), Милослав Средков (Бургас) и Петко Минков (Пловдив). За подобни случаи регламентът на конкурса гласи, че победител е този, чието решение е най-бързо. Безспорно това е решението на Валентин Цеков - той единствен успешно съчетава двата разгледани подхода за решаване задачата, което води до изключително бързо работеща програма. Ето какво казва победителят за своето решение тук.