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

Dean's Cup, 2013

На 1. Декември, 2013г. се проведе десетото (юбилейно!) издание на Турнира за Купата на Декана на ФМИ. В него взеха участие близо 35 човека - студенти от ФМИ, както и ученици и студенти от други университети. Около две трети от участниците бяха представители на факултета, които се бориха за купата на присъственото състезание.

Този път нивото на задачите се получи много близко до това, което искахме - всяка задача беше решена, като няколко състезателя бяха готови с 5-те по-лесни задачи до 100-тната минута. Може би лесните задачи бяха малко по-сложни, отколкото трябваше - моите лични очаквания бяха, че ще има човек с над половината задачи на първия час. Множеството неуспешни събмити по три от лесните (но, както се оказа, относително tricky) задачи: Giraffe, GuessGame и Increase, като че ли забавиха състезателите.

Приятна изненада беше, че този път нямаше почти никакви проблеми със системата - тя успя да падне едва 5 секунди преди края и не повлия на класирането.

Победители

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

В официалното състезание шампионът от предните две години Влади Харалампиев защити титлите си и отново грабна първото място. За това му помогнаха както доброто начало (5 задачи на 60-тата минута), така и решаването на три от сложните задачи (Tribes, Birthday, и Unlock). Браво, Влади!

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

Третото място отиде при Ясен Трифонов, който пък беше единственият от присъствените състезатели, справил се с потоковата задача в темата (задачата DotA).

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

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

На второ място в онлайн състезанието беше Елица Банкова, която изпревари много от по-опитните/известните състезатели. Тя бе и дамата, а също така и ученичката с най-добро постижение на състезанието. Поздравления!

На трето място се класира представителят на ученическия национален отбор Енчо Мишинев, който, макар и да имаше правилната идея по задачата DotA, го домързя да я направи. Мързел!

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

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

Name Solved Time A B C D E F G H I J K Att.
1 Владислав Харалампиев 9 820 13 (0) 9 (0) 60 (0) - (2) 42 (0) 257 (1) 100 (0) - () 75 (0) 136 (1) 25 (3) 16
2 Даниел Балчев 8 1091 17 (0) 51 (2) 69 (0) 225 (0) 97 (2) 284 (1) - (4) - () 135 (3) - () 10 (2) 22
3 Ясен Трифонов 7 739 17 (0) 27 (0) 144 (2) - () 50 (0) - () - () 247 (1) 106 (0) - (3) 6 (4) 17
4 Красимир Георгиев 6 357 32 (0) 18 (0) 76 (0) - () 53 (1) - (7) - () - () 113 (1) - () 22 (0) 15
5 Калоян Дърмонев 6 895 72 (1) 59 (3) 137 (2) - () - (1) 282 (1) - () - () 164 (0) - () 19 (1) 15
6 Гален Георгиев 6 1016 12 (0) 80 (3) 258 (1) - () 188 (3) - () - () - () 148 (1) - () 68 (5) 19
7 Владимир Владимиров 6 1032 32 (0) 40 (3) 160 (0) - () 170 (14) - (6) - () - () 116 (0) - () 52 (6) 35
8 Ивайло Чернев 6 1114 35 (0) 23 (1) 284 (0) - () 163 (0) - () - () - () 263 (7) - () 63 (6) 20
9 Никола Таушанов 5 265 9 (0) 24 (1) 47 (0) - () - (21) - () - () - () 131 (0) - () 13 (1) 28
10 Радослав Комитов 5 437 33 (0) 18 (0) - (1) - () 84 (1) - () - () - () 121 (0) - () 100 (3) 10
11 Мария Митева 5 1152 64 (3) 130 (2) 290 (1) - () - (1) - () - () - () 107 (0) - () 298 (7) 19
12 Елена Денева 4 349 71 (0) 102 (3) - () - () - (3) - (4) - () - () 60 (1) - () 34 (0) 15
13 Тодор Бончев 3 634 56 (0) 119 (4) - () - () 297 (4) - () - () - () - (4) - () - (17) 32
14 Гергана Тодорова 2 85 17 (0) - (4) - () - () - (6) - () - () - () - () - () 67 (0) 12
15 Атанас Атанасов 2 200 7 (0) - (2) - () - () - () - () - () - () - (3) - () 52 (7) 14
16 Ивайло Мариновски 2 310 152 (2) - (16) - () - () - () - () - () - () - () - () 18 (5) 25
17 Пламен Начев 2 395 36 (0) - (5) - () - () - () - () - () - () - (3) - () 198 (8) 18
18 Николай Велков 1 139 - (4) - (3) - () - () - (1) - () - () - () - () - () 79 (3) 12
19 Момчил Сулов 1 148 - (1) - (1) - (1) - () - (1) - (1) - () - () - () - () 148 (0) 6

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

Name Solved Time A B C D E F G H I J K Att.
1 Веселин Георгиев 9 1352 8 (0) 49 (3) 62 (0) - () 100 (2) 194 (3) - () 285 (0) 201 (0) 256 (0) 13 (1) 18
2 Елица Банкова 6 588 18 (0) 32 (0) 223 (0) - () 163 (0) - () - () - () 88 (1) - () 42 (0) 7
3 Енчо Мишинев 6 660 6 (0) 18 (0) 151 (2) - () 67 (1) - () - () - () 113 (0) - () 62 (9) 18
4 Паолина Гаджулова 5 629 18 (0) 86 (5) - () - () 129 (2) - () - () - () 169 (0) - () 64 (1) 13
5 Димитър Карев 4 605 14 (0) 74 (6) - () - () 242 (0) - (4) - () - () - (4) - () 133 (1) 19
6 Валери Цолов 3 483 28 (0) - (8) - () - () - () - () - () - () 223 (0) - () 131 (5) 16
7 Стефан 3 724 189 (0) 236 (4) - () - () - (1) - () - () - () - () - () 198 (1) 9
8 Ангел Николов 3 754 184 (0) - () - () - () 146 (4) - () - () - () - () - () 163 (9) 16
9 Владимир Начев 3 1047 211 (7) 280 (12) - () - () - () - () - () - () - (6) - () 115 (3) 31
10 Ивайло Мариновски 2 310 152 (2) - (16) - () - () - () - () - () - () - () - () 18 (5) 25
11 Ралица Манолова 2 372 203 (1) - (7) - () - () - () - () - () - () - () - () 129 (1) 11
12 Емил Гелев 0 - () - () - () - () - () - () - () - () - (8) - () - (1) 9
13 Христо Танев 0 - () - () - () - () - () - () - () - () - () - () - (1) 1
14 Даниел Величков 0 - (1) - (2) - () - () - () - () - () - () - () - () - (1) 4

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

  1. Класиране към 115-та минута
  2. Класиране към 150-та минута
  3. Класиране към 210-та минута
  4. Класиране към 240-та минута
  5. Класиране към 270-та минута
  6. Крайно класиране

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

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

Odds

Dean's Cup 2013

Author: Alexander Georgiev
Tags: Trivial, Iteration, Simple Math
Statement | Archive | Online Judge
A. Odds

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

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

GuessGame

Dean's Cup 2013

Author: Alexander Georgiev
Tags: Easy, BruteForce
Statement | Archive | Online Judge
B. GuessGame

Това беше пример за задача, в която трябва да жертваме изчислителна сложност, за да направим кода ни по-лесен.

Единият вариант е да решим задачата с O(N), където N е броят вече зададени въпроси. За целта трябва да имплементираме логика, която действа адекватно спрямо отговорите на Крис. Почти всички състезатели тръгнаха по този път, тъй като той е интуитивният и оптимален (откъм бързодействие) начин за решаване на задачата. Това, разбира се, не е ненаправимо, но включва много if-ове и е лесно за объркване (даже много лесно, както се видя от броя събмити по задачата). А дори не бях дал възможността Крис да е отговорила с 0 на някои от въпросите!

Вместо това ще направим решението доста по-бавно, но значително по-просто и без почти никаква логика. Нека числото на Крис е между 1 и M (като в случая M е 1000). Защо да не пробваме всяко възможно число между 1 и M и да проверим дали N-те отговора на Крис са консистентни с нашето предположение? Така можем да напъхаме в един списък/вектор/масив числата, които са били консистентни, и накрая единствено трябва да проверим дали той съдържа:
  • нула елемента, в който случай връщаме -2;
  • един елемент, в който случай връщаме въпросния елемент;
  • повече от един елемент, в който случай връщаме -1;
И това е! Така сложността е O(N∙M) на тест, но за дадените ограничения това е напълно достатъчно.

Meeting

Dean's Cup 2013

Author: Alexander Georgiev
Tags: Easy/Medium, Dynamic Programming
Statement | Archive | Online Judge
C. Meeting

Всеки път, когато ви искат някакъв вид "оптимално разпределение" се замислете дали задачата не може да стане с динамично оптимиране. Наистина, чрез него можем да проверим всички разпределения, като сред тях намерим и оптималното такова.

Тази задача не е изключение и се решава именно така. Нещо повече, тъй като целта ни беше да е достъпна за повече хора, от състезателите не се изискваше да приложат никоя от възможните "допълнителни" оптимизации - решение със сложност O(T∙N∙K2) минаваше!

Нужната ни таблица е двумерна и е от вида dyn[group][remaining], като съдържа отговорите на въпросите "Какъв е оптималният отговор оттук нататък, ако сме стигнали до група group и ни остават remaining милиционера?". Наистина, независимо как сме разпределили милиционерите в предишните групи, отговорът за останалите групи е еднозначно определен от броя милиционери, които можем да ползваме. Таблицата заема памет в порядъка на O(N∙K).

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

Накрая, сложността за всеки от тестовете е броят клетки на динамичната таблица, умножен по броя операции, които са нужни за всяка клетка - тоест O(N∙K∙K).

Boats

Dean's Cup 2013

Author: Ivaylo Strandjev
Tags: Medium/Hard, Geometry, Graph, Dijkstra
Statement | Archive | Online Judge
D. Boats

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

Задача, в която ни искат "най-малкото време, за което можем да се предвижим от едно място до друго", най-вероятно се налага да приложим някой от алгоритмите за намиране на най-къс път в граф. Почти очевидно за по-опитните състезатели е, че тази задача се решава с алгоритъма на Дейкстра. Самата имплементация на алгоритъма също изисква съвсем дребна промяна на станартния алгоритъм. Защо, тогава, толкова малко хора я направиха?

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

Това може да стане по няколко начина. Единият е сравнително стандартен - правим троично търсене за да намерим времето, в което лодките ще са най-близо една до друга. Ако в това време лодките са на повече от R разстояние, то не можем да се прехвърлим от едната лодка в другата. В противен случай правим две двоични търсения - едно за да намерим левия край, и още едно за а намерим десния край на интервала. (Всъщност, сега като се замисля, тъй като лодките не променят скоростта и посоката си, то "най-близката" точка ще е именно в центъра на интервала (освен ако той не е безкраен). Така, намирайки единия край и знаейки центъра, лесно можем да намерим и другия край). Този начин, за съжаление, е твърде бавен за тази задача - нужно е да го направим за всяка двойка лодки - а те могат да бъдат от порядъка на O(N2). Прибавяйки и логаритъма, който е нужен за троичното и двоичното търсене, общата сложност на тест става O(N2log(1/A)), където A е желаната от нас точност.

Другият начин е чрез решаване на квадратно уравнение. Проблемът при него е, че трябва много да внимаваме при съставянето и имплементацията му. За сметка на това чрез него можем да намерим интервала на пресичане на две лодки за O(1), което вече прави решението достатъчно бързо.

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

Increase

Dean's Cup 2013

Author: Alexander Georgiev
Tags: Medium, Binary Search
Statement | Archive | Online Judge
E. Increase

Задачата Increase изискваше от състезателите да съчетаят два много прости и известни алгоритъма, за да постигнат достатъчно бързо решение.

Първият алгоритъм (по-скоро техника) беше двоично търсене. Както в много задачи, изискващи двоично търсене, и в случая търсенето беше по отговора на задачата. Наистина, ако сме фиксирали стойността на K, можем без особено главоболия да проверим дали тя ни върши работа. Лесно можем да се убедим, че ако имаме отговор с K, то имаме отговор за K + 1 - например същият интервал от последователни елементи на списъка - неговата сума може само да се е увеличила. Аналогично, ако нямаме отговор за K, то нямаме отговор и за K - 1. Така виждаме, че отговорът на въпроса "Имаме ли отговор при дадено K?" е монотонен - до някоя стойност е "не", после става "да" и не се променя.

Сега, имайки фиксирано K, можем да изчислим новите стойности на елементите на списъка по дадената в условието формула. Остава да проверим дали има подинтервал на масива със стойност по-голяма или равна на M. За това пък има друг стандартен алгоритъм, който можете да разгледате в детайли тук.

Сложността на описания алгоритъм (с известни уговорки за log(M))) е O(N∙logM).

Tribes

Dean's Cup 2013

Author: Ivaylo Strandjev
Tags: Medium/Hard, Data Structures, Beap
Statement | Archive | Online Judge
F. Tribes

За решението на тази задача беше нужно единствено имплементирането на малко по-екзотична структура данни, подобна на heap, която обаче поддържа и бърза операция за обединяване. Пример за такава структура е (имплементираната в авторското решение) Leftist Tree или по-стандартната биномна пирамида, които позволяват merge на две такива структури за O(logN). Така сложността на цялата задача става O(Q∙logN), където Q е броят на query-тата, а N - броят на хората.

Не особено силните тестове (към които добавих тест, който да убива най-тривиалните O(N2) решения, но авторът в последствие е решил да махне) позволиха на някои от състезателите да минат задачата с решения, които не постигат тази сложност в най-лошия случай. Едно от миналите решения, например, ползва свързани списъци, чиито merge е O(L1 + L2), където L1 и L2 са дължините на списъците.

Birthday

Dean's Cup 2013

Author: Ivaylo Strandjev
Tags: Hard, Graph, 2-SAT
Statement | Archive | Online Judge
G.Birthday

Правилата, зададени в задачата, образуват конюнкция от дизюнкции (йее, Дискретна Математика!) от вида (Vi or Vj) and (Vk or Vp) and ... and (Vy or Vz), като, разбира се, някои от променливите може да присъстват със своето отрицание. По-специфично, нека разгледаме какви са импликациите на всяко от трите изисквания:
  1. Ако X иска Y, то от това, че X присъства, би следвало, че и Y присъства (XY). Също така, ако Y не присъства, то и X не присъства (!Y!X);
  2. Ако X не иска Y, то от това, че X присъства, би следвало, че Y не присъства (X!Y). Също така, ако Y присъства, то значи X не присъства (Y!X);
  3. Ако трябва поне единият от X и Y да присъства, то от това, че X не присъства, би следвало, че Y присъства (!XY). Сходно, ако Y не присъства, следователно X присъства (!YX).
На пръв поглед, проблемът е еквивалентен на една от най-популярните NP-пълни задачи - задачата за удовлетворяване на булеви изрази. Тази негова инстанция, обаче (където във всяка от дизюнкциите имаме по най-много две променливи), също позната като 2-SAT, има полиномиално (при това много бързо) решение.

Накратко, решението е следното:
  1. Строим насочен граф от импликациите, съдържащ
    2*N върха -- по един връх за всяка променлива (човек) и за нейното отрицание.
  2. Намираме силно-свързаните компоненти в графа. Това можем да направим, например, със сравнително лесният алгоритъм на Косаражу.
    • Ако една променлива попадне в една и съща компонента с нейното отрицание, то задачата няма решение. Наистина, ако са в една компонента, то имаме импликация от вида X!X -- демек, ако X дойде, то тогава X няма да дойде.
    • Ако никой връх не е в една компонента със своето отрицание, то със сигурност имаме решение.
  3. Обхождаме компонентите в реда, в който са генерирани от алгоритъма на Косаражу (този ред е специален, тъй като компонентите са топологично-сортирани). За всяка променлива X със сигурност ще срещнем или (компонентата на) X преди (компонентата на) !X, или (компонентата на) !X преди (компонентата на) X, тъй като вече проверихме, че те са в различни компоненти. Ако срещнем X преди неговото отрицание, то не включваме X в отговора; в противен случай го включваме.
Това е! Сложността е O(N + М) за цялата задача, като се доминира от намирането на силно-свързаните компоненти.

DotA

Dean's Cup 2013

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

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

Вместо това ще бъдем само частично алчни. Ще пробваме да фиксираме всеки от отборите и да проверим дали той може да бъде победител. Нека фиксираният отбор е X. Логично, след като сме го "нарочили" да е краен победител, то ще направим така, че този тим спечели всичките си оставащи мачове.

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

За всеки от оставащите отбори броим колко мача вече са спечелили. Ако има отбор с ≥ SX точки от досега изиграните мачове, то очевидно отбор X не може да стане краен победители и спираме до тук.

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

Графът, който трябва да построим за потока в тази задача, всъщност е много подобен на този от задачата

Snow Cleaning

Dean's Cup 2012

Author: Alexander Georgiev
Tags: Hard, Graph, Matching, Eulerian Tour
Statement | Archive | Online Judge
SnowCleaning от миналата година. Отново имаме известен брой ребра (оставащите мачове), които трябва да насочим (да изберем победител). Както и при нея, тук ще построим двуделен граф, в който от едната страна стоят ребра (свързани със source-а с капацитет 1), а от другата ще са отборите (свързани със sink-а с капацитет максималния брой оставащи мачове, които могат да спечелят). Ако съществува максимален поток, то фиксираният отбор X може да бъде краен победител; в противен случай - не може.

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

Най-лесният алгоритъм за намиране на поток в двуделен граф е със сложност O(F∙(N + M)), където F е резултатният флоу, N е броят върхове в двуделния граф, а M е броят ребра в двуделния граф. Сравнително лесно можем да видим, че двуделният граф е много рядък - всеки връх от лявата страна е свързан с точно два върха от дясната. Така можем да намерим, че както броят върхове, така и броят ребра в двуделния граф са от порядъка на O(N + R). Нещо повече, в най-лошия случай F = R, тъй като капацитетът от сорса към ребрата е 1. Така виждаме, че сложността на всеки от потоците е O(R∙(N + R)).

Тъй като трябва да извършим поток за потенциално всеки от отборите, то сложността за тест е O(N∙R∙(N + R)). Това на пръв поглед е много, но тъй като почти винаги потокът действа далеч по-бързо от очакваната O(F∙(N + M)) сложност, реално върви задоволително бързо.

Pairs

Dean's Cup 2013

Author: Alexander Georgiev
Tags: Easy, Iteration, Greedy
Statement | Archive | Online Judge
I.Pairs

Това беше планирано като третата най-лесна задача в темата (след Odds и Giraffe). Реално съществува много добър алгоритъм, който решава задачата с O(N) време и O(1) памет (вижте решението на Поли за насоки), но дадените ограничения изобщо не го изискваха.

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

Сложността при тази имплементация е O(N∙logN) по време и O(N) по памет.

Unlock

Dean's Cup 2013

Author: Ivaylo Strandjev
Tags: Medium/Hard, Dynamic Programming
Statement | Archive | Online Judge
J.Unlock

Сравнително малките ограничения (до 16 точки) веднага издаваха на по-опитните състезатели, че задачата може да бъде решена с динамично по битова маска. Наистина, стейтът dyn[mask][last] (където mask е битовата маска на вече "покритите" точки, а last е последната използвана точка) е достатъчен.

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

Вместо това, ще изнесем тези изчисления преди самото динамично. За всеки две точки можем да намерим маската на покритите при тяхното свързване. Това можем да направим с O(N3) и да запазим в двумерен масив masks[N][N].

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

Giraffe

Dean's Cup 2013

Author: Ivaylo Strandjev
Tags: Trivial, Tricky, Ad-Hoc
Statement | Archive | Online Judge
K.Giraffe

Аз (демек Александър Георгиев, защото аз пиша анализите) още от началото не харесвам тази задача и бях против нейното даване. След 2-3 мейла и няколко стотин реда спор в чата, в крайна сметка не можах да изляза на глава с Иво, та ей я на. Надявам се сте се забавлявали с нея.
Страницата е посетена 1543 пъти.