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

Dean's Cup, 2017

Тази година броят автори беше дори по-голям от миналата - цели пет различни човека!
Освен дългогодишните автори Александър Георгиев и Ивайло Странджев, за втора година се включиха четирикратният носител на купата Владислав Харалампиев, както и Владимир Владимиров. Новото попълнение сред авторите беше ученикът Александър Кръстев, който допринесе (както се оказа) една от най-сложните задача в темата.

От дадените десет задачи, две бяхме оценили като "Trivial", две като "Easy", четири като "Medium", една като "Hard", и една като "Very Hard". Състезателите ни изненадаха, като Радослав Димитров реши "Very Hard" задачата за 6 минути, а "Hard" задачата - за 10. За сметка на това една от "Medium" задачите се оказа по-костелив орех.

Както обикновено, в задачите имаше известно количество закачки. Например, задачата Knapp казваше в заглавието си, какво е решението (Knapsack); задачата Tennis пък имаше решение на два реда, но повечето състезатели не се сетиха за него и писаха дългата имплементация.

Тази година всички задачи за Ели бяха лесни, а останалите - трудни. Как се променя животът...

Победители

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

За втора поредна година победител в "официалното" присъствено състезание и носител на Купата на Декана за 2017-та година стана Даниел Атанасов (който, освен всичко, беше и именник). Той постигна това като реши с една задача повече от следващите го студенти.

Следващите четири места в присъственото състезание бяха с по шест решени задачи, като определящо за класирането им беше единствено времето. На второ място (с 473 наказателни минути) се нареди Иво Дилов, а тройката (с 509 наказателни минути) заформи Антон Чернев. Забележете, че тримата миналата година бяха първи, втори, и четвърти, съответно, като единствено липсата на Георги Шопов (който вече е магистър и няма право да участва) промени класирането на Антон от четвърто на трето място.

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

Радослав Димитров за втора поредна година стана победител в задочното (онлайн) състезание, а също така и първенец в смесеното класиране. Той постигна това за смайващите 2 часа и 40 минути, като успя да реши двете най-сложни (според нас) задачи за сумарно 16 минути. Радо е ученик в 11-ти клас в ОМГ "Акад. Кирил Попов", гр. Пловдив.

На второ място се класира младата надежда на Българската състезателна информатика - Мартин Копчев - ученик в 8-ми клас в ПМГ "Акад. Иван Гюзелев", гр. Габрово. Само в същия дух!

Третият на виртуалния подиум беше Иван Иванов - студент от Американския Университет в Благоевград.

Награди

И тази година бяха предвидени награди за най-добрите, като студентите от Софийски Университет получиха парични награди, осигурени от университета, а участниците в онлайн изданието - с предметни награди от авторите на задачите. Фирмата, в която работим с Иво Странджев - HyperScience - също се включи с малка (useless) наградка за първенеца в присъственото състезание, за да остане все пак нещо материално за спомен.

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

• За onsite състезанието:
  
  1. 800 лева + Useless Box
  2. 500 лева
  3. 400 лева
  4. 300 лева
• За online състезанието:
  
  1. Портативна колонка JBL Flip 4
  2. Настолна игра Ticket to Ride: Europe
  3. Тесте карти за игра CodeDeck

Класиране

Rank	Name	Solved	Time	A	B	C	D	E	F	G	H	I	J
1	Радослав Димитров	10	756	1 (2:35)	1 (117:05)	1 (6:28)	1 (9:17)	5 (160:00)	3 (49:25)	2 (33:59)	3 (142:33)	2 (20:13)	1 (13:48)
2	Мартин Копчев	9	773	1 (4:42)	1 (234:25)	1 (22:39)	1 (9:51)	1 (47:48)	3 (62:46)	1 (81:07)	4 (152:23)	-	2 (37:08)
3	Даниел Атанасов	7	767	1 (9:29)	1 (100:28)	1 (17:43)	1 (22:08)	1 (211:21)	5 (296:44)	-	-	-	1 (28:30)
4	Иван Иванов	7	878	1 (5:31)	1 (132:49)	1 (25:54)	1 (29:59)	-	5 (296:25)	-	1 (229:52)	1 (0:00)	1 (76:38)
5	Иво Дилов	6	473	1 (5:09)	1 (27:27)	1 (35:40)	1 (41:48)	-	10 (0:00)	-	2 (270:14)	-	1 (72:42)
6	Антон Чернев	6	509	1 (12:38)	1 (167:24)	1 (39:02)	1 (20:05)	-	4 (131:01)	-	-	-	2 (58:11)
7	Даниел Данаилов	6	698	1 (5:53)	1 (182:47)	1 (34:19)	1 (18:06)	-	-	-	2 (238:05)	-	5 (118:44)
8	Даниел Урумов	6	742	1 (6:44)	2 (292:48)	1 (42:25)	1 (49:12)	4 (0:00)	-	-	3 (167:25)	-	2 (103:20)
9	Гико Копев	6	826	1 (18:42)	-	1 (35:40)	1 (43:04)	2 (151:20)	13 (266:56)	-	2 (0:00)	-	1 (49:44)
10	Илиян Йорданов	6	974	2 (21:17)	-	1 (25:59)	1 (29:39)	1 (0:00)	6 (120:56)	-	1 (282:25)	-	8 (232:56)
11	Александър Георгиев	6	1055	1 (4:52)	-	1 (140:58)	1 (44:58)	7 (0:00)	2 (206:51)	-	2 (247:19)	-	16 (69:11)
12	Антъни Господинов	5	270	1 (7:36)	1 (0:00)	1 (16:17)	1 (30:00)	-	3 (0:00)	-	-	5 (99:09)	1 (36:10)
13	Николай Денев	5	771	1 (7:50)	-	1 (54:29)	1 (28:43)	-	6 (0:00)	-	6 (220:22)	-	5 (279:09)
14	Иван Кирев	5	1082	1 (153:42)	-	2 (169:08)	1 (175:06)	4 (237:52)	-	-	-	-	1 (265:49)
15	Виктор Кожухаров	4	94	1 (10:37)	-	1 (16:56)	1 (21:04)	-	-	-	3 (0:00)	-	1 (45:18)
16	Александър Станев	4	114	1 (9:21)	-	1 (29:12)	1 (15:39)	-	10 (0:00)	-	-	-	1 (59:05)
17	Цвета Огнянова	4	204	1 (7:33)	-	1 (121:37)	1 (13:32)	-	3 (0:00)	-	1 (0:00)	-	1 (61:13)
18	Лазар Неновски	4	300	1 (5:07)	-	5 (122:16)	1 (26:04)	-	-	-	-	1 (0:00)	1 (66:32)
19	Станислав Николов	4	307	1 (8:20)	-	1 (32:32)	1 (27:57)	-	6 (0:00)	-	-	2 (0:00)	8 (97:55)
20	Камен Кънчев	4	315	1 (28:26)	-	2 (84:09)	1 (39:13)	-	-	-	-	-	1 (142:58)
21	Цветомир Кайджиев	4	745	1 (23:04)	3 (221:40)	-	1 (212:56)	-	-	-	-	-	1 (247:17)
22	Румен Михов	3	108	1 (16:49)	-	1 (42:10)	1 (48:32)	-	-	-	-	-	-
23	Михаил Михайлов	3	142	1 (8:42)	-	2 (99:01)	1 (14:07)	-	-	-	-	-	18 (0:00)
24	Йоана Зелова	3	164	1 (11:26)	-	4 (43:30)	1 (49:02)	-	-	-	-	-	-
25	Николай Максимов	3	486	1 (7:38)	-	-	1 (24:55)	-	-	-	-	-	10 (273:14)
26	Адриян Ибовски	3	541	1 (134:28)	-	1 (235:39)	1 (170:31)	-	-	-	-	-	-
27	Димитър Стайков	3	619	1 (181:26)	-	-	1 (143:20)	-	-	1 (0:00)	-	-	2 (274:07)
28	Спасиян Тодоров	2	29	1 (17:09)	-	-	1 (11:13)	-	-	-	-	-	-
29	Георги Каров	2	41	1 (16:36)	-	-	1 (23:32)	-	-	-	-	-	2 (0:00)
30	lolasd2sw	2	46	1 (9:49)	-	-	1 (35:17)	-	-	1 (0:00)	-	9 (0:00)	34 (0:00)
31	Антоний Златаров	2	154	1 (76:04)	-	-	2 (57:04)	-	-	-	-	3 (0:00)	-
32	Камен Кънев	2	194	1 (131:47)	-	-	1 (62:01)	-	-	-	-	-	-
33	larodi94	1	47	1 (46:55)	-	-	-	-	-	-	-	-	-

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

A. LeftPad

Това беше една от двете тривиални задачи в темата, като директно казваше какво изисква. Функцията leftpad() е наистина елементарна за имплементиране, особено ако се ползва STL. Не се очакваше тя да затрудни никой от състезателите - както и стана: абсолютно всички участници, предали поне едно решение, я решиха.

B. Binetrees

Ще използвам абревиатурите КЛД, ЛКД и ЛДК за означаване на различните видове обхождания, както и за реда на записване на върховете във входните масиви. Задачата се свежда до решаването на 2 случая:


1. Вход ЛКД и КЛД, изход ЛДК
2. Вход ЛКД и ЛДК, изход КЛД

Да разгледаме първия случай, в който имаме ЛКД и КЛД и търсим ЛДК. Авторското решение използва следната идея:

1. Намираме корена на текущото дърво, което разглеждаме (в началото това е цялото дърво). Това е първия елемент от КЛД разглеждането на текущото под-дърво.
2. Извикваме рекурсивно текущата функция за елементите наляво от корена (това е лявото под-дърво).
3. Извикваме рекурсивно текущата функция за елементите надясно от корена (това е дясното под-дърво).
4. Накрая печатаме корена (тъй като търсим ЛДК, той е последен).

След края на изпълнение на програмата ще разполагаме с ЛДК. Примерен код, който прави това (ползвайки аритметика с указатели): За втория случай (да намерим КЛД от ЛКД и ЛДК) трябва да разместим стъпки 2, 3 и 4 както и да коригираме начина на локализиране на поддърветата, но иначе е доста сходно.

В случая забележете, че търсим линейно корена в ЛКД представянето. Забележете, че за специални тестове това може да стане O(N) операция, правейки цялото решение O(N2). Това за съжаление е твърде бавно. Можем, обаче, предварително да запазим в допълнителни масиви индексите на всеки елемент във всяко от дадените ни обхождания, като така ще можем да намираме позицията на корена константно (O(1)). Така цялата сложност се ограничава до едно единствено обхождане (и печатане) на всички елементи, тоест O(N).

C. Knapp

Тъй като държахме да имаме задача за Динамично Оптимиране в темата, но в същото време "сложните" слотове бяха заети от други задачи, се наложи да дадем просто такова. За целта прибегнах до дребна модификация на една от най-популярните задачи за динамично - задачата за раницата. Интересен факт е, че това беше закодирано и в самото име на задачата (Knapp...sack). Както и очаквахме, мнозинството (над половината) от състезателите успяха да се справят и с нея.

Стандартно за задачата за Раницата, динамичната таблица е масив с размера на всички възможни сумарни времена, които може да отнеме ниво на подготовка. Тъй като Ели имаше една седмица, това са точно 7 * 24 * 60 = 10080 минути, тоест клетки на таблицата (+1, тъй като 0 също е валидна сума).

Попълваме таблицата задача по задача. В началото всички клетки са равни на нула, освен клетка нула (тъй като това Ели да не реши нито една задача е валидно ниво на подготовка). За всяка задача, обхождаме таблицата отзад-напред и ако дадената задача отнема A_i минути, то от всяка клетка k можем да решим и тази задача, като обновяваме клетка A_i + k, стига тя да попада в интервала [0, 10080].

След като сме добавили всички задачи, трябва да сумираме числата в динамичната таблица, което дава желания от нас отговор. Тъй като за всяка задача обхождаме дялата таблица, сложността е O(N∙T), където T е размерът на динамичната таблица (в случая е фиксиран на 10081).

D. DARBA

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

E. Tape

Тази задача беше подготвена от ученикът Александър Кръстев за Европейската Младежка Олимпиада по Информатика, която се проведе тази година в България. За нещастие, по време на тестването на задачата случайно попаднахме на много просто решение, което решаваше перфектно задачата. Също така се оказа, че има известна редица (редицата на De Bruijn), която е именно това, което се търси в задачата. В следствие на тези неща се отказахме да я дадем там, но пък пасна перфектно в това състезание!

Funnily enough, докато тествах задачата преди EJOI реших да си напиша рекурсия (бектрек), който да ми генерира оптимални редици. За мое учудване, той завършваше моментално за произволни дължини - дори за N = 1,000,000, колкото беше ограничението в първоначалния вариант на задачата! При това, тъй като го бях написал да генерира оптимални редици, генерираната редица не просто беше намирана супер бързо, а беше и оптимална. Всичко това със следната кратка рекурсийка:
Тук bits задава колко е дължината на уникалните под-стрингове, a[i] са битовете на редицата, която генерираме, а cnt ни казва колко пъти сме срещали всяка битова маска с bits бита (реално искаме да е не повече от 1).

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

Алтернативно (доказано) решение, което беше и първоначалната идея на автора на задачата, можете да видите тук.

F. FooBar

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

Ако има "bar"

Търси се дали някъде има последователност от "bar"-ове. Ако има такава, тя определя еднозначно къде върху числовата ос се намираме. Ако броят "bar"-ове е X, то числото, което го е изпечатало, е X * 7. Причината да изберем последователност от "bar", а не от "foo", е, че е сигурно, че никога нямаме две числа, делящи се на 7, без между тях да има поне едно делящо се на 3 (трябва да е очевидно защо).

И така, ако имаме последователност от "bar" някъде от входа, това, което трябва да направим, е да генерираме редицата "напред" и "назад".

1. Възможен подход за генериране на редицата преди първия "bar" е: обхождаме числата преди числото X * 7 и за всяко генерираме съответната последователност от "foo" и "bar" според условието. Не бива да забравяме, че числото X * 7 може да се дели на 3 и тогава трябва да добавим съответния брой "foo"-та преди да почнем да генерираме друго. Продължаваме да правим това, докато общо не генерираме поне толкова думи, колкото имаме във входа преди първия "bar". Повтаряме тази процедура с числата, които следват фиксираното.


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

Ако няма "bar"

Ако в редицата няма нито един "bar", трябва да преброим колко "foo"- та имаме. Нека означим този брой с Y. Тук имаме отново два случая:

1. Броят "foo"-та съответства на единствено число, т.е. числото е Y * 3.
   
   1. Ако Y се дели на 7, това не е валидна последователност (понеже е трябвало да изведем и (Y / 7) * 3 "bar"-а)
   2. В противен случай, редицата ни е интервалът [Y*3, Y*3], разширен както е описано в "Разширяване на интервала"
2. Броят "foo"-та съответства на две последователни числа (забележете, че не може числата да са повече от две без да срещнем число делящо се на 7). За да стане това, трябва броят "foo"-та да е нечетен (защо?). Нека означим този брой с 2*K + 1. Тогава двете числа ще са K*3 и (K+1)*3. Отново има два случая:
   
   1. Ако някое от числата в затворения интервал [К*3, (К+1)*3] се дели на 7, нямаме решение и извеждаме -1
   2. В противен случай разширяваме интервала [K*3, (K+1)*3] както е описано в "Разширяване на интервала" и това е отговорът

Разширяване на интервала

Трябва да се внимава когато се извежда отговорът: ако има няколко възможни редици, трябва да изберем започващата най-рано, а ако още има няколко кандидата - трябва да изберем завършващата най-късно. Това означава, че отговорът може да започва с число, което не се дели нито на 3 нито на 7 и/или да завършва на такова число. Така че, когато намерим редица в някоя от точките по-горе, трябва да я разширим колкото можем и в двете посоки докато стигнем до число, делящо се на 3 и/или 7.

G. GCD

Анализ на задачата от автора можете да намерите тук.

H. Lamer

Първото наблюдение в решението на тази задача трябва да е, че увеличаването на животите на главите всяка секунда не влияе никак на избора коя глава трябва да бъде отсечена. С други думи ако трябва да изберем коя глава да отсечем във фиксирания интервал [from; to] в момент 0, то това ще бъде същата глава ако направим същата заявка за кой да е момент t. Изменението на главите е еднакво за всяка глава и съответно минималната глава в момент 0 в интервала [from; to] ще бъде минимална по всяко време.

След като се досетим това, вече е очевидно, че задачата е доста чист вариант на Range-Minimum Query проблема. При това на по-простия тип, където елементите върху които търсим минимумите не се променят след като са инициализирани. В този случай може да се приложи и прост алгоритъм със сложност O(1) за отговор на заявките, но със O(N∙log(N)) препроцесинг.

Идеята на това решение е следното: да си преизчислим минимумите за всички под-последователности с дължини 1, 2, 4, 8, 16, ..., ${{максималната степен на 2, която е по-малка или равна на броя числа}} на оригиналната редица. Това става със сложност O(N∙log(N)) защото имаме O(N) такива под-последователности с дължина степен на двойката (оценката е малко щедричка tbh) и броят на тези дължини е log(N), следователно общото време за преизчисляване е O(N∙log(N)).

След като направим това, отговорът на заявка "кое е минималното число в интервала [from, to]?" може да намерим като минимума измежду отговора на заявките за под-интервали [from; x] и [y, to] където х и у са НЯКАКВИ числа в интервала [from;to] и такива че x ≥ y (т.е. двата интервала се "засичат" по средата). Ето тук нашата таблица се намесва, за да ни осигури константна сложност за [from; x] и [y; to]; достатъчно е ние да си изберем х и у, така че двата интервала да се припокриват и да сме преизчислили резултата за тях. Един лесен за запомняне начин е да се използва максималната степен на двойката, ненадвишаваща броя на числата в интервала [from; to]. Нека това число е m. Тогава ans(from, to) = min(ans(from, from+m-1), ans(to-m+1, to)), където ans(from, from+m-1) и ans(to-m+1, to) гарантирано можем да вземем от таблицата с преизчислените резултати, защото са под-интервали с дължина степен на двойката и вече сме сметнали резултата за тях.

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

I. XorSum

В тази задача се искаше да "умножим" два полинома, като обаче "умножението" беше малко по-различно: вместо сума на i и j във формулата, имахме техния XOR.

Стандартното умножение на два полинома се дефинира като C[k] = SUM(i=0..k) {A[i] * B[k-i]}.

Наивното решение със сложност О(N2) не ни върши работа заради голямото ограничение на N (N ≤ 100,000). От това ограничение можем да предположим че очакваното решение ще е със сложност О(N∙log(N)). За да достигнем до решението на задачата, трябва първо да започнем от факта, че за да умножим два полинома за О(N∙log(N)), трябва да използваме Fast Fourier Transformation.

За конкретната задача ще можем да използваме трансформация подобна на FFT, но малко по-проста: това е тази на Walsh–Hadamard. Тук (частта след FFT) може да видите как точно работи FWHT (от Fast Walsh-Hadamard Transform). Накратко чрез тази трансформация, можем да "умножаваме" полиноми като вместо сума на i и j, използваме техния XOR, OR, AND и други побитови операции. И това се прави със сложност О(N∙log(N)).

И всъщност това е цялата задача - трябва да напишем бърза трансформация на Walsh-Hadamard за XOR. В линкнатия tutorial за FWHT има няколко задачи, които не е лошо да видите, за да видите как се използва тази трансформация в повече детайли (Random Nim Generator, And Closure).

Интересно нещо за тази трансформация е, че понякога можем да я използваме за да оптимизираме решения, които не се очаква да минат. Това най-често се среща при задачи свързани с динамично оптимиране с побитови маски. Понякога за такива задачи съществува О(2N∙2N∙N) решение, което, с трансформация на Walsh-Hadamard, можем да свалим до О(2N∙N∙N) (а авторът да иска О(2N∙N) решение с допълнителни наблюдения). Пример за такава задача е Token Grid.

J. Tennis

И тази година включихме "Трололо" задача в темата (сходно на WordCoins от миналата година), като това беше задачата Tennis. Макар и правилата да са описани стриктно и имплементирайки ги да можете да решите задачата, малцина от състезателите се сетиха, че всъщност мачът приключва в момента, в който победителят достигне два сета (при формат "2 от 3"). Тъй като в условието е казано, че мачовете са изиграни изцяло (тоест никой не се е е предал), то победител е винаги последният човек, който е спечелил точка! Така решението беше просто да изчетете всички стрингове от входа и да изпечатате последния от тях.