Решение на задача 2 (ЖИЛИЩНИ БЛОКОВЕ) от конкурса
по програмиране на Musala Soft и PC Magazine/Bulgaria
от Петър Петров

Забелязваме, че са в сила следните твърдения:
  1) Ако дадена височина h се среща в поне един от двата силуета, то точно един блок с тази височина задължително участва във всяко възможно решение.
  2) Ако дадена височина h не се среща в никой от двата силуета, то няма смисъл да опитваме да включим блок с тази височина в търсеното решение (с други думи, това по никакъв начин няма да доведе до по-успешно решение).

Можем да обобщим тези две твърдения в следното:
  3) Нека [h1,h2,h3,...,hp] е множеството от всички различни височини, срещани в двата силуета, а p е броя им. Тогава, ако съществува поне едно решение, то задължително съществува и решение, състоящо се от K=p блока с височини (h1,h2,h3,...,hp).

Следователно, достатъчно е да намерим решение, състоящо се от K=p блока с височини (h1,h2,h3,...,hp). Ако такова не съществува, ясно е че изобщо няма решение. А намирането на такова решение се свежда до намирането на координатите на югозападния ъгъл на всеки от блоковете.

Ще отбележим още някои твърдения, които ще ни бъдат от полза:
  4) Западната стена на блок с височина h може да се намира на координата x, единствено ако в южния силует височините с индекси (x,x+1,x+2,...,x+M-1) са не по-малки от h.
  5) Аналогично на 4), но за южната стена.
  6) Югозападният ъгъл на блок с височина h може да е с координати (x,y) единствено ако западната му стена може да се намира на x и южната му стена на y.

Можем да изчислим предварително в един вектор максималните възможни височини на блок, чиято западна стена се намира на координата x. Аналогично и за южната стена. Това ни позволява впоследствие да проверяваме дали даден блок може да бъде поставен на координати (x,y) за константно време.

За всеки от блоковете можем да намерим ограничаващ правоъгълник, извън който да не е възможно да бъде поставен югозападния му ъгъл. Това става по някои прости правила. Например, ако в южния силует на индекс 8 се намира височината 50, то ясно е, че западната стена на блока с височина 50 не може да бъде извън интервала [8-M+1,8]. Сечението на всички такива интервали за височината 50 ни дава едно ограничение за x координатата на съответния блок. Ако височината 50 не се среща в южния силует, а само в западния, то за допустим интервал по x взимаме максималния възможен, т.е. [0,N-M].
След като имаме така намерения ограничаващ интервал по x, можем да го стесним още повече, като движим лявата му страна надясно и дясната му наляво, докато западната стена на съответния блок не може да се намира на съответната координата (вж. твърдение 4).
Аналогично намираме ограничаващите интервали по y. Така вече за всеки блок имаме ограничаващ правоъгълник.

Следващата стъпка е да съставим за всеки блок по една двумерна булева карта, която да показва за всяко отделно квадратче от ограничаващия му правоъгълник, дали е възможно на него да бъде поставен югозападния ъгъл на блока (според твърдение 6).

Ще въведем и една характеристика на даден блок - площ (area) - това е броят на квадратчетата, на които е възможно да бъде поставен югозападния му ъгъл. Очевидно, всяко едно от тях се намира в ограничаващия му правоъгълник.

Пристъпваме към описанието на самото решение. То представлява branch-and-bound - това е усъвършенстван backtracking, тоест търсене с връщане, или пълно изчерпване. При branch-and-bound-а, за разлика от обикновения backtracking, се гледа и напред. Основната идея на нашия branch-and-bound ще бъде да пробва различни варианти за югозападния ъгъл на всеки блок, докато не се получи решение. Ще приложим следните оптимизации:
  - преди началото на branch-and-bound-а, блоковете се сортират по показателя area. По този начин блоковете, за които има по-малко възможности за разполагане ще бъдат поставени по-напред и branch-and-bound-ът ще мине първо през тях. При това, те могат евентуално да направят невъзможно поставянето на следващи блокове, което ще бъде открито на възможно най-ранен етап. Може да се отбележи, че винаги има поне един блок с area не по-голяма от 1 - това е блокът с най-голяма височина. Ако пък някой блок е с area 0, то това ще бъде първият блок прегледан от branch-and-bound-а и той ще спре още при него. Нулева area може да се получи например ако в даден силует разстоянието между първото и последното срещане на дадена височина е по-голямо или равно на M, или ако има изпъкнала област от еднаква височина с дължина по-малка от M, или пък ако максималната височина се среща само в единия от двата силуета.
  - когато югозападният ъгъл на блок се поставя на координати (x,y), това прави невъзможно поставянето на югозападен ъгъл на друг блок в квадрата с координати (x-M+1, y-M+1, x+M-1, y+M-1). Branch-and-bound-ът използва това и когато поставя даден блок на координати (x,y), всички следващи, все още непоставени блокове се преглеждат и в булевите им карти се отбелязват квадратчетата на които вече не е възможно да бъдат поставени, като при това се обновяват стойностите на area-та на всеки от тях. Ако area-та на някой от тях спадне до 0, значи за него няма нито една възможна позиция и съответно текущия блок не може да бъде поставен на (x,y).

Така написаният branch-and-bound почти никога не се връща назад, а почти винаги открива решението или липсата му от първия път (всъщност, не съм открил случай в който той въобще да се връща назад поне веднъж, но това не означава че такъв не съществува).


Петър Иванов Петров (piettropro@bigfoot.com, pesho@pesho.com)
СУ / ФМИ, спец. Информатика, 3 курс

16 Януари, 2001 г.