Турнир за Купата на Декана, 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 |
Смесено класиране
- Класиране към 115-та минута
- Класиране към 150-та минута
- Класиране към 210-та минута
- Класиране към 240-та минута
- Класиране към 270-та минута
- Крайно класиране
Задачи и Решения
Ето пълен архив със задачите и решенията.Odds
Dean's Cup 2013
Author: Alexander Georgiev
Tags: Trivial, Iteration, Simple Math
Statement | Archive | Online JudgeA. Odds
Задачата Odds беше по дизайн най-лесната задача в темата. Единственото, което състезателите трябваше да направят за нейното решаване, беше да съобразят, че за да се превърне четно число в нечетно трябва да го съберат с нечетно. И тъй като имаме горна граница на желаната сума, за нас е най-изгодно да го съберем с най-малкото нечетно число сред входните такива.Odds
Dean's Cup 2013
Author: Alexander GeorgievTags: Trivial, Iteration, Simple Math
Statement | Archive | Online Judge
Така трябва да минем веднъж през входните числа и да намерим най-малкото нечетно, след което да минем втори път и да преброим нечетните, а също така и четните, които, събрани с най-малкото нечетно, дават сума по-малка или равна на M.
Сложността на този алгоритъм е
O(N).GuessGame
Dean's Cup 2013
Author: Alexander Georgiev
Tags: Easy, BruteForce
Statement | Archive | Online JudgeB. GuessGame
Това беше пример за задача, в която трябва да жертваме изчислителна сложност, за да направим кода ни по-лесен.GuessGame
Dean's Cup 2013
Author: Alexander GeorgievTags: Easy, BruteForce
Statement | Archive | Online Judge
Единият вариант е да решим задачата с
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 JudgeC. Meeting
Всеки път, когато ви искат някакъв вид "оптимално разпределение" се замислете дали задачата не може да стане с динамично оптимиране. Наистина, чрез него можем да проверим всички разпределения, като сред тях намерим и оптималното такова.Meeting
Dean's Cup 2013
Author: Alexander GeorgievTags: Easy/Medium, Dynamic Programming
Statement | Archive | Online Judge
Тази задача не е изключение и се решава именно така. Нещо повече, тъй като целта ни беше да е достъпна за повече хора, от състезателите не се изискваше да приложат никоя от възможните "допълнителни" оптимизации - решение със сложност
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 JudgeD. Boats
Това беше (малко изненаващо за нас) най-малко решаваната задача в състезанието. Тя получи едва едно вярно решение в рамките на петте часа, а не изискваше особено сложен или нестандартен алгоритъм. Weird! Може би геометрията наплаши хората?Boats
Dean's Cup 2013
Author: Ivaylo StrandjevTags: Medium/Hard, Geometry, Graph, Dijkstra
Statement | Archive | Online Judge
Задача, в която ни искат "най-малкото време, за което можем да се предвижим от едно място до друго", най-вероятно се налага да приложим някой от алгоритмите за намиране на най-къс път в граф. Почти очевидно за по-опитните състезатели е, че тази задача се решава с алгоритъма на Дейкстра. Самата имплементация на алгоритъма също изисква съвсем дребна промяна на станартния алгоритъм. Защо, тогава, толкова малко хора я направиха?
Проблемът идва от строенето на самия граф. Времената за прехвърляне от лодка в лодка са ни имплицитно зададени чрез движението на лодките. По-точно, за всеки две лодки или няма възможност (когато и да било) да се прехвърлим от едната в другата, или съществува точно определен времеви интервал, в който можем да направим това. Преди да можем да приложим Дейкстрата трябва да намерим тези интервали за всеки две лодки.
Това може да стане по няколко начина. Единият е сравнително стандартен - правим троично търсене за да намерим времето, в което лодките ще са най-близо една до друга. Ако в това време лодките са на повече от R разстояние, то не можем да се прехвърлим от едната лодка в другата. В противен случай правим две двоични търсения - едно за да намерим левия край, и още едно за а намерим десния край на интервала. (Всъщност, сега като се замисля, тъй като лодките не променят скоростта и посоката си, то "най-близката" точка ще е именно в центъра на интервала (освен ако той не е безкраен). Така, намирайки единия край и знаейки центъра, лесно можем да намерим и другия край). Този начин, за съжаление, е твърде бавен за тази задача - нужно е да го направим за всяка двойка лодки - а те могат да бъдат от порядъка на
O(N2). Прибавяйки и логаритъма, който е нужен за троичното и двоичното търсене, общата сложност на тест става O(N2∙log(1/A)), където A е желаната от нас точност.Другият начин е чрез решаване на квадратно уравнение. Проблемът при него е, че трябва много да внимаваме при съставянето и имплементацията му. За сметка на това чрез него можем да намерим интервала на пресичане на две лодки за
O(1), което вече прави решението достатъчно бързо.При този вариант можем значително да си опростим сметките, като, докато изчисляваме разстоянието от дадена лодка до всички останали, фиксираме нейната позиция и променим релативните скорости на останалите спрямо нея. Така трябва да намерим сечението на окръжност (с център фиксираната лодка) и права (всяка от другите лодки с новата им скорост).
Increase
Dean's Cup 2013
Author: Alexander Georgiev
Tags: Medium, Binary Search
Statement | Archive | Online JudgeE. Increase
Задачата Increase изискваше от състезателите да съчетаят два много прости и известни алгоритъма, за да постигнат достатъчно бързо решение.Increase
Dean's Cup 2013
Author: Alexander GeorgievTags: Medium, Binary Search
Statement | Archive | Online Judge
Първият алгоритъм (по-скоро техника) беше двоично търсене. Както в много задачи, изискващи двоично търсене, и в случая търсенето беше по отговора на задачата. Наистина, ако сме фиксирали стойността на 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 JudgeF. Tribes
За решението на тази задача беше нужно единствено имплементирането на малко по-екзотична структура данни, подобна на heap, която обаче поддържа и бърза операция за обединяване. Пример за такава структура е (имплементираната в авторското решение) Leftist Tree или по-стандартната биномна пирамида, които позволяват merge на две такива структури за Tribes
Dean's Cup 2013
Author: Ivaylo StrandjevTags: Medium/Hard, Data Structures, Beap
Statement | Archive | Online Judge
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 JudgeG.Birthday
Правилата, зададени в задачата, образуват конюнкция от дизюнкции (йее, Дискретна Математика!) от вида (Vi or Vj) and (Vk or Vp) and ... and (Vy or Vz), като, разбира се, някои от променливите може да присъстват със своето отрицание. По-специфично, нека разгледаме какви са импликациите на всяко от трите изисквания:Birthday
Dean's Cup 2013
Author: Ivaylo StrandjevTags: Hard, Graph, 2-SAT
Statement | Archive | Online Judge
- Ако X иска Y, то от това, че X присъства, би следвало, че и Y присъства (X → Y). Също така, ако Y не присъства, то и X не присъства (!Y → !X);
- Ако X не иска Y, то от това, че X присъства, би следвало, че Y не присъства (X → !Y). Също така, ако Y присъства, то значи X не присъства (Y → !X);
- Ако трябва поне единият от X и Y да присъства, то от това, че X не присъства, би следвало, че Y присъства (!X → Y). Сходно, ако Y не присъства, следователно X присъства (!Y → X).
Накратко, решението е следното:
- Строим насочен граф от импликациите, съдържащ
2*N върха -- по един връх за всяка променлива (човек) и за нейното отрицание. - Намираме силно-свързаните компоненти в графа. Това можем да направим, например, със сравнително лесният алгоритъм на Косаражу.
- Ако една променлива попадне в една и съща компонента с нейното отрицание, то задачата няма решение. Наистина, ако са в една компонента, то имаме импликация от вида X → !X -- демек, ако X дойде, то тогава X няма да дойде.
- Ако никой връх не е в една компонента със своето отрицание, то със сигурност имаме решение.
- Обхождаме компонентите в реда, в който са генерирани от алгоритъма на Косаражу (този ред е специален, тъй като компонентите са топологично-сортирани). За всяка променлива X със сигурност ще срещнем или (компонентата на) X преди (компонентата на) !X, или (компонентата на) !X преди (компонентата на) X, тъй като вече проверихме, че те са в различни компоненти. Ако срещнем X преди неговото отрицание, то не включваме X в отговора; в противен случай го включваме.
O(N + М) за цялата задача, като се доминира от намирането на силно-свързаните компоненти.DotA
Dean's Cup 2013
Author: Alexander Georgiev
Tags: Hard, Graph, Flow
Statement | Archive | Online JudgeH.DotA
В тази задача трябва да бъдем алчни, но не твърде алчни. Съществуват няколко решения, които са базирани изцяло на greedy алгоритми, но са грешни. При създаването на тестовете се опитах да убия тези от тях, за които се сетих, така че би трябвало да не минават.DotA
Dean's Cup 2013
Author: Alexander GeorgievTags: Hard, Graph, Flow
Statement | Archive | Online Judge
Вместо това ще бъдем само частично алчни. Ще пробваме да фиксираме всеки от отборите и да проверим дали той може да бъде победител. Нека фиксираният отбор е X. Логично, след като сме го "нарочили" да е краен победител, то ще направим така, че този тим спечели всичките си оставащи мачове.
Така X ще има определен брой точки от вече изиграните, а също така някакъв допълнителен брой от оставащите (които, казахме, че ще спечели). Нека сумата на тези точки (тоест максималния брой точки, който този отбор би могъл да спечели) е SX. За да стане краен победител то трябва всички останали отбори да съберат стриктно по-малко от него точки.
За всеки от оставащите отбори броим колко мача вече са спечелили. Ако има отбор с ≥ SX точки от досега изиграните мачове, то очевидно отбор X не може да стане краен победители и спираме до тук.
В противен случай, за всеки от останалите отбори се получава някаква горна граница на броя оставащи мачове, които могат да спечелят. А как решаваме задачи, в които имаме горни ограничения (капацитети) на върховете или ребрата? С flow, разбира се!
Графът, който трябва да построим за потока в тази задача, всъщност е много подобен на този от задачата
Snow Cleaning
Dean's Cup 2012
Author: Alexander GeorgievTags: Hard, Graph, Matching, Eulerian Tour
Statement | Archive | Online Judge
Така, за всеки тест и всеки отбор, трябва да пуснем по един флоу. Можем да си спестим част от работата, като забележим, че някои от изчисленията ще са едни и същи независимо кой отбор сме фиксирали. Такива изчисления са, например, строенето на графа (само капацитетите са зависими от фиксирания отбор), и броят спечелени до сега победи / броят оставащи мачове.
Най-лесният алгоритъм за намиране на поток в двуделен граф е със сложност
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 JudgeI.Pairs
Това беше планирано като третата най-лесна задача в темата (след Odds и Giraffe). Реално съществува много добър алгоритъм, който решава задачата с Pairs
Dean's Cup 2013
Author: Alexander GeorgievTags: Easy, Iteration, Greedy
Statement | Archive | Online Judge
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 JudgeJ.Unlock
Сравнително малките ограничения (до 16 точки) веднага издаваха на по-опитните състезатели, че задачата може да бъде решена с динамично по битова маска. Наистина, стейтът Unlock
Dean's Cup 2013
Author: Ivaylo StrandjevTags: Medium/Hard, Dynamic Programming
Statement | Archive | Online Judge
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 JudgeK.Giraffe
Аз (демек Александър Георгиев, защото аз пиша анализите) още от началото не харесвам тази задача и бях против нейното даване. След 2-3 мейла и няколко стотин реда спор в чата, в крайна сметка не можах да изляза на глава с Иво, та ей я на. Надявам се сте се забавлявали с нея.Giraffe
Dean's Cup 2013
Author: Ivaylo StrandjevTags: Trivial, Tricky, Ad-Hoc
Statement | Archive | Online Judge
Страницата е посетена 2364 пъти.