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

Dean's Cup, 2016

За първа година от 2008-ма насам, в подготовката на задачите се включиха четирима човека, включително четирикратният носител на купата - Влади Харалампиев. Този път бяха подготвени за състезанието 10 задачи, от които едва две бяха оценени от нас като "Hard". Все пак, това се оказа достатъчно, тъй като до края на състезанието нямаше никой, който да е решил всички (въпреки че победителят Радослав Димитров беше близо). За наша изненада доста хора изгубиха много време на задачи, оценени като "Easy" от нас, включително и на една "Trivial".

Победители

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

Победител в присъственото състезание (и носител на Купата на Декана за 2016-та година) стана Даниел Атанасов, студент първи курс (и национал на България от IOI). С една задача по-малко (но все пак люта борба за първото място до след 4-тия час) на второ място се класира Иво Дилов, също първокурсник от КН. С още една задача по-малко на трето място се класира Георги Шопов, четвъртокурсник от КН. Петицата оформиха Антон Чернев (първи курс, КН), и Марк Андонов (трети курс, КН). Тази година специалността Компютърни Науки напълно доминираше, като и петимата наградени бяха от нея.

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

Победител в задочното (онлайн) състезание, а също така и първенец в смесеното класиране, стана Радослав Димитров - ученик в 10-ти клас от ОМГ "Акад. Кирил Попов", гр. Пловдив. Той беше първият състезател, успешно предал задача I. Palindromes (задачата на Влади Харалампиев), както и единственият състезател с 9 задачи. Второ място зае Петър Няголов, ученик в 10-ти клас от МГ "Баба Тонка", гр. Русе. Той беше единственият друг участник, който успя да се справи със задача I, като ползва различно решение (сходно на моето, което ще опиша тук). Тройката заформи победителят от миналогодишното издание - Иван Ганев (ученик в 11-ти клас от ПМГ "Нанчо Попович", гр. Шумен).

Награди

Наградите тази година включваха:

• Осигурени от ФМИ:
• Лаптоп
• Фотоапарат
• Два принтера
• Осигурени от Александър Георгиев и Ралица Димитрова:
• Шумозаглушаващи слушалки Bose QuietComfort 25
• Дрон Parrot Mambo
• Бордигра Ticket to Ride - Europe
• От авторите на задачите:
• Клавиатура Razer BlackWidow Ultimate Stealth

Класиране

Rank	Name	Solved	Time	A	B	C	D	E	F	G	H	I	J
1	Радослав Димитров	9	902	2 (17:07)	1 (84:40)	2 (37:15)	1 (148:08)	1 (164:02)	28 (0:00)	1 (202:48)	1 (58:22)	1 (69:57)	4 (119:03)
2	Даниел Атанасов	8	859	3 (17:08)	1 (79:12)	3 (42:11)	1 (248:14)	1 (106:35)	-	8 (257:06)	1 (57:46)	-	1 (49:59)
3	Петър Няголов	8	897	1 (13:32)	1 (47:27)	3 (95:10)	2 (0:00)	3 (163:59)	7 (0:00)	1 (289:26)	1 (32:18)	3 (228:56)	1 (26:03)
4	Иван Ганев	8	1003	1 (23:50)	1 (107:22)	2 (90:52)	20 (230:12)	2 (147:31)	-	1 (276:42)	2 (65:42)	1 (0:00)	4 (59:59)
5	Иво Дилов	7	700	2 (26:40)	1 (109:12)	1 (90:05)	1 (209:36)	2 (178:26)	-	1 (0:00)	1 (49:33)	-	1 (36:02)
6	Емил Инджев	6	682	1 (22:41)	1 (44:17)	-	1 (171:07)	2 (0:00)	-	1 (238:31)	1 (57:51)	-	4 (146:45)
7	Георги Шопов	6	956	1 (245:34)	1 (119:29)	2 (291:24)	3 (183:18)	-	-	-	1 (49:07)	-	1 (66:30)
8	Антон Чернев	6	1064	1 (97:26)	1 (145:14)	2 (241:11)	-	1 (291:56)	-	-	1 (115:28)	-	2 (171:50)
9	Валентин Борисов	5	251	1 (19:16)	2 (94:16)	1 (61:03)	-	1 (0:00)	-	-	1 (47:50)	-	1 (27:52)
10	Гико Копев	5	582	-	1 (125:35)	7 (207:48)	1 (107:21)	13 (0:00)	-	-	2 (90:19)	-	5 (50:01)
11	Марк Андонов	5	614	2 (153:47)	1 (140:17)	2 (195:44)	-	9 (0:00)	-	-	1 (71:30)	-	3 (52:20)
12	Георги Каров	5	881	4 (60:09)	1 (199:22)	-	-	3 (297:57)	-	-	4 (112:52)	-	2 (210:04)
13	Джон Димитров	4	333	1 (97:28)	1 (49:38)	-	-	-	-	-	1 (63:31)	-	2 (121:26)
14	Виктор Радивчев	4	463	3 (75:12)	1 (106:10)	2 (0:00)	-	1 (0:00)	1 (0:00)	-	1 (92:19)	-	3 (188:22)
15	Марин Шаламанов	4	616	2 (140:03)	1 (196:05)	-	2 (171:24)	-	-	-	3 (107:50)	-	1 (0:00)
16	Божин Кацарски	4	688	1 (156:34)	1 (200:33)	4 (0:00)	-	-	-	-	1 (101:41)	-	6 (228:22)
17	Станислав Иванов	4	728	-	1 (189:34)	-	1 (240:42)	-	-	-	1 (153:37)	-	3 (143:59)
18	Иво Карагьозов	3	258	-	1 (50:03)	-	-	3 (0:00)	-	-	3 (67:12)	-	5 (140:06)
19	Пламен Начев	3	371	-	1 (247:35)	-	-	6 (0:00)	-	-	2 (30:52)	-	2 (91:40)
20	Петър Ангелов	3	421	-	2 (145:17)	1 (0:00)	-	-	-	-	1 (82:56)	-	2 (192:40)
21	Ивайло Кирилов	3	532	1 (266:47)	-	-	1 (0:00)	2 (0:00)	-	-	2 (49:50)	-	4 (214:56)
22	Цвета Огнянова	3	561	-	4 (199:42)	-	-	-	-	-	1 (170:47)	-	2 (189:51)
23	Васил Георгиев	3	603	-	-	-	1 (82:32)	-	-	2 (236:32)	3 (283:27)	-	-
24	Стоян Ефтимов	3	620	3 (290:51)	-	-	-	-	-	-	4 (101:07)	-	3 (227:51)
25	Денис Михайлов	3	635	-	1 (293:39)	-	-	-	-	-	5 (218:31)	-	4 (121:47)
26	Стефан Шклифов	3	735	-	2 (169:26)	-	-	-	-	-	4 (299:19)	-	4 (265:27)
27	Божидар Василев	3	746	2 (227:14)	12 (0:00)	-	-	-	-	-	3 (247:22)	-	1 (270:34)
28	Явор Иванов	2	208	-	5 (0:00)	2 (0:00)	-	-	-	-	2 (79:51)	-	2 (127:53)
29	Димитър Добрев	2	286	-	-	-	-	-	-	-	1 (75:40)	-	4 (209:37)
30	Даниел Данаилов	2	294	-	-	-	-	-	-	-	1 (44:47)	-	10 (248:54)
31	Антон Петков	2	328	-	-	1 (0:00)	-	1 (0:00)	-	-	1 (94:58)	-	2 (232:52)
32	Камен Кънчев	2	349	-	-	-	-	-	-	-	2 (80:22)	-	7 (267:34)
33	Иван Камбуров	2	378	-	-	-	-	-	-	-	4 (293:04)	-	4 (84:38)
34	Георги Попов	2	424	1 (195:01)	1 (228:34)	1 (0:00)	-	-	-	-	-	-	-
35	Иван Вардаров	1	97	1 (96:29)	-	-	-	-	-	-	2 (0:00)	-	-
36	Николай Денев	1	120	2 (0:00)	-	-	-	-	-	-	1 (119:33)	-	-
37	Стефан Николов	1	139	-	-	-	-	-	-	-	1 (138:23)	-	1 (0:00)
38	Денислав Желязков	1	208	-	4 (0:00)	-	-	-	-	1 (207:21)	-	-	-
39	Владимир Ананиев	1	211	2 (0:00)	-	-	-	-	-	-	3 (210:18)	-	-
40	larodi v	1	217	-	-	-	-	-	-	-	1 (216:26)	-	-
41	Кристина Илиева	1	238	-	-	2 (0:00)	1 (0:00)	-	-	-	2 (237:09)	-	-
42	Даниел Урумов	1	255	-	5 (0:00)	-	-	2 (0:00)	-	-	1 (254:56)	-	4 (0:00)
43	Александър Митов	0	0	-	-	-	-	-	-	-	1 (0:00)	-	-
43	Александър Дойков	0	0	-	-	-	-	-	-	-	5 (0:00)	-	-
43	Борис Глузов	0	0	-	-	-	-	-	-	-	6 (0:00)	-	2 (0:00)
43	Влади Неколов	0	0	-	-	-	-	-	-	-	-	-	8 (0:00)

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

A. 8Bit

Задачата 8Bit трябваше да е третата най-лесна задача в темата, но много от състезателите не видяха, че просто next_permutation() на вектор с нули и 8 единици ще свърши работа. In hindsight, трябваше да я дам с ограничения до 1,000,000 или дори по-малко за да е по-очевидно, че това решение ще е достатъчно бързо. Амортизираната сложност на това решение е O(T∙N), тъй като следващата премутация е амортизирано O(1).

Повечето състезатели ползваха много бързо алтернативно решение, базирано на комбинаторика - ползвайки триъгълник на Паскал (или просто формулата за комбинации C(n, k) = n! / k! * (n - k)!) можем да сметнем по колко начина можем да разположим k единици в n позиции. След това решението е конструктивно и е със сложност O(T∙log(N)) (трябва да обходим битовете на всяко число).

Трети начин да се направи задачата е да се ползват побитови операции за да симулираме next_permutation() константно в двоично число, гарантирайки си O(1) (този път неамортизирано).

B. WordCoins

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

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

Наистина, нека се замислим. Нека разгледаме думите "KON", "BOB" и "QDE". Ако искаме да направим от "KON" -> "BOB" ще трябва да платим -21, докато да трансформираме "BOB" в "QDE" ще платим 7, за сумарно -14. Обаче, точно -14 е и разликата "KON" -> "QDE". И тъй като в условието ни е казано, че винаги ще има път от първата до последната дума, може изобщо да не разглеждаме ребрата и да строим граф и да търсим най-къс път, а просто да сметнем разликата между първата и последната дума.

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

C. Progression

Задачата Progression беше дадена от Влади Владимиров, и беше единственото динамично в темата (като даже имаше решение, което не е базирано на ДП).

Първото наблюдение, което трябва да направим, е че макар и числата да са до 100,000, спокойно можем да ги направим да са до 10,000 (по-точно до N). За дадени две числа реално ни интересува единствено кое от тях е по-голямо или дали са равни. Така можем да ги "компресираме" до някакви по-малки стойности.

След това можем да направим динамично със стейт [10000][10000] (от тип short за да влиза в ограниченията по памет), като стейт [pos][last] отговаря на въпроса "Ако съм в позиция pos и предходното число е било last колко е най-дългата редица от тук нататък?". Тъй като last и pos еднозначно определят следващото число, преходът е O(1), съответно цялото решение е със сложност O(N∙N).

Алтернативно, можем да фиксираме първите две числа от редицата (с два цикъла за O(N2)), след което да симулираме попълването й, винаги взимайки следващото най-близо срещане на тези две числа. На пръв поглед това става O(N3), но ако добавим проста проверка никога да не разглеждаме една и съща двойка числа повече от веднъж (просто един допълнителен boolean масив), можем да видим, че ще разгледаме всяко число по O(N) пъти (по веднъж с всяко друго). Така това решение е O(N2).

D. Women

Тази задача беше дадена от Ивайло Странджев и беше учебников пример за Вериги на Марков. В случая нямахме никакви усложнения, така че можеше просто да вдигнем дадената ни матрица на преходите на някаква висока степен и да изпечатаме резултатите. Сложността на това решение е O(N3∙log(K)), където K е броя итерации, които искаме да направим. Тъй като имаме логаритъм от K можеше спокойно да ползваме някоя огромна стойност (примерно 1,000,000,000), като така си гарантираме, че матрицата ще converge-не и точността ще е достатъчно добра.

Решението на Иво Дилов е доста готино, тъй като си спестява писането на бързо вдигане на степен, използвайки факта, че произволна висока степен би свършила работа. Така той вдига 20 пъти матрицата на квадрат (всеки път ползвайки предходната) - което е еквивалентно на това да направи 1048576 итерации (да вдигне първоначалната матрица на степен 2²⁰).

Реално, повечето от състезателите не писаха това, ами правиха някакъв вид динамично със стейт [node][steps], където node е състоянието, което искат да изчислят, а steps е текущата минута. Симулирайки това до няколко хиляди стъпки дава достатъчно точни резултати, за да мине изискването от 10^-6.

E. Motherboard

Задачата Motherboard имаше два основни подхода, по които можеше да бъде решена - единият с двоично търсене, а другият - с троично такова.

Както повечето задачи, които се решават с двоично търсене, то обикновено се прави по отговора. Ако фиксираме максималното разстояние между два процесора, то за всяка двойка можем да определим някакъв интервал [Y1, Y2], в който може да попада шината, така че да удовлетвори тези два процесора. Ако накрая сечението на всички N^2 процесори е ненулево, то избраното максимално разстояние е окей (и продължаваме двоичното търсене надолу); в противен случай продължаваме с по-големи стойности. Това решение е със сложност O(N2∙log(Y)).

Алтернативно, можем да търсим перфектната позиция на шината ползвайки троично търсене. Фиксирайки позицията, можем да сметнем за O(N2) колко е максималното разстояние между двойките процесори. Състеателите, пробвали това решение, трябваше да са малко несигурни дали то ще работи, тъй като функцията не е точно каквато ни трябва (първо монотонно намаляваща, после монотонно нарастваща) - има и "плоски" части. За щастие, потенциалният плосък участък може да се получи единствено при минимума на функцията, което няма как да "излъже" троичното търсене. Така това решение също би работило за O(N2∙log(Y)).

F. PrimePals

Задачата PrimePals беше единствената нерешена задача по време на състезанието - което беше изненада за мен, тъй като по мое мнение Palindromes беше по-трудна.

Първото важно наблюдение, което ни трябва тук, е че нямаме прост палиндром с четна дължина, различен от 11. Защо? Един от начините да проверим дали число се дели на 11 е да сумираме цифрите на четните позиции на числото, от тях да извадим сумата на цифрите на нечетни позиции и да проверим дали разликата се дели на 11. Добре де, обаче ако имаме палиндром с четен брой цифри, тази разлика ще е винаги 0, тоест винаги ще се дели на 11. Така единственият прост палиндром с четен брой цифри е самото число 11.

Така елиминираме случаите, когато D е четно (все пак трябва да се справим с частния случай за 11) - тогава отговорът е винаги -1. Така си намаляме леко ограниченията, като вече D ≤ 9. Това ни помага да ползваме най-лесната проверка за прости числа (пробвайки всички числа, по-малки или равни на корен квадратен от числото), а и ни позволява да ползваме int-ове за сметките, които са малко по-бързи.

Самото решение звучи тъпо: просто ще пробваме всички ключове и ще видим дали има такъв, който да ни върши работа.

Ама ама... нали ключът може да е до 999,999,999? Това не е ли твърде много?

Ами да, само че огромна част от тези ключове са невалидни, тъй като правят някое от числата непалиндром. Нещо повече, правят първото число непалиндром.

Има ли по-умен начин, по който да генерираме ключовете, така че първото число да е винаги палиндром? Ами да - ще генерираме само първите D/2 цифри, а останалите ще изчислим по първото число от списъка на Ели, така че то да бъде палиндром. Реално то еднозначно определя останалите D/2 цифри на ключа.

След като генерираме ключ, трябва да проверим:

1. Дали всяко от останалите числа в списъка е палиндром;
2. Дали всички числа в списъка са прости.

Проверката за палиндромичност става за O(N∙D), а за простота - O(N∙sqrt(M)), където M е максималното число. Както казахме, то е 999,999,999, тоест sqrt(999999999) ≈ 32000. Ъмм, 30 * 100000 * 100 * 32000 изглежда мнооого голям брой операции (30 е броят тестове, 100000 е броят на всички ключове, 100 е броят числа в списъка, 32000 е броят операции за проверка за простота). Обаче няма как да направим тест, в който да ги достигнем, тъй като трябва за всеки ключ да проверката за просто число за всяко число да отнема 32000 операции, което не става. Най-малкото всеки втори ключ дава четно число, което терминира проверката съвсем в началото. Оказва се, че, макар и за някои ключове проверката да е относително бавна, за мнозинството е адски бърза, като това решение върви достатъчно бързо (0.2 секунди, при TL 3 секунди).

Фън факт, първоначално исках задачата да е с по-големи ограничения, за да трябва да се ползва бърза проверка за прости числа (примерно Рабин-Мюлер). Добре, че се отказах :)

G. SkyScammer

Във втората задачка на Иво Странджев той нещо се гаври с фирмата ми (Skyscanner) и ника ми (espr1t). Гад.

Като цяло задачата си задава чиста постановка за намиране на най-къс път, като сложното в задачата беше да се намерят разстоянията между върховете. За целта можеше да се ползва широк набор от формули, като може би най-простата e: където RADIUS е даденият радиус на земното кълбо - 6378.

След като имаме разстоянията, проста имплементация на алгоритъма на Дейкстра би свършил работа.

H. Lotto

Задачата Lotto беше най-лесната в темата, като изискваше просто изчерпване (за всяка позиция в матрицата проверяваме дали цифрите надолу или надясно съвпадат с дадените ни).

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

I. Palindromes

Задачата Palindromes беше дадена от четирикратния победител на ТКД - Влади Харалампиев. Според мен това беше най-трудната задача, но все пак двама от състезателите успяха да се справят с нея. Ето и анализа на Влади:

Основната идея е, че ако P е множеството от всички непразни поднизове-палиндроми, то броят елементи в P е O(|S|).

Това може да се покаже така - нека вече сме добавили всички палиндроми сред първите p - 1 символа и сега разглеждаме p-я символ. Нека най-дългия палиндром, свършващ в p-я символ, е s. Тогава само s потенциално може още да не се сме добавили в P, всички по-къси палиндроми вече са били добавени (например, ако имаме низ cccabaaba; при p = 8 най-дългият палиндром е на позиции 3 - 8; 6 - 8 е по-къс от него и тъй като е суфикс, то 3 - 8 ще има и префикс със същия низ; значи вече сме го добавили в P).

От горното следва, че може за O(|S|) проверки дали подниз е палиндром да намерим всички елементи в P. Тогава може просто да ги сортираме и при заявка да печатаме елемента на съответния индекс. За намирането на всички палиндроми просто вървим от ляво надясно. Дължината на най-дългия палиндром при преход може максимум да се увеличи с 2.

Трябва да се научим бързо да сравняваме поднизове (за равенство при търсенето на палиндроми и за < при сортирането). Това може да правим с хешове + двоично търсене (което ще даде сложност O(L log2(L)) за цялата задача) или със суфиксен масив (което ще даде O(L log(L))). Би трябвало да можем да решим задачата и въобще за линейно време, но ще бъде доста трудно за написване.

J. Matchsticks

Задачата Matchsticks беше втората задача, дадена от Влади Владимиров. Основното при нея беше да се види каква е стратегията, която ползва клечките оптимално, така че да се получат възможно най-много квадратчета. Доста от състезателите видях (разписвайки си първите няколко на листче), че това е да строим квадрат от малки квадратчета. В началото започваме с едно единствено квадратче (ползвайки 4 клечки). След това правим слой около него с 8 квадратчета (ползвайки 3 + 3 + 2 + 3 + 2 + 3 + 2 + 2 клечки). Следващият слой е с 16 квадратчета (ползвайки 3 + 2 + 2 + 3 + 2 + 2 + 2 + 3 + 2 + 2 + 2 + 3 + 2 + 2 + 2 + 2 клечки). Следващият слой е с 24 квадратчета и т.н. Забелязваме, че във всеки слой имаме 4 квадратчета, които ни отнемат по 3 клечки, а всички останали можем да направим за 2.

За да се справим с даденото относително голямо N, ще добавяме по цял слой, стига да ни трябват всички негови квадратчета. Тъй като броят квадратчета във всеки следващ слой нараства (с 8, но това няма значение), то ни трябват най-много O(sqrt(N)) слоя. В последния (непълен) слой трябва да добавим до O(sqrt(N)) квадратчета. Така цялото решение е със сложност O(sqrt(N)).

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