Трикове в динамичното оптимиране

Dynamic Programming Tips and Tricks

Трик с референции

Първо ще покажем малък трик в C++, който може леко да ви улесни при писането на задачи, които се решават с динамично оптимиране (а и не само). Чрез него можете да си спестите малко код, няколко индексирания в масиви, а също така да се подсигурите, че няма да забравите да попълните динамичната таблица след изчисляване на отговора. Този трик работи както за рекурсивните динамични, които вече разгледахме, така и за итеративните, които ще видим във втората тема за динамично оптимиране.

Трикът е да ползвате референция към клетката от динамичната таблица, която изчислявате в момента, вместо променлива за отговора на съответното състояние. Ползвайки референцията, вие променяте стойността на самата клетка в таблицата, като, обаче, не губите време за индексация всеки път (достъпвате я директно чрез адреса й, макар и скрито) като можете да ползвате много по-кратко и логично име. И, разбира се, тъй като де факто променяте самата клетка на динамичната таблица, след като сте свършили с изчисленията не е нужно да ѝ присвоявате намерения резултат - тя вече го има.

Например нека изчисляваме състояние от тримерно динамично и текущото състояние е (int year, int left, int right). По принцип бихме имплементирали нещо от рода на:
С този трик кодът би изглеждал по следния начин: Nice, а?

memset() за double[]

В първата тема за динамично оптимиране казахме, че не можем да ползваме функцията memset() за нецелочислени типове (например double). Затова съветвахме или да се ползва допълнителен масив (от тип bool), в който отбелязваме дали клетката е вече изчислена, или да инициализираме масива ползвайки цикли.

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

Относително предвидимо, 0.0 и в нецелочислени типове (float, double, long double) също е само нули в двоичен вид. Това означава, че memset() ще работи правилно, ако искаме да запълним нецелочислен масив с нули.

Всъщност се оказва, че memset() с -1 също би инициализирало масива с удобна стойност, но по малко по-различен начин, отколкото бихте очаквали. Нека имаме следния код: Ако беше целочислен, масивът щеше да се запълни със стойността -1. В случая, обаче, той е нецелочислен и се запълва със специалната стойност NaN ("Not a Number"). Това е стойност, запазена за резултат от невалидни аритметични изрази - например нула върху нула (0.0 / 0.0) или корен квадратен от отрицателно число (sqrt(-42)) биха дали NaN. Нещо специфично за тази стойност е, че тя не е равна на никоя стойност - дори на самата себе си! Така ако имате if (sqrt(-42.0) == sqrt(-42.0)) {..., няма да влезете в тялото на if()-а, тъй като той би се оценил като false, а не true, както бихте очаквали!

Можем да се възползваме от това по следния начин: Реално, проверката дали дадена клетка е запълнена е дали нейната стойност не е NaN - ползвайки свойството, че NaN е различно от всичко (включително себе си). Наистина, ако dyn[idx] е NaN, if()-ът би се евалюирал до false и бихме счели, че клетката не е изчислена (тоест не бихме return-нали веднага). От друга страна, която и друга стойност да има, изразът dyn[idx] == dyn[idx] би бил true и бихме върнали съответната стойност.

Инициализация с валидна стойност

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

Нека вземем за пример задачата ChangingSounds. В нея -1 е валиден отговор. Ако сме инициализирали таблицата с -1 и изчислим дадена клетка и отговорът за нея е -1, то реално ние няма да променим първоначалната стойност. Следващия път като стигнем отново до същото състояние (стейт) ще видим, че клетката е -1 и ще почнем да я изчисляваме отново. Така решението ни може все пак да стане експоненциално, въпреки, че уж ползваме динамично (реално го ползваме, но не за всички клетки). Така примерно можете да видите как моето решение фейлва с TL именно на тест, където много от клетките са с отговор -1. Също така можете да видите колко по-грозен код съм писал преди 8 години xD.

Еднозначен стейт

?	Знаете ли, че най-младият милиардер и създател на Facebook, Mark Zuckerberg, е участвал в TopCoder? Е, не много успешно, в следствие на което го тролват малко, но все пак.

Една от най-опасните грешки при динамично оптимиране при дизайна на стейта е да го направите такъв, че да не е еднозначен. Тоест да не описва състоянието достатъчно добре. Така от един и същ стейт бихте могли да имате два различни резултата. Нееднозначен стейт не е куул. You know what's cool? Еднозначен стейт.

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

Обикновено е удобно те да бъдат изнесени като глобални променливи/масиви (така не се налага да ги подавате като аргументи във функцията или рекурсията на динамичното).

Всичко останало, обаче, може и да участва, но може и да не участва. От вас се иска да изберете кое трябва и кое не, от което пряко зависи колко голяма динамична таблица ще ви е нужна, а също и колко бързо ще бъде решението. Това е и сложната част в тези задачи.

Динамично с map

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

Макар и понякога да работи, ако задачата има хитро решение и е достатъчно добре направена, това решение би било няколко пъти по-бавно от авторското и, съответно, би имало Time Limit на поне няколко от най-тежките тестове. Особено често това се наблюдава в TopCoder. Там изключително често неопитни, a понякога дори опитни състезатели ползват map вместо динамична таблица и, съответно, фейлват задачата поради тази причина.

Извод: използвайте динамично с map само в случаите, в които наистина не можете да измислите как да съкратите паметта по някакъв начин.

Примерна задача, в която може да се ползва map като динамична таблица е задачата
FiboPrimes. Тук трябва да забележим, че тъй като винаги делим на някакво число, то дървото, което се получава, е сравнително плитко (с дълбочина най-много O(log(N))). Съответно броят стейтове не е толкова голям и можем да ползваме map.

Примерен код, който решава задачата, би бил: Забележете, че оригиналното авторско решение се базира на динамично, което пази като стейт просто текущото число, като не мемоизира най-високите стойности. Тъй като дървото на рекурсията не е много разклонено там, овърхедът от преизчисляването на едно и също състояние много пъти не пречи на решението. Все пак, решението, ползващо map, е дори по-бързо от авторското. При вход с едва една цифра повече (десет пъти по-голям от разрешения в задачата) авторското решение върви за около 8 секунди, докато решението, базирано на мап, завършва за едва 0.2.

Обединяване на размерности

Понякога е неудобно да ползваме многомерни масиви. Представете си, че имаме динамична задача, която зависи от девет аргумента. Дори без числа и променливи в себе си, dyn[][][][][][][][][] изглежда грозно, да не говорим колко тромаво и сложно за писане.
Примерно в задачата Projects се изисква именно деветмерно динамично, като всяко измерение е число между нула и пет, включително. Вместо това, можем да кодираме стейта в едно единствено число - просто като го представим като число в K-ична бройна система. Наистина, ако имаме тримерно динамично с размерности [7][7][7], то очевидно [x][y][z] е еквивалентно на [x * 7 * 7 + y * 7 + z]. Ако помните от темата за Променливи, структури и масиви, масивите в C/C++ са организирани по почти същия начин.

?	В следващата лекция за динамично оптимиране ще разгледаме едно популярно доразвиване на тази идея. Там всяко измерение е от тип bool, тоест 0 или 1, като такъв тип динамични се наричат "динамично по битова маска".

В случая с дадената задача ще кодираме деветте измерения (с числа в интервала [0, 5]) като число с база K = 6 (всяко измерение ще е "цифра" на число в тази бройна система). Така първото измерение ще е b[0] * 6⁰, второто ще е b[1] * 6¹, и така нататък, като последното ще е b[8] * 6⁸. Сега вече можем да използваме едномерна таблица с 10,077,696 клетки за да запазваме изчислените стойности.

Оптимизация на паметта

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

В миналата тема, например, подсказахме, че задачата за винарската изба на Ели (втората примерна задача) е такава. Как бихме подходили ако ограничението за броя бутилки беше 1000 вместо 200? Вече нужната таблица би била dyn[1000][1000][1000], заемайки близо четири гигабайта памет - многократно повече от лимита на повечето състезания.

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

Ненужно-голям тип

Може би най-лесната от тези оптимизации е чрез наблюдение колко ще е най-големият възможен отговор от динамичното. Ако видим, че той е сравнително малък, можем да ползваме по-малък (откъм брой битове) тип за динамичната таблица (примерно short или дори char, вместо int). Така постигаме неколкократно подобрение на ползваната памет - два пъти ако заменим int със short, и четири, ако го заменим с char.

Забележете, че това е псевдо оптимизация - в най-добрия случай тя ни помага едва няколко пъти, тъй като разликата между най-големия и най-малкия възможен тип е не повече от осем пъти. Тя не намаля броя клетки, които се съдържат в динамичната таблица - само по колко байта заема всяка от тях.

Пример за такава задача е Space. В нея можем да забележим, че отговорът ще е малък, като даже се събира в unsigned char. Следователно ни е нужна четири пъти по-малко памет за динамичната таблица.

Друга подобна задача е Garbage, където вместо int можем да ползваме short - в най-лошия случай отговорът ще е 900 (ако взимаме само от едната страна отговорът ще е най-много 100 по 9).

Ненужно измерение

Най-честият, но вече не толкова очевиден случай, е когато сме измислили стейт, който не е "оптимален" - някой от неговите аргументи е еднозначно определен от останалите и реално не ни трябва.

Именно това е случаят със задачата за винарската изба на Ели. Забелязахте ли, че независимо дали изберем бутилка от лявата или тази от дясната страна, годината се увеличава? Тогава, не можем ли да ползваме тази информация и да не пазим годината в стейта изобщо? Ако в началото сме имали 10 бутилки и в момента най-лявата ни е тази с индекс 2, докато най-дясната с индекс 5 (индексирано от 0), то можете ли да пресметнете колко години са минали? Очевидно, от ляво сме взели вече две бутилки (с индекси 0 и 1), докато отдясно четири (с индекси 9, 8, 7 и 6). Следователно са минали шест години и в момента сме в седмата.

Така можем изцяло да премахнем едното измерение и да ползваме двумерна таблица. С тази оптимизация на паметта свалихме сложността по памет на O(N2), вместо досегашното O(N3), като при това не жертвахме изобщо скорост!

?

Това, че премахваме даден аргумент от динамичната таблица, не ни пречи да си го подаваме в рекурсията за удобство - така няма да се налага да го изчисляваме по останалите аргументи (въпреки, че бихме могли). В конкретната задача можем все пак да подаваме и годината като част от аргументите на рекурсията, но да не я ползваме в стейта.

Дори ако ограниченията бяха до 1000 (вместо до 200), решението би вървяло за части от секундата, ползвайки около едва четири мегабайта памет.

Друг пример е задачата Gingers, която е съвсем лека модификация на Blonds. Интересно обаче е, че доста хора не се сещат как да сведат първата до втората. Вместо да ползваме по едно измерение за всеки от типовете хора (тоест dyn[1000][1000][1000]), можем да направим наблюдението, че реално русите и чернокосите приятели на Ели не са различими един от друг за целите на задачата. Следователно можем да ги обединим в едно единствено измерение, получавайки 500 пъти по-малката таблица dyn[2000][1000].

Подобна оптимизация може да се приложи и в задачaта Преливане. В нея всъщност е възможно от дадено състояние да се върнем отново в себе си след определен брой преливания. Това означава, че трябва да ползваме или BFS или Dijkstra, вместо динамично.
В задачата трябва да направим наблюдението, че независимо какви преливания сме направили, количеството течност е винаги едно и също. Следователно, ако знаем колко вода има в първия и втория съд, то знаем и колко има в последния - общото количество минус това в първите два. Така бихме съкратили броя възможни състояния от 8,000,000 (200 * 200 * 200) на едва 40,000 (200 * 200).

Друга подобна задача е А1. Apples от националната олимпиада 2007 година.

?	Тази задача съм виждал давана (в хронологичен ред) първо в TopCoder, после на националната, а няколко години по-късно - и в Codeforces.

При нея трябва да съобразим, че редът и колоната на единия от хората и редът на втория еднозначно определят колоната на втория. Наистина, тъй като rowFirst + colFirst == rowSecond + colSecond можем да преместим единия аргумент от едната страна на равенството в другата и да получим colSecond == rowFirst + colFirst - rowSecond. Така вместо да пазим таблица dyn[70][70][70][70] можем да минем и само с dyn[70][70][70].

Eдна относително сложна задача, в която трябва да приложите това, е задачата Brainfuck. В нея е казано, че ще ни трябват най-много четири клетки, всяка със стойност 0...255. Едно наблюдение е, че ще ползваме само клетки със стойности между 97 ('а') и 122 ('z') включително. Вместо да пазим истинската стойност на клетките, можем да пазим само дали сме вече в интервала от букви и ако да - коя буква е сложена. Наистина, ако веднъж стигнем до интервала 'a'-'z' няма причина да излизаме от там. Така реално ни трябва да пазим само стойности между 0 и 26, включително (от 0 до 25 са буквите, а 26 указва, че текущата клетка е в началната си стойност). Трябва да пазим и до кой символ (от стринга, който искаме да изпечатаме) сме стигнали. Едно от важните наблюдения в задачата е, че ако имаме този символ, и индекса на клетката, от която сме изпечатали този преди него, то имаме нейната стойност наготово - ние току-що сме я изпечатали! Тоест ни интересува само индексът на клетката - а можем да пропуснем нейната стойност.
Равносметката е, че вместо да пазим [50][27][27][27][27][4], можем да пазим [50][27][27][27][4], подобрявайки нужната памет 27 пъти. (Реално ще ни трябват два такива масива - един за минималния брой ходове (като число) и един указващ коя е следващата операция, която трябва да направим, за да го постигнем.)

Компресия на аргумент

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

?	Обикновено задачите от този тип са специфично създадени с идеята да има недостиг на памет (и хитър стейт) и нямат други особено трудни неща в тях.

Често трябва да направим наблюдение, чрез което да намалим някой (или някои) от аргументите. Почти винаги не можем да спечелим много от такива оптимизации -- обикновено си спестяваме константен фактор (да кажем два или три пъти, а не N пъти, както при премахването на размерност).

!

Понякога тези оптимизации няма да бъдат възможни без да направим някакви допълнителни изчисления или модификация на входните данни. Примери за такива допълнителни действия са да сортираме даден масив със стойности, който ползваме в динамичното, или да прекалкулираме някакви специални стойности за параметрите на стейта.

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

Пример за задача с такъв тип оптимизация на паметта е отново задачата Garbage, където трябва да пазим начален и краен ред и начална и крайна колона. Тъй като няма как крайният ред или колона да са по-малки от началните такива, можем да съкратим паметта си четири пъти (два пъти от редовете и два пъти от колоните). Реално всяка клетка, в която началната колона е по-голяма от крайната такава винаги ще остане неизчислена - тя не е валиден стейт (аналогично същото важи и за редовете). Затова можем по такъв начин да "компресираме" таблицата, че да премахнем тези неизползвани клетки.

За целта всяка валидна двойка (start, end) можем да кодираме в едно число. Така двойката (0, 0) ще е числото 0, (0, 1) ще е числото 1, ..., (1, 1) ще е числото 100, ..., (99, 99) ще е 5049. Можем да смалим таблицата до dyn[5050][5050], като първото измерение е за началния и крайния ред, а второто - за началната и крайната колона. Забележете, че dyn[5050][5050] има приблизително четири пъти по-малко на брой клетки, тоест пести около четири пъти памет.

Друга примерна задача за компресия на аргумент е Noise. Тя се решава с динамично по битова маска, което ще разгледаме в следващата тема.

?

В тази задача може да се направи и една оптимизация на времето. Тъй като трябва да свържем всички точки рано или късно, то можем на всяка стъпка на динамичното да намерим първата, която все още не е свързана с някоя друга, и да кажем, че ще свържем на тази стъпка именно нея с някоя друга. Така решението става O(2N∙N), вместо O(2N∙N2).

Трябва да се направи наблюдението, че на всеки ход добавяме точно по два бита - тоест броят сетнати битове в маската е винаги четен. Така можем да си съкратим паметта двойно като не пазим последния бит - него можем еднозначно да определим по останалите (ако в маската без последната позиция има нечетен брой единици - значи последният е 1; в противен случай е 0).

Подобна задача е и MarblesInABag. В нея първоначално можем да видим, че ако искаме да помним броя и на двата вида топчета, ще са ни нужни приблизително 128 мегабайта (4000 * 4000 * 8 байта). Можем да симулираме по два хода наведнъж - вземане от нас и вземане от другия играч. Така общият брой топчета намалява с две и неговата четност остава същата. Така, ако знаем колко сини топчета има и пазим колко червени топчета има делено целочислено на две, можем еднозначно да определим колко червени топчета има (умножавайки числото по две и ползвайки четността). Така намаляме нужната памет наполовина, влизайки в ограниченията от 64 мегабайта.

Последният ни пример за тази оптимизация постига много повече от предходните. В задачата Zero очевидното петмерно динамично би заемало огромно количество памет, и все пак бихме се досетили, че много голяма част от клетките ще останат празни. По-наблюдателните състезатели биха забелязали, че реално таблицата ще е много, много рядка, тъй като в две последователни отпивания на едно момиче нейното число намалява поне наполовина. Наистина, дори да е било нечетно и тя да го е намалила само с единица при първото пиене, то при второто ще е четно и ще трябва да го раздели на две. Така можем да кодираме числото на всяко момиче в едва O(log(NUM)) клетки, вместо O(NUM). За цялостен анализ погледнете анализа от архива на задачата, или малко по-подробна версия на английски.

Жертва на време за памет

?	От края на 2013-та година, състезанията в TopCoder предоставят по-големи ограничения по памет (256 мегабайта) и custom time limit, който може да е по-малък от две секунди.

Обикновено ограничението по памет е далеч по-строго от ограничението по време. Например в TopCoder има time limit две секунди, докато memory limit 64 мегабайта. Забележете, че за две секунди можем да изпълним приблизително 200 милиона операции, докато имаме място само за 16 милиона int-а. Ако имаме решение, което се нуждае от 50 милиона операции и 120 мегабайта, то понякога ще може да го направим да ползва 100 милиона операции и 60 мегабайта, което, макар и по-бавно, вече би влязло и в двете ограничения.

Други състезания имат различни ограничения както по време, така и по памет, но обикновено положението е същото: ако можете да изпълните X операции в даденото време и да заделите Y клетки в масив, то X е поне няколко пъти по-голямо от Y.

Най-често при тази оптимизация вкарвате допълнителен цикъл в самото тяло на динамичното, като така премахвате или намаляте някое от измеренията на динамичната таблица. Пример за подобна задача е: Тук трябва да направите компромис между времето и паметта. Съществуват решения с:

• O(N) памет, O(N) време
• O(sqrt(N)) памет, O(N) време
• O(log(N)) памет, O(N∙log(N)) време
• O(1) памет, O(N2) време

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

Оптимизация на паметта чрез итерация

Във втората част за динамично оптимиране ще разгледаме друг (итеративен) начин, по който можем да конструираме самото решение, чрез който понякога можем да съкратим нужната ни памет драстично, премахвайки почти изцяло едно от измеренията.

Допълнителни материали

1. Динамично оптимиране, част I
2. Динамично оптимиране, част II
3. C++ References (en.wikipedia.org)