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

Dean's Cup, 2018

С малко повече от месец по-късно от обикновеното (на 20. Януари, вместо стандартно началото на Декември) се проведе петнадесетото издание на Турнира за Купата на Декана. Тази година беше десетата, в която аз и Иво даваме задачи, което беше малък milestone за нас.

Победители

Получи се хубаво състезание, в което хората в топ 10 бяха добре разделени - или със задача, или с поне 180 наказателни минути, с изключение на 6-7 място, които бяха с над час разлика.

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

В присъственото състезание победител стана първокурсникът Виктор Терзиев, който в последните 5 минути успя да предаде една от двете задачи, които пробваше да събмитне над час. Така той стана с 9 задачи (и ужасно наказателно време). Ироничното е, че не успя да предаде една от най-лесните задачи в темата, и въпреки това накрая водеше с една задача на втория в присъственото състезание - двукратния (и миналогодишен) шампион Даниел Атанасов. На трето място беше съотборникът на Дани - Иво Дилов, който също беше с 8 задачи, но значително по-лошо наказателно време от него. Челната петица беше допълнена от Антон Чернев (съотборник на Дани и Иво) със 7 задачи и Иван Ганев (съотборник на Виктор) също с толкова, но по-лошо време.

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

В задочното състезание победител заслужено стана многократният медалист от IOI Енчо Мишинев от Ямбол, който успя да се справи с всички 11 задачи за съвсем малко над четири часа! Втори с една задача по-малко (но 13 неуспешни събмита по нея, като някои от тях много близо до верни) се нареди победителят от миналата година Радослав Димитров от Пловдив. Трети със 7 решени задачи стана Петър Няголов от Русе, следван почти веднага от Момчил Пейчев от Варна. Петицата заформи бившият носител на Купата на Декана от 2005-та година - Веселин Георгиев, също със 7 задачи като Петър и Момчил, но много по-лошо време.

Награди

Наградите за присъственото състезание бяха спонсорирани от ФМИ, като най-добре представилите се състезатели ще бъдат наградени на тържеството по повод 24-ти Май (а може и по-рано, ще видим). За тях са предвидени парични награди, и разбира се, купа за победителя.

За участниците в онлайн изданието наградите ще бъдат дадени от авторите на задачите, които ще дарят хонорара си за подготовката на състезанието за целта. Тази година и ФМИ се включва с част от средствата за тази награда.

Наградите тази година бяха:

• За onsite състезанието:
  
  1. Първо място: 750 лв.
  2. Второ място: 500 лв.
  3. Трето място: 350 лв.
  4. Четвърто място: 250 лв.
  5. Пето място: 150 лв.
• За online състезанието:
  
  1. Първо място: Смартфон Xiaomi Note 6 Pro
  2. Второ място: Wireless слушалки Sony WH-CH700N
  3. Трето място: Кецове Puma Suede Classic NYC

Класиране

Rank	Name	Solved	Time	A	B	C	D	E	F	G	H	I	J	K
1	Енчо Мишинев	11	1257	2 (3:18)	2 (21:24)	2 (232:50)	1 (19:34)	2 (59:07)	1 (31:54)	5 (244:19)	1 (72:44)	1 (92:06)	2 (167:39)	2 (111:37)
2	Радослав Димитров	10	1484	2 (2:33)	3 (12:11)	16 (129:45)	2 (17:24)	2 (41:58)	3 (52:25)	13 (0:00)	1 (169:27)	1 (182:35)	1 (228:53)	3 (166:49)
3	Виктор Терзиев	9	1960	1 (15:32)	3 (28:42)	20 (294:46)	1 (37:45)	12 (109:37)	14 (0:00)	-	1 (126:29)	6 (206:00)	1 (258:35)	1 (141:48)
4	Даниел Атанасов	8	736	2 (10:27)	2 (22:40)	2 (235:37)	1 (36:18)	1 (79:58)	1 (45:31)	-	1 (89:08)	-	-	3 (116:04)
5	Иво Дилов	8	1209	1 (5:13)	3 (72:39)	4 (274:06)	3 (67:51)	3 (130:27)	2 (86:15)	-	1 (138:09)	-	-	4 (174:06)
6	Петър Няголов	7	582	1 (5:16)	1 (32:08)	6 (0:00)	1 (10:42)	1 (58:10)	2 (33:46)	-	1 (211:36)	-	-	3 (170:07)
7	Момчил Пейчев	7	655	1 (28:56)	1 (21:16)	-	1 (61:28)	2 (98:45)	1 (46:46)	-	1 (207:52)	-	-	1 (169:57)
8	Антон Чернев	7	822	1 (59:46)	2 (22:08)	7 (0:00)	2 (87:17)	1 (146:20)	2 (101:44)	-	1 (156:03)	-	-	1 (188:33)
9	Иван Ганев	7	1123	1 (13:26)	2 (28:48)	-	1 (38:40)	9 (186:02)	4 (62:39)	-	1 (226:05)	-	2 (0:00)	4 (267:13)
10	Веселин Георгиев	7	1333	1 (3:54)	1 (17:58)	2 (267:01)	5 (182:10)	2 (223:33)	1 (234:57)	-	-	-	-	1 (283:13)
11	Петър Ангелов	6	523	1 (50:27)	1 (18:43)	-	2 (40:51)	2 (111:52)	2 (72:15)	-	1 (168:48)	-	-	11 (0:00)
12	Антъни Господинов	6	830	1 (27:57)	4 (53:15)	-	1 (61:36)	9 (129:27)	3 (145:09)	-	1 (151:40)	-	-	15 (0:00)
13	Александър Станев	6	860	1 (44:30)	2 (31:30)	-	1 (51:42)	6 (224:09)	8 (137:24)	-	1 (110:23)	-	-	1 (0:00)
14	Валентин Латунов	5	716	1 (16:21)	1 (37:29)	7 (0:00)	2 (162:32)	1 (248:21)	3 (190:44)	-	-	-	-	-
15	Александър Георгиев	5	1332	13 (175:34)	5 (170:22)	52 (0:00)	2 (59:05)	1 (0:00)	11 (206:28)	-	1 (179:36)	-	-	-
16	Виктор Кожухаров	4	216	1 (10:29)	3 (30:54)	-	2 (40:47)	10 (0:00)	2 (53:48)	-	-	-	-	-
17	Михаил Михайлов	4	327	1 (72:53)	4 (70:23)	-	1 (42:20)	-	6 (0:00)	-	1 (80:59)	-	-	22 (0:00)
18	Александър Радославов	4	395	3 (44:56)	3 (0:00)	1 (0:00)	1 (83:43)	-	1 (108:30)	-	1 (117:02)	-	-	5 (0:00)
19	Георги Каров	4	511	1 (12:17)	4 (160:06)	-	3 (42:38)	1 (0:00)	2 (0:00)	-	1 (195:40)	-	-	-
20	Даниел Урумов	4	663	8 (0:00)	3 (41:17)	-	-	9 (0:00)	1 (75:18)	-	1 (155:58)	-	-	7 (229:57)
21	Александър Иванов	3	271	2 (44:24)	3 (61:02)	5 (0:00)	1 (105:26)	-	19 (0:00)	-	-	-	-	-
22	Марин Шаламанов	3	401	2 (75:50)	1 (90:31)	-	-	-	5 (133:47)	-	-	-	-	-
23	Стаси Тодорова	3	409	3 (64:32)	2 (105:10)	-	3 (139:07)	5 (0:00)	5 (0:00)	-	-	-	-	-
24	Деян Хаджи-Манич	3	560	3 (64:22)	8 (152:40)	-	2 (0:00)	-	2 (142:41)	-	-	-	-	-
25	Велислав Гърков	3	563	2 (121:44)	6 (140:29)	-	-	-	2 (160:34)	-	-	-	-	-
26	Никола Максимов	3	595	3 (72:53)	4 (289:50)	-	1 (131:28)	1 (0:00)	4 (0:00)	-	-	-	-	-
27	Димитър Сейков	3	839	2 (175:15)	3 (254:57)	-	3 (0:00)	-	-	-	5 (268:04)	-	-	-
28	Радостин Хандъров	2	163	1 (35:04)	4 (0:00)	-	1 (127:32)	-	3 (0:00)	-	-	-	-	-
29	Васил Жухов	2	169	2 (36:48)	5 (0:00)	-	1 (111:39)	1 (0:00)	8 (0:00)	-	-	-	-	-
30	borisd_2000	2	311	1 (112:51)	6 (0:00)	4 (0:00)	2 (177:16)	-	-	-	-	-	-	-
31	Огнян Цветков	2	386	-	2 (150:35)	-	-	-	1 (0:00)	-	1 (215:02)	-	-	-
32	Криси Стоянова	2	448	4 (105:21)	-	-	-	-	6 (181:57)	-	-	-	-	-
33	Александра Игнатова	2	557	1 (180:38)	-	-	-	-	11 (175:43)	-	-	-	-	-
34	Кръстан Драганов	1	163	4 (102:18)	1 (0:00)	-	1 (0:00)	-	-	-	-	-	-	-
35	Теодор Тотев	1	170	-	2 (149:23)	-	-	-	2 (0:00)	-	-	-	-	-
36	Камен Вакъвчиев	1	221	8 (80:24)	1 (0:00)	-	2 (0:00)	-	1 (0:00)	-	-	-	-	-
37	Георги Илиев	1	261	2 (0:00)	-	-	1 (0:00)	-	5 (180:30)	-	2 (0:00)	-	-	2 (0:00)
38	Христо Иванов	0	0	3 (0:00)	-	-	-	-	2 (0:00)	-	-	-	-	-
38	Емилиана Димитрова	0	0	-	-	-	-	-	3 (0:00)	-	-	-	-	-
38	Явор Василев	0	0	-	-	-	1 (0:00)	-	-	-	-	-	-	-
38	Юлиян Славчев	0	0	-	2 (0:00)	-	-	-	5 (0:00)	-	-	1 (0:00)	-	-
38	Мартин Маринов	0	0	-	2 (0:00)	-	-	-	-	-	-	-	-	-
38	Даниел Трополинов	0	0	-	5 (0:00)	-	1 (0:00)	-	-	-	-	-	-	-

Задачи

Тази година авторският екип се състоеше от Ивайло Странджев (задачи D, E, F, и K), Владислав Харалампиев (задача G) и аз, Александър Георгиев (задачи A, B, C, H, I, J). Този път подготвихме 11 задачи (вместо стандартните 10, колкото имаше предните няколко години), тъй като ни притесняваше, че няма да има много сложни задачи и искахме състезанието да е интересно до края дори за най-добрите. В крайна сметка две от задачите (задача G. Coloring и J. ChessTournament) си бяха сложни, така че се очертаваше наистина сериозна тема. Енчо все пак разби надеждите ни за "интересно до края" състезание, като успя да приключи с всички задачи 55 минути преди края му. Разбира се, наличието на интернет, и това, че участниците в онлайн изданието правят състезанието на собствени компютри значително помагат, така че дадените 11 задачи бяха почти непосилни за състезателите от присъственото състезание.

Откъм сложност, този път задачите бяха оценени като:

• Trivial (1 задача): A. ABBA
• Easy (3 задачи): B. DEADBEEF, F. Pancakes, и H. Tres
• Easy/Medium (1 задача): K. Chord
• Medium (3 задачи): C. Price Change, D.Community, и E. Banica
• Medium/Hard (1 задача): I. Server
• Hard (1 задача): J. Chess Tournament
• Hard/Very Hard (1 задача): G. Coloring

Този път нямаше наистина "Very Hard" задача, което беше и причината да имаме 11 задачи, вместо 10. "Bell curve" разпределението по сложност, което обикновено целим, не ни се получи особено, но крайното класиране беше доста задоволително: първите четирима участника са с различен брой задачи; разликата по време между четвъртия и петия е много голяма; а разликата между петия и шестия е отново една задача.

И тази година в задачите имаше известно количество закачки, като Trololo задачата този път беше H. Tres (ако последният стринг е "Elly" трябваше да се изпечата "Kriss", и обратно).

Чудихме се дали G. Coloring или J. Chess Tournament ще се окаже най-трудна, като все пак очаквахме Coloring да е малко по-тежка. Така и стана, като имаше само един човек, който успя да я реши. Chess Tournament, която по мое мнение беше осезаемо по-трудна от I. Server, в крайна сметка имаше същия брой решения (3), което беше една от изненадите за мен.

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

Решения

A. ABBA

Това беше единствената задача в темата, която бяхме оценили като "Trivial". Дори на нея, обаче, имаше грешни събмити, което донякъде ме изненада. Все пак, почти всички състезатели успяха да се справят с нея, като беше решена от 33 човека (от общо 37 с поне една решена).

В случая, ограниченията бяха достатъчно малки за да пробваме всяка възможност от A^B, такива, че A + B = S. Разбира се, тъй като резултатът можеше да бъде по-голям от размерите на 64-битово число, трябваше или да ползваме дълги числа (вградени в Python и Java), или да съобразим, че double също би свършил работа, тъй като не ни трябва абсолютна точност, а само да сравним възможните степени. Трети вариант беше да ползваме логаритми, с което също можем да държим числата малки, но това решение също би могло да страда откъм точност, тъй като би било с double-и. И не, в случая решението с логаритми е легитимно.

Примерно решение би било:

B. DEADBEEF

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

За да я решим е нужно единствено да имплементираме функция, която конвертира дума в "число" по дадените правила, като проверява дали то е валидно такова. Важното тук е да внимаваме за частните случаи, които включваха:

• Да имаме само суфикс (примерно "0xLL"), което е невалидно
• Да имаме повече от един суфикс (примерно "0x5LUL"), което е невалидно
• Да имаме суфикс, който не е на края на числото (примерно "0x2CELL05"), което е невалидно
• Имаше и грешката да пробваме всеки суфикс в стринга, но стрингът да е твърде къс (например "ULL" в "A") в който случай бихме получили Runtime Error

Самата имплементация може да стане относително елегантно:

C. Price Change

Тази задача беше оценена като Medium, но реално се оказа значително по-сложна, отколкото очаквахме (беше решена от 6 човека, докато другите две, които определихме като "Medium" бяха със, съответно, 25 и 14 решения).

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

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

Минималният отговор е казано, че ще бъде 10 / 100 = 0.1, докато максималният 10000 * 100 = 1000000. За да избегнем проблеми със закръглянето на double можем да "умножим" всички цени по 100, получавайки цели числа. Наистина, 184.01 можем да представим като 18401, но в последствие да изпечатаме като floating point число с 2 знака (printf("%d.%02d", price / 100, price % 100);).
Нещо повече, по всяко време, когато прибавяме или изваждаме процент от цената също можем да извършваме операциите само с цели числа (гледайки дали резултата по модул 100 е ≥ 50 или < 50). Малко по-сложен е моментът, в който трябва да направим средно аритметично на цените. Тогава имам деление на N (броя дни, в които се е продавал билета), но това не променя твърде много нещата - този път трябва да проверим дали числото по модул N е под или над N/2. Като цяло, следната функция би ни свършила работа за деление на произволно число: Остатъкът от решението (след прочитането на входа) би могъл да изглежда по следния начин:
Така двоичното търсене ще е в интервала [10, 100000000], което ще изисква около 27 итерации (колкото що-годе е двоичният логаритъм от 100,000,000). Тъй като на всяка итерация трябва да се симулират цените през всеки от дните (O(N)), получаваме сумарна сложност на задачата O(N∙log(S∙10000)), което си остава O(N∙logS). С тези ограничения тази сложност е повече от достатъчна.

D. Community

Първата задача на Иво беше решена от повече хора, отколкото очаквахме (цели 25 човека!). Макар и стандартен алгоритъм, не е алгоритъм, който се изучава в университета. Явно хората лесно успяха да го намерят в интернет и или да копират решения, или да имплементират логиката, описана в различни статии.

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

E. Banica

Тази задача очаквахме да е по-лесна от предната, но броят хора, които успяха да я решат (14) показва, че изобщо не е така.

Първата част от задачата е просто парсване на входа и превръщане в числови комбинации. След това работим просто с комбинации от числата 1 ... N.
Макар и задачата да е зададена с вероятности, всъщност ограниченията са такива че може да се изчисли точно колко комбинации от късмети се намират между късметите на Рашко и на Мими. Действително, общо комбинациите с 60 числа са 2⁶⁰, което се събира в 64 битово цяло число (long long в C++ или long в Java).

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

Интересната част от решението е да се напише функция code(combination, N), която взима комбинация от числа в интервала от 0 до N - 1 и връща код (номер в лексикографската наредба) за тази комбинация. В псевдокод тази функция изглежда така: Използвайки тази функция задачата става тривиална - трябва да кодираме комбинациите на Рашко и на Мими и да изчислим колко числа се намират между двете. Нека означим с C_R кода на комбинацията на Рашко и с C_M кода на комбинацията на Мими. Тогава броят числа между тях е C_M - C_R - 1 и съответно отговорът на задачата е: (C_M - C_R - 1) / 2^N. Не трябва да забравяме да разгледаме частния случай, когато комбинацията на Мими е преди комбинацията на Рашко и съответно разликата става отрицателна - в този случай, очевидно, отговорът е 0.

F. Pancakes

Макар и тази задача да беше определена от нас като "Easy", тя все пак беше по-малко решавана от Community (23 срещу 25 решения). Хора, задачата беше сортиране! Колко да е сложно? Очевидно повече, отколкото очаквахме, тъй като дори победителят в присъственото състезание не я реши до края на състезанието (след 14 неуспешни събмита). (facepalm).

В задачата се иска да сортираме тиганите по определен критерий. Първо трябва да съобразим, че обемът тесто в даден тиган зависи квадратно от неговия диаметър и съответно скоростта, с която ще използваме цялото тесто в даден тиган с диаметър d и време за готвене на една палачинка t е правопропорционална на (d * d) / t. И така, трябва да сортираме тиганите в намаляващ ред по тази скорост. Единственото нещо, за което трябва да се внимава е int overflow понеже d * d * t > MAX_INT.

G. Coloring

Най-сложната задача в темата както и миналата година беше на Влади Харалампиев. Все пак, тя беше решена от един от състезателите (Енчо Мишинев) и почти решена от друг (Радослав Димитров).

Как точно трябваше да я решим? Откриване на оптимално оцветяване в общи графи е NP-трудна задача. Ясно е, че в нашия случай наивно изчерпване няма да мине по време, за това трябва да използваме структурата на графа.

Класът графи, описан в условието, се нарича хордални графи. Основно свойство на хордалните графи е, че те имат perfect elimination order (P.E.O.). Т.е. можем да подредим върховете им в ред v₁, v₂, ... v_n така, че за всеки връх v_i Pred(v_i) образуват клика (Pred(v_i) са върховете, свързани с v_i и намиращи се преди v_i в редицата). Забележете, че дефиницията в Wikipedia е малко по-различна (там съседите, с които даден връх образува клика, са след него в P.E.O).

Да видим как можем да откриваме P.E.O. С индукция може да се покаже, че всеки хордален граф има връх, всички съседи на който образуват клика (тези върхове се наричат simplical vertices; твърдението на индукцията е – всеки граф има simplical vertex; ако графът не е пълен, то има два simplical vertices, които не са съседни). Един начин да открием P.E.O. е да откриваме един по един simplical vertices на графа (simplical vertex безопасно може да се сложи в края на P.E.O.). Това също вероятно е прекалено бавно за ограниченията на задачата.

P.E.O. може да се открива в линейно време с модификация на BFS. Една от тях се нарича lexBFS (lexicographic BFS), по-лесно се доказва, но по-трудно се реализира. Друга се нарича MCS (maximum cardinality search). При тази модификация започваме от произволен връх и на всяка итерация разглеждаме върха с най-много съседи сред вече разгледаните върхове. Редът, в който са разгледани върховете, е P.E.O.

Да приложим greedy оцветяване, като разглеждаме върховете в ред на P.E.O. Под greedy оцветяване разбираме това, че за всеки връх използваме минималния възможен номер на цвят (който още не е бил използван сред съседите на върха). Нака v_i е върха, за който |Pred(v_i)| е максимално. Тогава greedy - алгоритъмът ще използва точно |Pred(v_i)| + 1 цвята. Забележете, че v_i U Pred(v_i) образуват клика, от което с по-малко цвята графът не може да се оцвети. Значи greedy-алгоритъмът връща оптимално оцветяване.

H. Tres

Тазгодишната "трололо" задача в темата беше с буква H и 19 човека успяха да видят "измамата" преди края на състезанието. Основното тук беше да забележим, че независимо какви карти имат и как играят, те винаги се редуват. Ако в даден рунд бъдат дадени четен брой карти, то първият играч губи и започва отново в следващия. Ако пък е нечетен, то първият печели, съответно следващият рунд бива започнат от другия играч.

Нека разгледаме следната поредица от 5 рунда: [EKEKE], [KEKE], [K], [EKEKEK], [EK] - можете да забележите, че ако конкатенираме хората във всички рундове получаваме алтерниращи E-та и K-та, тоест независимо как играят момичетата в края ако Ели е започнала първа, то Крис ще спечели и обратно - ако Крис е започнала, то Ели ще спечели.

Съответно, решението беше да прочетете 53 стринга, и ако последният започва с 'E' да изпечатате "Kriss", иначе "Elly". Авторското решение пък ползва това, че картите са зададени на по един ред, тоест можем да прочетем три реда и да погледнем буквата, с която започва последният:

I. Server

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

Авторската имплементация ползва надграждане на Сегментни Дървета (за което по-късно ще има друга тема: Интервални Дървета).

В началото на задачата трябваше да "компресираме координатите", тъй като възможните времена бяха в голям диапазон (малко по-малко от 32 милиона възможности). Реално не ни интересуваше *точно* кога се е случил даден ъпдейт, а само къде попада спрямо останалите. Затова стандартна техника е да се прочете целия вход, да се сортират числата, и да се заменят с индексите им в сортирания масив (което се нарича "компресия на координатите").

След като имаме вече времена в интервала [0, 200000], вместо [0, 32000000], можем да обработим евентите един по един, като при всеки от тях първо ъпдейтваме интервалното дърво, а после правим куери в него. Цялата имплементация на интервалното дърво, нужно за тази задача, е следната: Тук викаме update() с idx = компресираното време и val - промяната в кредитите в конкретното съобщение. Числото, което трябва да изпечатаме след като обновим дървото с новата информация, е -min(0LL, query()).

Тъй като обновяването в интервално дърво е с логаритмична сложност (а в случая query-то, което по принцип също е логаритмично, сега даже е константно), цялата сложност на решението е O(N∙logN).

J. Chess Tournament

Най-трудната моя задача в темата беше J. Chess Tournament. Забавното е, че измислих задачата без да имам идея как точно да я реша. Да си призная, отне ми доста време за да измисля решение (идея + имплементация + дебъгване ми отне над 3 часа), така че трите успешни решения по време на състезанието са една идея повече, отколкото очаквах (очаквах едно, максимум две).

Ако забелязахте, до тук няма задача за Динамично Оптимиране (ако изключим алтернативното решение на E. Banica, което е голям overkill). И тъй като тема без динамично не може, тази задача беше именно такава!

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

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

Един и същ стейтНека разгледаме как можем да получим един и същ стейт (едина и съща редица от останали хора в турнира) няколко пъти. Ако имаме трима участници A, B, и C, които стоят един до друг (и Ели не е никой от тях), дали A ще бие B, после C, или пък C ще бие B и после A ще бие C, или пък B ще бие C, но после A ще бие C, за Ели няма значение - крайният резултат е, че по някое време тя потенциално може да се наложи да се бие с A и няма шанс да се бие с B и C. Така само с 4 човека успяхме да стигнем по три различни начина до един и същи стейт. По също толкова начина можем да стигнем до стейт, в който B е оцелял, а както и за C. Когато участниците стават повече, този брой нараства експоненциално.

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

Битови маскиВ задачи, където елементите могат или да са или "ползвани" (в случая - отпаднали) или не (все още в турнира) често ползваме битова маска. В случая, обаче, броят елементи (50) е твърде голям за това.

Можем да направим наблюдението (а то е и намекнато в обяснението на първия пример), че Ели "разделя" участниците на две: тези отляво на нея няма как да се бият с тези отдясно на нея. За да стане това, Ели трябва да отпадне.

Така с динамично с битова маска можем да решим значително по-големи инстанции, стига Ели да е що-годе посредата. Например, при 42-ма участници и Ели на 19-та позиция, ще имаме нужда от маска с 18 бита за под-задачата наляво и с 23 бита за тази надясно). Въпреки това, обаче, може Ели да не е посредата (примерно пак 42-ма участници, но Ели е 13-та - така ще са нужни цели 29 бита за под-задачата надясно, което вече е твърде много). Така това решение отпада (но пък ми свърши чудесна работа за да тествам "умното" си, йей!). Добре, какво тогава?

Независими интервалиЩе направим друго динамично, в стейта на което пазим "интервал", за който сме си гарантирали, че няма да бъде повлиян нито отляво, нито отдясно. Тоест, за сега стейтът ни е двумерен: [L][R].

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

Един лесен пример как бихме започнали следва точно от наблюдението, което направихме по-рано. Можем да сметнем вероятността Ели да спечели за интервала [1, N] (и момичето е на позиция K) като намерим вероятността за [1, K] и да я умножим по вероятността за интервала [K, N]. Тъй като Ели "разделя" цялата редица на две, то тези две под-задачи са независими (от гледна точка на нея, която държи да не загуби нито един мач).

В самото динамично ще ни се налага да смятаме не само какъв е шансът Ели да спечели в даден интервал, ами и произволни други хора. Това не променя нищо - всеки човек е просто някакъв индекс в масива, така че ще включим и него като трето измерение: [L][R][who].

Победител в някой от краищатаТук можем да направим второ наблюдение - можем да пускаме рекурсията по такъв начин, че човекът, който искаме да спечели дадения под-интервал, винаги да е в един от неговите два края (тъй като той разделя интервала). Така можем да смалим третото измерение, като ще пазим само информация в кой от двата края (левия или десния) на дадения интервал се намира той. Така постигаме стейт с размер [50][50][2] вместо досегашните [50][50][50].

Разцепване на под-интервалиНека сме в даден интервал [L, R] и знаем, че (за простота) човекът в левия край на интервала трябва да спечели. Ще наричаме човека, който искаме да спечели, "нашия човек". Какъв е шансът за това?

Ако интервалът съдържа само един елемент, то шансът е 1. Нашият човек няма срещу кого да играе, съответно печели.

В случай, че в интервала има поне още един човек, то "нашият човек" ще трябва да спечели поне една партия.

Ще фиксираме къде ще се случи последната партия в интервала. Нека това е позиция L ≤ M < R (ще пробваме всички възможности, като всяка от тях е равно-вероятна). Забележете, че тъй като фиксираме индекса на последната партия (в текущия интервал [L, R]), то след нея в интервала ще остане само "нашия човек". В противен случай той би имал поне още една партия, тоест избраната позиция не би била последна.

Фиксирайки последната партия, ние разделяме текущия интервал на два независими под-интервала. Тъй като всички партии наляво от M и всички партии надясно от M+1 ще се изиграят преди нея, то двата под-интервала няма как да си влияят един на друг и можем да изчислим рекурсивно.

В под-интервала, в който попада "нашият човек" знаем кой искаме да победи и можем директно да изчислим. В другия интервал не знаем, затова ще пробваме всеки един от хората там. Фиксирайки срещу кой опонент ще бъде последната партия, ние можем да сметнем неговия шанс за победа в неговия под-интервал ([M+1, R]), след което да сметнем нашия шанс да спечелим в нашия под-интервал ([L, M]) и накрая да умножим тези две вероятности.

Нека фиксираната позиция за последната среща е L ≤ M < R и индексът на победителя, който сме фиксирали, е M+1 ≤ X ≤ R. Така, шансът за печалба на "нашия човек" се формира от:

• 1 / (R - L) // Шансът последната партия да е между позиции M и M+1
• recurse(L, M, 0) // Шансът "нашия човек" да спечели в под-интервала до последния мач (нулата указва, че се намира в левия край на [L, M])
• recurse(M + 1, X, 1) // Шансът избрания опонент да спечели в под-интервала наляво от себе си до последния мач (единицата указва, че се намира в десния край на [M+1, X])
• recurse(X, R, 0) // Шансът избраният опонент да спечели в под-интервала надясно от себе си до последния мач (нулата указва, че се намира в левия край на [X, R])
• a[L] / (a[L] + a[X]) // Шансът "нашият човек" да спечели срещу фиксирания опонент

КодНека видим как би изглеждало това като код:
СложностГорното динамично има размер O(N2) (което е и сложността по памет). За всеки от тези стейтове правим два вложени цикъла (един да изберем мястото на последния мач, и един да изберем опонента) - тоест O(N2). Така сумарно можем да сметнем, че решението е със сложност по време O(N4). Реално то е с много малка константа, тъй като няма как L > R, както и когато интервалът става по-малък (тоест L става по-близко до R) циклите вътре не правят по N итерации. С малко мислене можем да видим, че константата тук е около 1/16, тоест даденото решение ще работи и за по-големи N от дадените на турнира. Реално, N може да бъде някъде до около 200, вместо дадените 50 - така ще прави (по груба сметка) около 200⁴ / 16 ≈ 100,000,000 операции, което спокойно ще влезе в една секунда.

Нещо повече, можем да разделим самото динамично на две (за да избегнем двата вложени цикъла вътре). Така бихме могли да постигнем дори O(N3) сложност.

На самия турнир не се искаше толкова ефективно решение, като и тримата решили я състезатели ползваха O(N5) решения (колкото беше и моето оригинално такова). На системата към informatika.bg съм качил версия на задачата с по-големи ограничения, ако искате да тествате с тях.

K. Chord

Една от лесните задачки (определена от нас като "Easy/Medium") се спотайваше в края на темата. Може би заради това, че беше последна, може би пък защото беше отделена на втора страница в списъка със задачи, реално не беше особено "популярна" сред състезателите (като за сложността си) - едва 11 човека я направиха.

Нека разгледаме как можем да я решим. Понеже изрично е казано че КОЙко се намира извън София, в тази задача няма прекалено много частни случаи. Най-лесно е да интерпретираме задачата като квадратно уравнение. Първо трябва да изчислим единичен вектор в посоката, в която сочи КОЙко. Това става като образуваме вектора с координати (x_посока - x_КОЙко, y_посока- y_КОЙко) и го разделим на неговата дължина. Нека означим координатите на така получения вектор с (vx, vy).
Координатите на всички точки на лъча зададен от КОЙко се задават с формулите x := x_КОЙко + t * vx, y := y_КОЙко + t * vy където t ≥ 0. Съответно пресечните точки на правата, върху която лежи този лъч, със София са решенията на уравнението:
(x_КОЙко + t * vx)² + (y_КОЙко + t * vy)² = 20²
Тук трябва да разкрием скобите и да групираме по степените на t за да получим квадратно уравнение от типа A * t² + 2 * B * t + C = 0. При правилни сметки тук би трябвало да се получи:

A := vx² + vy² = 1 (понеже (vx, vy) е единичен вектор)
B := x_КОЙко * vx + y_КОЙко * vy
C := x_КОЙко * x_КОЙко + y_КОЙко * y_КОЙко - 20 * 20

Формулата за дискриминантата на това уравнение е D := B * B - A * C (обърнете внимание че използвам опростената формула заради множителя 2 пред B във формулата).

Ако дискриминантата е отрицателна или 0 можем директно да изведем отговор 0 - лъчът зададен от КОЙко не пресича София или я допира в единствена точка.

В противен случай получаваме двете решение за t:
t₀ = -B - sqrt(D), t₁ = -B + sqrt(D)
Тук трябва да разгледаме още един случай - ако правата пресича София, но не и лъчът. Това се случва ако решенията за t са отрицателни. Обърнете внимание че понеже КОЙко е извън София или и двете решения ще са отрицателни или и двете ще са положителни. И така - проверяваме за коя да е от двете стойности на t, дали е отрицателна. Ако е - извеждаме 0, в противен случай отговорът на задачата е: -B + sqrt(D) - (-B - sqrt(D)) = 2 * sqrt(D)

Алтернативно, задачата можеше да бъде решена и с троично търсене за да намерим най-близката до (0, 0) точка (X, Y) по лъча. Ако тя е на разстояние по-голямо или равно на 20 (радиуса на София), то отговорът е нула. Ако е по-малко, то ще имаме ненулева дължина на хордата. Можем да разгледаме два правоъгълни триъгълника с обща страна (0, 0), (X, Y) и трети точки - пресечните с кръга. Тъй като знаем по две страни на триъгълниците (радиуса и разстоянието от най-близката точка по лъча до (0, 0)), третата се намира тривиално (и е с дължина половината от отговора).

Това решение е по-дълго за имплементация (15 реда, след четенето на входа), но се справя по-лесно с частните случаи (тъй като не ни интересува дали лъчът е насочен към кръга или не, както и дали двете дадени точки и (0, 0) лежат на една права). Решението нямаше да има и проблем ако и двете дадени точки лежат в кръга.