След като имахте достатъчно време да се пробвате да дорешите задачите от контролното, тук ще опишем нашите идеи за решения на задачите:
A. Бал
Задачата напомняше на Дейкстра (граф, претеглени ребра, оптимален път между два фиксирани върха), но от една страна цените на ребрата бяха зададени по нестандартен начин, а от друга не се питаше за най-къс път, ами дали дадена цена ще е достатъчна. Това, реално, успя да заблуди много от вас. Тук ще покажем, че задачата си е чиста Дейкстра, след като помислим над двете "нестандартни" неща в задачата.
- Цени: "алгоритъмът" за определяне на цените на ребрата беше точно описан в условието - ако имаме височина на колата K и ребро от A до B с текуща височина H, ние трябва да заплатим:
- 0, ако K <= H.
- (K - H) * (K - H) + K - H, в противен случай
- Най-къс път: ако началните ни пари C биха ни стигнали за *някой* път, относително лесно можем да видим, че биха ни стигнали и за най-евтиния път. Така свеждаме задачата до намиране цената на най-късия път и сравняването й с C - ако е по-малка или равна, печатаме "YES", а в противен случай печатаме "NO".
Можете да разгледате примерно решение, имплементиращо задачата с Дейкстра и с Белман-Форд (второто има няколко TL-а, тъй като задачата беше предвидена да се реши с Дейкстра).
B. Ягоди
Това беше може би най-лесната задача, тъй като нито изискваше особено хитра идея (за разлика от Хобитата), нито имаше особено сложна имплементация (като, например, Бал).
Това, което трябваше да забележите, е че ако направите префиксен масив със сумите на ягодите от началото до индекс i (за всеки индекс i), то после ще можете бързо да отговаряте на заявките, като правите двоично търсене в този префиксен масив. Наистина, за дадено куери q ви интересува най-малкият индекс (индексирано от 1), в който сумата на ягодите е по-голяма или равна на числото q.
Примерна имплементация с Binary Search, а също така възможен cheat ако познавате STL достатъчно добре.
C. Хобита
Най-лесната за имплементация, но изискваща относително хитро наблюдение задача в темата. Въпросното наблюдение беше, че трябва да намерите броя на елементите, които трябва да разместите, но не и в какъв ред трябва да се разместят - реално можем да считаме, че ги местим някъде другаде, а после можем да ги оставяме на върха на купчината в какъвто ред искаме. Това е еквивалентно да изберем реда, в който ги звимаме от купчината и ги поставяме на върха й. Нека вземем следния пример:
Как ги имаме: (най-долен) 3 8 5 2 7 6 1 4 (най-горен)
Как ги искаме: (най-долен) 8 7 6 5 4 3 2 1 (най-горен)
За да стигне 8 най-отдолу, очевидно трябва да вземем 3 и да го сложим най-отгоре, по някое време. Наблюдението, което направихме, ни казва, че можем просто да го вземем и за сега да не го оставяме най-отгоре - само да го преброим към отговора (+1). Следващото число е 8, което точно търсихме - него не трябва да го местим, то си отива на мястото. Следващото число, което искаме над 8 е 7. Реално, обаче, имаме 5 - тоест и 5 трябва да го преместим най-отгоре. Преброяваме го към отговора (+1) и го махаме. За 2 правим същото (+1). Стигнахме до 7, което искахме да е над 8, тоест не го местим - след като сме махнали 3, 5, и 2, то си отива на мястото. Следващото е 6, което трябваше да е над 7 - също окей. 1 и 4 не са си на мястото, тоест ги местим (+2). Преброихме 5 местения, колкото е и отговорът.
Реалната имплементация на този алгоритъм е изненадващо проста.
D. Принцове
Тази задача пък си плачеше за BFS - пита се за най-малък брой ходове, всеки ход отнемащ 1 минута. Имаше две по-специфични неща от най-праволинейното BFS:
- Неевклидността на дъската: това не беше изобщо голям проблем, тъй като вместо да правим проверка дали излизаме от дъската трябваше да смятаме клетката по модул N и М.
- Принцовете: ако нямаше принцове или в случаите, в които има само един принц, пътят е ясен: от Ели до принца и от принца до изхода. Какво става, обаче, ако имаме два принца? Очевидно, трябва да отидем първо до единия, а после до другия, но не е ясно кой да е първи. Затова можем просто да пробваме и двата варианта и да видим кой от двата е с по-малък брой ходове.
Няколко човека имплементираха до някаква степен грешни решения, като отиваха до по-близкия принц първо. Това, обаче, не винаги е оптимално, тъй като трябва да се вземе напредвид и разстоянието от втория принц до изхода. Задачата може да се реши аналогично и с до 5-8 принца (пробвайки всички пермутации на принцовете) или до малко над 20 принца (ползвайки динамично оптимиране, което предстои да учим). Впрочем, тази задача оригинално е дадена във варианта с 5 принца на състезание за ученици 7-8 клас където трима ученика са я решили перфектно, а 8 почти перфектно. Примерно решение, имплементиращо BFS, можете да видите тук.
E. Резачка
Задачата изискваше да направите наблюдението, че не сме ограничени колко пъти можем да ползваме резачката, съответно можем да правим рязания, които не ни трябват. Второто наблюдение беше, че можем да почнем да "режем" стринга отзад напред, оставяйки накрая само L символа (може да се покаже, че това винаги е оптимално, тъй като по-къси стрингове са лексикографски по-малки от по-дълги със същия префикс). Оказва се, че отговорът се състои от L-1-те най-малки символа от целия стринг заедно с първия символ в стринга (него няма как да го "махнем" при каквото и да било ползване на резачката). Много хора не се сетиха за този символ и просто намираха L-те най-малки символа от стринга.
Съществува много просто и кратко решение, което ползва STL и хваща 60-70 точки. Задачата, обаче, беше направена с идеята нормалните (N*logN) сортирания да са бавни. Изискваше се да направите и наблюдението, че азбуката ви е много малка (едва 62 символа!), съответно беше перфектен кандидат за сортиране чрез броене (Counting Sort). Това решение е линейно и хващаше всички тестове.