Турнир за Купата на Декана, 2009

Dean's Cup, 2009

Задачите за Ели (от А до I) бяха дадени от мен, Александър Георгиев, и тествани от Иван Иванов, който също така даде идеи и написа алтернативни (и в повечето случаи по-добри) решения на задачите, за което му благодаря сърдечно. Последната задача (геометрията J) беше на Ивайло Странджев и леко обърканото условие не успя да спре седем от състезателите да я решат. =) По мое мнение тя беше втората по трудност задача след безспорния фаворит (задача Travel). Мнението ми беше грубо опровергано от седемте човека, които я решиха (пет от които от първи събмит!). И все пак - забележете, че никой от топ тримата в общото класиране не успя да я направи. Поне донякъде съм бил прав =)

Победители

Присъствено състезание

Победител в присъственото състезание и съответно заслужил Купата на Декана стана
Момчил Иванов, първи курс, специалност Компютърни Науки. Честито!

В много близка борба, след него се класираха Стефан Аврамов и Иван Георгиев. Както се вижда и от класирането по-долу, борбата беше безмилостно жестока, както е казал знаменитият български автор. Само две минути наказателно време не достигнаха на миналогодишния победител в Online версията Стефан Аврамов да capture-не the flag!

Иван Георгиев, от друга страна, след като дълго време водеше поради добрия
success rate (6 задачи, предадени от първи път и едва 2 неуспешни опита на 7мата!), също беше на косъм да грабне купата, стига да беше успял да додебъгне написания си поток на задача H.

Онлайн състезание

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

На второ място се класира студентът Георги Ацев, който беше и единственият в онлайн версията, който реши геометричната задача.

С тежък махмурлук Румен Христов извоюва третото място. Специално за нашия сайт, потърпевшият коментира:

Пълно класиране

Присъствено Състезание

Name

A

B

C

D

E

F

G

H

I

J

Total

1.

Момчил Иванов

34/1

95/1

39/0

139/0

178/0

-/-

82/1

262/1

226/1

-/-

8/1157

2.

Стефан Аврамов

30/6

51/0

22/0

72/0

238/1

-/-

99/1

168/2

214/3

-/-

8/1159

3.

Иван Георгиев

13/0

43/0

21/0

101/0

-/3

-/-

236/2

-/2

80/0

255/0

7/792

4.

Георги Бойваленков

19/0

31/0

7/0

69/2

-/4

-/-

130/4

-/-

169/1

237/0

7/805

5.

Иван Тодоров

33/6

43/1

29/1

-/9

86/1

-/-

106/2

-/-

-/-

-/3

5/519

6.

Зорница Костадинова

39/1

78/0

49/0

110/1

-/-

-/-

-/-

-/-

-/1

269/0

5/587

7.

Васил Люнчев

48/2

75/0

92/1

121/0

-/3

-/-

273/1

-/-

-/-

-/-

5/691

8.

Иван Люцканов

45/0

97/0

30/2

221/4

-/-

-/-

-/-

-/-

-/1

189/0

5/704

9.

Господин Бодуров

13/0

75/1

82/0

-/2

-/-

-/-

-/3

-/-

-/-

58/0

4/249

10.

Николай Костов

34/0

82/0

47/0

136/2

-/-

-/-

-/65

-/-

-/-

-/-

4/341

11.

Николай Русев

25/0

68/2

34/0

137/4

-/-

-/-

-/-

-/-

-/-

-/5

4/386

12.

Калоян Йовчев

39/0

-/-

67/0

179/1

-/21

-/-

-/-

-/-

-/1

161/6

4/588

13.

Йордан Боев

114/4

132/0

49/0

220/1

-/3

-/-

-/-

-/-

-/-

-/-

4/617

14.

Мартин Иванов

26/0

242/0

42/1

-/7

-/-

-/-

-/-

-/-

-/-

-/-

3/332

15.

Калоян Иванов

93/4

-/2

80/0

183/2

-/-

-/-

-/-

-/-

-/-

-/-

3/476

16.

Станимир Николов

224/4

-/-

69/0

-/-

-/-

-/-

-/-

-/-

-/-

-/-

2/373

Задочно състезание

Name

A

B

C

D

E

F

G

H

I

J

Total

1.

Антон Анастасов

23/2

41/0

24/2

159/5

69/2

-/5

110/0

200/0

129/1

-/6

8/1000

2.

Георги Ацев

63/0

89/3

3/0

206/5

-/-

-/-

155/1

188/3

16/0

262/1

8/1246

3.

Румен Христов

36/0

43/0

46/0

72/2

230/17

-/14

254/1

209/3

-/9

-/-

7/1352

4.

Недялко Присадников

19/1

32/0

18/1

50/0

-/-

-/-

195/0

129/1

-/8

-/-

6/504

5.

Ростислав Руменов

60/4

69/0

75/0

131/5

-/-

-/-

158/3

-/-

98/1

-/-

6/853

6.

Ясен Трифонов

23/1

46/0

12/1

105/5

-/-

-/-

-/3

287/6

151/0

-/-

6/887

7.

Ивайло Караманолев

22/2

42/0

48/0

71/2

-/-

-/-

-/-

-/-

-/-

-/-

4/264

8.

Ваня Данчева

185/1

216/0

172/1

263/2

-/-

-/-

-/-

-/-

-/-

-/-

4/917

9.

Александър Гьорев

23/2

71/0

23/2

-/1

-/-

-/-

-/1

-/-

-/-

-/-

3/198

10.

Вили Христова

107/10

134/1

147/0

-/2

-/6

-/-

-/-

-/-

-/-

-/-

3/609

11.

Никола Таушанов

22/0

-/4

96/0

-/3

-/-

-/-

-/-

-/-

-/-

-/-

2/119

12.

Михаил Карев

220/0

-/-

-/-

-/-

-/-

-/-

-/-

-/-

-/-

-/-

1/220

Смесено класиране

Можете да разгледате пълното класиране за повече информация.

Ето едно нещо, което винаги ми е било интересно - временни класирания по време на състезанието =). Цъкнете на даден ред за да отворите класирането в дадената минута.

1. Първи събмити (Ацев for the win!) (5 минута)
2. Някъде в началото - Бойваленков им прави БОЙ БОЙ БОЙ! Неди следва близо (40 минута)
3. Неди повежда, първи събмити на Рости, Румен решава 3 задачи за 10 минути (60 минута)
4. Анастасов се появява сред тези с 4 задачи (75 минута)
5. Джо повежда (без грешен събмит по предадените), Анастасов и Аврамов следват (120 минута)
6. Анастасов повежда, измисляйки и написвайки Fractions за 19 минути (130 минута)
7. Още маса хора стават с по 5 задачи (150 минута)
8. Анастасов става със 7 задачи. Рости, ей тъй както си стои, става втори и отива да яде (165 минута)
9. Бойваленков си възвръща второто място с добро време. Румен цикли по 3 задачи (195 минута)
10. Анастасов предава 8-ма задача и води останалите вече с две (200 минута)
11. Ацев решава 7-ма задача и става втори. Момо брои несъкратимите дроби между 0 и 1 (210 минута)
12. След като успешно ги преброява, става втори. Аврамов кепчърва флага в киното (230 минута)
13. Аврамов кепчърва флага и в играта на Ели и Крис и става втори. Момо си припомня как се пишеше flow (250 минута)
14. След като коментира един ред, matching-ът му тръгва (най-вече за негово учудване) и става втори (260 минута)
15. Вили Христова е с 3 задачи. Браво мацка! Няма промени на челните места (295 минута)
16. Анастасов, след час и четиридесет минути мързел, взема, че печели. Момо печели присъственото като разказва мръсни вицове на Аврамов и в същото време гъделичка Джо (крайно класиране)

Задачи и Решения

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

Ето пълният архив със задачите.

Grading

Unknown Source

Statement | Archive | Online Judge

A.Grading

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

Fuel

Dean's Cup 2009

Author: Alexander Georgiev
Tags: Easy, Dynamic Programming
Statement | Archive | Online Judge

B.Fuel

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

Какво е първото нещо, което ни хрумва за тази задача? От дома на Ели тръгваме и проверяваме по колко начина можем да стигнем до крайната точка ако отием в първата бензиностанция, после ако отидем във втората бензиностанция и така нататък, до всяка от тях, която можем да достигнем с един резервоар. После за всяка от тях по аналогичен начин сумираме броя отговори за продълженията оттам. С този прост алгоритъм (който може да се реализира чрез рекурсия) бихме могли да намерим отговора на задачата.

На практика, този алгоритъм, макар и верен, не би работил за приемливо време (все пак така би трябвало да обходи близо 2¹⁰⁰⁰ пътя, което е... много. =)

Какво можем да забележим, обаче? Без значение как сме пристигнали в бензиностанция А_i, броят начини, по които можем да стигнем до края е един и същ! Следователно след като изчислим този брой за дадена бензиностанция, можем просто да го запишем в един масив. Така следващия път, когато разглеждаме същата бензиностанция, вместо да преизчисляваме всичко наново, можем просто да върнем това число.

Точно това е и идеята на динамичното оптимиране - да не преизчисляваме даден резултат отново и отново ако той няма да се променя. С тази проста допълнителна стъпка към тривиалния подход можем да решим задачата. Общата сложност на този алгоритъм е О(N2).

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

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

Shoes Easy

Dean's Cup 2009

Author: Alexander Georgiev
Tags: Easy, Search, Iteration, Sorting
Statement | Archive | Online Judge

C.ShoesEasy

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

Точно това се очаква и да направите - да прочетете входа, да сортирате числата в намаляващ ред и да изведете K-тото от тях. Просто, а? Това беше и задачата, която беше предвидена за всеки.

Може би това, че беше дадена чак трета спря някои от участниците да я решат? Това е очаквано по ACM състезания - често най-лесната задача е някъде посредата за да може да не бъде намерена и решена за 3 минути (както се случи с тази). Това е и един важен skill при този тип състезания - състезателите бързо да "познаят" кои са лесните задачи (но това по-скоро се тренира с времето). Интересното е, че четвъртата лесна задача, беше дадена чак девета (Fractions) и още по-малко хора я направиха. Но тя не беше и ЧАК толкова лесна, колкото първите три =)

Така, сега да се върна на задачата - за нея има хубав (всъщност линеен) алгоритъм; друг, който ползва бързо сортиране и е със сложност О(N∙logN), и няколко други, които или сортират с по-бавен алгоритъм, или избират даден елемент и проверяват дали той е К-ти, като са със сложност О(N2) - напълно достатъчно при дадените изисквания. При наличие на вградена сортираща функция във всеки език, поддържан от системата spoj0 (на която беше проведено и състезанието), най-добрият вариант за състезателите беше да ползват него.

Авторското решение е с написан собствен квадратен алгоритъм за сортиране (Bubble Sort). Иван ползва вградения в C++ STL sort() за същото нещо и после обръща масива (за да не се налага да предефинира comparison функцията).

Можете да намерите и алгоритъм със слжоност О(N) ето тук.
Тъй като числата бяха по-малки или равни на 1000, друга алтернатива е да се ползва Counting Sort и да се намери K-тия елемент отново с линейна сложност. Напълно ненужно.

Painball

Dean's Cup 2009

Author: Alexander Georgiev
Tags: Medium, Probability, Simple Geometry
Statement | Archive | Online Judge

D.Painball

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

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

Поради това, че мерките са в манхатаново разстояние се образува или триъгълник, или всичко останало без триъгълник. За решаване на задачата беше нужно да видим в кой от двата случая сме и после да сметнем лицето на равнобедрен правоъгълен триъгълник. Не особено сложно, нали? След това остава да разделим лицето на триъгълника (или на останалта част) на лицето на цялата дъска и сме готови!

Хм, искат ни отговора като несъкратима дроб? Това не ни затруднява кой-знае колко много, но защо го правят? Ааа да - ами за да няма проблеми при сравняване на double числа! Добре де, възможно е автора да го е домързяло да пише checker (blush).

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

Решението на тази задача е със сложност O(1).

Game

Dean's Cup 2009

Author: Alexander Georgiev
Tags: Medium, Basic Game Theory
Statement | Archive | Online Judge

E.Game

Това всъщност съществува като реална игра, която се играе с камъчета. Определят се някакви числа A₁, A₂, ..., A_K, които двамата участници могат да вземат, и начален брой камъчета в купчинката N. Който не може да вземе камъче - губи. Тя е и доста изследвана и се дава като уводна задача при теорията на игрите (поне в състезателната информатика).

Идеята на решението е следната. Ако не са останали камъчета в купчината, играчът, който е на ход очевидно губи. Нека можем да вземаме 2, 5, или 6 камъчета. Тъй като знаем, че в позиция 0 играчът губи, то ако сме в позиции 2, 5, или 6 можем лесно да спечелим, като вземем съответно толкова камъчета и оставим другия в губеща позиция. Ако ли пък нямаме ход, който закарва другия в губеща позиция (като, например, ако в купчинката има 1 камъче), казваме, че сме в губеща позиция. Така разделяме всички възможни позиции на печеливши или губещи.

По-конкретно, можем да решим задачата със следния алгоритъм: Прочитаме входа, маркираме 0 като губеша позиция, после за всяко число от 1 до N проверяваме дали имаме вземане на определен брой камъчета, което би поставило противника в губеща позиция. Ако такова има - значи текущата позиция е печеливша. В противен случай, позицията е губеща. Така в началото преизчисляваме всички възможни query-та и после константно отговаряме дали дадената позиция е печеливша или губеща за Ели (съответно дали тя или Крис печели).

До тук добре, само че как аджеба това ще мине? Ограничението за N е до 100,000,000! Сто милиона, ей! Е пък процесорът (особено i7-цата на Мило) прави по почти три милиарда операции в секунда. Добре де, простички операции, но все пак. При добра реализация това решение беше (нарочно) направено да минава.

А можем ли да не генерираме целия масив (няма ли друг живот)? Можем, разбира се! Поради малките ограничения се оказва, че ако генерираме само малка част от масива, можем да намерим закономерност в нея.

Тъй като броят момчета, които Ели и Крис могат да зачеркват са най-много десет, то дадена позиция зависи най-много от предните десет. А колко възможности за предни десет имаме? Ами 2¹⁰, тоест 1024м, тъй като всяка от предните позиции е или печеливша, или губеща, тоест две възможности на позиция.

Така ако почнем да търсим цикъл в масива, то той може да бъде дълъг най-много 1024 символа. Също така, преди началото на цикъла може да има символи, които не влизат в него - по същата логика те могат да бъдат най-много 1024 на брой. Следователно можем да пробваме за всеки брой символи извън цикъла какво е разцепването на еднакви подстрингове на останалата част - което е позната стрингова задача. Можем да приложим този алгоритъм в първите, да кажем, 5000 позиции. Тук сме допълнително улеснени от факта, че стрингът ни е бинарен (с азбука от едва 2 символа).

Оригиналната задача е давана в TopCoder, където ограниченията бяха по-брутални. Броят на възможните зачерквания беше до 20, и най-голямото зачеркване също беше 20. Query-тата бяха до 1,000,000,000. Това вече е наистина много - стандартният метод не би работил хич. Нещо повече, оптимизацията с търсенето на pattern (или цикъл ако искате) също няма да работи (повярвайте, пробвах!).

Тогава какво да правим? Ами ще търсим цикъла по-умно, като се възползваме от това, че стрингът ни е бинарен. Ще си пазим в един масив до 2²⁰ какви последователности вече сме видели. Под последователност ще разбираме дали предходните 20 позиции са били губещи/печеливши. Както по-горе коментирахме, има 2²⁰ възможности за тях. Така че след най-много 1,048,576 генерирани позиции ще намерим цикъл (по принципа на Дирихле).

Малко по-подробно да обясним този алгоритъм. Почваме стандартния алгоритъм (марикираме 0 като губеща, почваме да си циклим по позициите). Но на всяка стъпка ще гледаме какви са били предходните 20, ще изчисляваме тяхната битова маска (1 за печеливша, 0 за губеща) и ще я записваме в един масив, че сме я срещнали на позиция i. По-късно, да кажем на позиция k > i, ще срещнем същата маска. Какво означава това? Че всички позиции между i и k-1 включително са цикъла, който търсим.

След като сме го намерили, за всяко query ще можем да определим къде из цикъла (или евентуално в символите преди първото срещане на цикъла) се намираме. Но тях вече сме ги сметнали, така че знаем дали позицията е печеливша или губеща и директно можем да отговорим дали Крис или Ели ще спечели. Имплементация на този алгоритъм написаха повечето от състезателите, които решиха задачата, а също и Иван. Неговото решение можете да намерите в архива на задачата.

Travel

Dean's Cup 2009

Author: Alexander Georgiev
Tags: Hard, Dynamic Programming, RMQ
Statement | Archive | Online Judge

F.Travel

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

Всъщност, това беше неочаквано дори за мен. Ако забележите, 216-та минута даже се осъмнявам да не би time limit-ите да не са нагласени като хората, или тестовете да са грешни, и събмитвам моето решение за да проверя дали то ще върви. Въпреки, че го бяхме тествали и преди състезанието. Оправдавам нерешаването ѝ на умората след 8 решени задачи =).

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

А ето и каква е идеята. Нека сме в точка (row, col). Тук, отново като при задачата Fuel (всъщност, това е нейно доразвиване), отговорът ни за дадената позиция не зависи от пътя, който сме ползвали за да стигнем до тук. Можем да пробваме всяко от продълженията, които можем да достигнем с един резервоар, и да вземем най-добрия от техните отговори.

Това, за съжаление, би било твърде бавно - неговата сложност е от порядъка на O(N2∙M2). Какво, обаче, забелязваме? Ако имаме изчислени отговорите за всички бензиностанции в правоъгълника с горен ляв ъгъл (row, col) и долен десен (row + offsetRows, col + offsetCols), и имаме структура данни, която бързо ни казва кое е най-малкото число там, ще можем лесно да решим задачата.

Как? Тръгваме отзад-напред. Сортираме бензиностанциите по ред, а тези с равен ред - по колона. В структурата отбелязваме, че на позиция (N - 1, M - 1) можем да завършим задачата с цена 0 (тъй като по условие там няма бензиностанция, и ако вече сме в университета няма какво друго да направим, освен да завършим). После, обхождайки бензиностанциите в обратен ред, търсим за всяка от тях коя е най-малката цена, с която можем да завършим. Това правим чрез query до нашата структура данни, която по-късно ще опишем. След като намерим тази цена, добавяме към нея цената на текущата бензиностанция (все пак искаме да я ползваме) и обновяваме структурата ни данни в (row, col) с нея. Така продължаваме, докато минем всички бензиностанции. Накрая остава само да проверим какъв е отговорът на задачата ни - това става просто с query за правоъгълника с горен ляв ъгъл (0, 0) и долен десен ъгъл също (0, 0) - тоест в точката (0, 0) - което е и домът на Ели.

Сега за структурата. По принцип структура, в която бързо може да се обновява и пита за най-големия/най-малкия елемент се нарича RMQ (Range Minimim/Maximum Query). Има имплементации, които строят отговорите линейно и отговарят константно - те не ни интересуват, тъй като в случая нашите отговори се променят. Затова ни трябва двоично дърво, модификация на по-познатото индексно дърво (но не lowest bit), което Искрен нарича "марсианско" дърво (от задачата Марс). Това, което ще запазим от индексното дърво, е update() функцията - тя на практика остава същата, само че не събираме стойностите, ами ползваме min() или max().

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

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

Забележете, че това е итеративен вариант (който е малко по-бърз, в сравнение с рекурсивния) и не е много често срещан. Реализацията на Иван използва рекурсивен подход и е малко по-дълга, основно заради доста краткия update(), който може да се ползва при моя вариант. В решението на Антон Анастасов също се ползва рекурсивния вариант. И трите версии ползват памет [2 * MAX_N][2 * MAX_N], която е необходима за тези дървета (поне аз не знам начин да се направи с по-малко).

Използвайки тази нетривиална структура данни се постига сложност O(N∙logN∙M∙logM), която е и достатъчна за даденото времево ограничение.

Като цяло задачата задава някакъв насочен, ацикличен граф, с положителни или отрицателни цени на ребрата (цената може да бъде цената на върха, в който влиза реброто). Този граф, обаче, е огромен (с близо милион върха и възможност за близо 1,000,000,000,000 ребра). Освен това отрицателните цени не позволяват ползване на алгоритъма на Дейкстра, така че дори ако ограниченията бяха до 50 (където имаме 2500 върха и евентуално пълен граф) нямаше да можем да ползваме никой от познатите ни алгоритми за намиране на най-къс път за приемливо време.

Schedule

Dean's Cup 2009

Author: Alexander Georgiev
Tags: Easy, Bruteforce
Statement | Archive | Online Judge

G.Schedule

Mежду две от най-сложните задачи на състезанието (Travel и MovieSeating) беше задачата Schedule, която, за разлика от тях, беше значително по-лесна. Тя беше петата по брой решения, точно както беше планирано и от мен. Йее!

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

Очакванията ми отново бяха разбити поради факта, че почти всички състезатели предприеха подход, който съчетава брутфорс и грийди алгоритъма за един човек, вместо чист брутфорс, реализиран чрез бектрек. А ето и различните методи за решаването на задачата:

Метод 1: KISS Method (Keep it simple, stupid!)
Просто имитираме различни разпределения на мероприятията между Ели и Крис с много елементарна рекурсия, чиято имплементация можете да видите в авторското решение. Сложността на тази реализация е нещо от сорта на О(2N).

Метод 2: Greedy-Bruteforce
Това е методът, който повечето участници избраха. Итерират се всички 2^N битови маски, като мероприятията се разбиват на две независими множества - едното за Крис, другото за Ели в зависимост от това дали всеки от N-те бита е нула или едно (примерно 1 за Ели, 0 за Крис). Върху всяко от тях се прилага greedy методът в задачата за един човек - от сортираните по своя край мероприятия взимаме първото, което можем, после следващото, което започва след като първото завърши и т.н. Сложността на тази реализация е O(N∙2N).

Метод 3: Защо да е просто, като може сложно?
Това е методът, който Иван Георгиев реализира - динамично оптимиране по 3 параметъра - кое мероприятие разглеждаме в момента, кое е последното, което Ели е направила, и кое е последното, което Крис е направила. Ако се замислите, стейтът е еднозначно определен от тези три неща и така правим алгоритъм със сложност O(N3) както по време, така и по памет.

Метод 4: Да убием коня с лопатата.
Това е и хубавото решение на задачата - при реализация с интервални дървета или map/set, както и компресиране на координатите се постига O(N∙logN) сложност за по-трудния вариант на задачата с произволен брой хора (а не двама, както в случая).

Идеята е подобна на грийдито за 1 човек - сортираме интервалите по техния край - колкото по-рано свършва дадено мероприятие, толкова по-изгодно е то за нас. След това почваме да ги вземаме в този ред. За всяко взето, ъпдейтваме нашата структура от началния до крайния час на мероприятието, добавяйки 1 във всяка минута (update(a, b, +1)). За да определим дали можем или не можем да вземем дадено мероприятие, проверяваме в нашата структура дали във времевия интервал, в което е то, имаме (дори една) минута, в която имаме заетост K (при К човека, в случая 2). Тоест getMax(a, b). Ако имаме, значи сме запълнили нашия лимит и не можем да го вземем; иначе можем да го вземем и ъпдейтваме нашата структура.

Реализацията на Иван използва тази идея, но структурата му е линейна по продължителността на мероприятията. Можете да погледнете кода му за яснота.

MovieSeating

Dean's Cup 2009

Author: Alexander Georgiev
Tags: Hard, Graph, Flow
Statement | Archive | Online Judge

H.MovieSeating

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

Опитните състезатели веднага ще видят (не особено) скрития matching в задачата. Абстракцията е следната - имаме някакви обекти, които могат да бъдат свързани по някакъв начин с някаква печалба - да се максимизира тя. И докато понякога такива задачи биха могли да бъдат решени с динамично оптимиране, тази не беше такава.

Нещо повече - ограничението за K ≤ 17 е нещо, което по принцип се дава имено в динамични задачи с битова маска. В случая, обаче, то беше дадено единствено за заблуда. В тази задача колкото по-голямо е то, толкова по-добре - то всъщност (евентуално) ни намалява броя на ребрата в графа. :) Е, ако измислим как да си го построим като хората де, иначе трябва да пуснем K на брой matching-а.

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

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

Връх в лявата част на графа свързваме с връх в дясната само ако

1. имаме ребро в оригиналния граф;
и

2. ако човекът от лявата част стои на реда зад човека от дясната част.

Така си генерирахме чудничък двуделен насочен граф за всичките K реда, в който ако пуснем matching алгоритъм лесно ще намерим някое от оптималните нареждания. И тъй като ни интересува единствено броят доволни двойки, просто пускаме един flow и изпечатваме неговия резултат на екрана.

Моята импелемeнтция реализира гореописаното "хитро" решение. Решението на Иван пък пуска K на брой независими мачинга, което, ако е достатъчно добре написано, също минаваше. Забележете, че вторият вариант е по-бавен, особено ако ограниченията за K бяха по-големи. Сложността на първото решение е O(F), където F е сложността на flow/matching алгоритъма, докато при второто е O(K∙F).

Fractions

Dean's Cup 2009

Author: Alexander Georgiev
Tags: Easy, Simple Math, Primes
Statement | Archive | Online Judge

I.Fractions

Тази задачка е взета почти едно към едно от упражненията ни по Алгебра 2 =)

Идеята е доста проста - за да намерим колко несъкратими дроби 0 < P/Q < 1 има, за които P * Q = N!, нека първо факторизираме N!.

Така получаваме 2^P₁ * 3^^P₂ * 5^P₃ * ... * 241^P_K, където 241 е последното просто число, по-малко от 250, а P₁, P₂, ..., P_K са колко пъти се среща дадено просто число във факторизацията на N! (евентуално нула, ако простото число е по-голямо от N).

Лесно забелязваме, че за да са несъкратими дробите, то всичките двойки трябва да са или в числителя, или в знаменателя, всички тройки също, всички петици също и т.н. Ако имаме numPrimes на брой прости числа, по-малки или равни на N (тоест чиято степен е по-голяма от нула), то имаме общо 2^numPrimes възможности за дроби.

Не всички от тях обаче са в интервала (0, 1). Ще пресметнем колко от тях са в него. Взимаме произволна дроб P/Q. Ако тя е в интервала, то нейната обратна Q/P не е. Ако пък не е, взимаме Q/P, която е. Следователно само половината от дробите са в интервала (0, 1) и отговорът ни за N е 2^{numPrimes - 1}.

Остава да сумираме това за всяко N и сме готови.

Имплементация на 20 (non-blank) реда можете да намерите в архива, като имплементацията на Java на Иван (18 non-blank реда) се подсигурява за overflow и би работила дори за значително по-големи N. При N ≤ 250, обаче, и 64-битов тип върши чудесна работа.

NinePoints

Dean's Cup 2009

Author: Ivaylo Strandjev
Tags: Hard, Geometry
Statement | Archive | Online Judge

J.NinePoints

Задачата е на Ивайло Странджев и накратко се решава като се игнорира половината условие, което е сбъркано, и се сметнат два вектора =)