Дизайн и анализ на алгоритми - практикум, 2015

Обещах да напиша кратък анализ на задачите от пробното състезание (което направих още да е активно, за да можете да си решавате):

А. Square

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

Какъв е графът в тази задача? Всяко разположение на буквичките и празното квадратче реално е връх в графа. Всяко местене на празното квадратче от едно състояние (връх) е ребро. Тъй като можем да го преместим най-много в четири посоки, от всеки връх излизат най-много 4 ребра. А колко върха има графът? Очевидно имаме 9 позиции, ако направим всичките 9! пермутации ще получим точна оценка на броя върхове - малко над 300,000. Така ребрата са около 1,200,000 (реално по-малко, тъй като от доста от състоянията имаме само 3 или дори 2 валидни хода.).

Ребрата са без тежест - всяко от тях е едно преместване и можем да считаме с цена 1. Така между БФС и Дейкстра бихме избрали БФС (по-лесен и по-бърз за графи без цена (или с еднаква цена) на ребрата).

Има и един допълнителен трик: тъй като имаме много на брой дъски, които трябва да решим (до 1000), да правим БФС за всяка от тях би било бавно. Можем да се възползваме от факта, че *всички* входни дъски искаме да докараме до *една единствена* крайна такава. Вместо да правим 1000 БФС-та от всяка дъска до крайната, можем да пуснем едно единствено БФС от крайната до всички останали (после ще печатаме "пътищата" наобратно).

Някакво усложнение е, че трябва да намерите освен най-късия, така и лексикографски най-малкия отговор. Това обаче не прави задачата *особено* по-сложна.
Очаквайте задачата за "екстра кредит" да е с подобна (може би съвсем малко по-лека) сложност.

B. Bazinga

Това беше най-лесната задача. В задачата просто трябва да проверите по колко пъти се среща всеки от символите {'B', 'A', 'Z', 'I', 'N', 'G'} (като малки и големи). Отговорът е min(cnt('A') / 2, cnt('B'), cnt('Z'), cnt('I'), cnt('N'), cnt('G')). (Забележете, че делим броя А-та на две, тъй като участва два пъти в "BAZINGA".)
На контролното може би няма да има чак толкова лесна задача, но най-лесната няма да е много по-трудна.

C. Crosses

Това е логическа задача, в която имате кръгла маса и се редувате да слагате монети с еднакъв диаметър. Който не може да сложи монета губи. Трябва да забележете, че е оптимално да сложим като първи ход в центъра (имаме N - нечетно число, така че винаги имаме "център"). След това където и да сложи опонентът ни, ние можем да сложим симетрично спрямо центъра на него. Така ако той е можел да сложи, и ние можем. Рано или късно дъската ще се запълни и той ще загуби. Трябва да се справим с частния случай, в който дъската е с размер 1 - тоест дори като първи играч не можем да сложим кръст, в който случай печели Kriss. Ако това ще ви успокои, около половината от разширения национален отбор по информатика не се сетиха за частния случай.
Това беше втората най-лесна задача, която като имплементация е буквално тривиална, но пък изискваше известно мислене и досетливост. 

D. Dijkstra

Беше махната от темата.

Е. Sysadmin

Трябва да забележим, че ако можем да направим K кабела с дължина X, то със сигурност можем и с дължина X-1. Вярно е и обратното - ако не можем с X, то няма да можем и с X+1. Това ни дава възможност да направим двоично търсене по дължината, като за всяка фиксирана дължина тривиално (линейно) проверяваме колко кабела можем да направим. Трябваше да внимавате за overflow, тъй като 10,000 * 100,000,000 > 2,147,483,648.