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

Dean's Cup, 2011

Темата се получи сравнително добре балансирана, като всички задачи с изключение на една бяха решени по време на състезанието (при това - имаше човек, който успя да стори това сам!). Единствено задачата Random Sums, която изискваше по-екзотична структура данни, остана нерешена. Може би и за напред можем да даваме подобни задачи. =)

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

Победители

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

Победител в присъственото състезание и съответно заслужил Купата на Декана стана Владислав Харалампиев, първи курс, специалност Компютърни Науки. Той успя да реши цели десет задачи, с което победи с голяма преднина дори трето- и четвъртокурсниците, които тази година можеха да участват официално. Той беше и единственият присъствен състезател, който реши някоя от двете сложни задачи. Честито и браво за страхотната победа!

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

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

След тях челната десятка допълват Никола Таушанов (също 8 задачи), Красимир Георгиев (с най-добро време от състезателите със 7 задачи), на шесто място е миналогодишният шампион Иван Георгиев, след него Николай Хубанов, Иван Тодоров, Николай Русев и Борислав Вълков.

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

Победител в задочното (онлайн) състезание стана шампионът от 2005-та година Веселин Георгиев, който водеше през почти цялото състезание до седем минути преди края, когато Влади предаде десетата си задача. Интересно е, че Веско изпрати минаващо решение на своята десета задача едва 42 секунди след края на състезанието. Тази по-малко от минута го лиши от победата, тъй като така той повеждаше Влади (понеже би имал с близо 200 минути по-добро време и равен брой задачи).

Атанас Вълев грабна второто място в онлайн класирането с осем задачи и сравнително малко на брой грешни събмити.

Румен Христов завоюва третото място, като водеше в началото на състезанието (с четири задачи за 12 минути). Той, обаче, предпочете да решава една от трудните задачи (и беше първият, който успя да се справи с нея – той предаде WinterGames успешно два часа и половина след началото на състезанието). След това той спря участието си (отивайки да спи), въпреки, че имаше шансове да победи.

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

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

	Name	Solved	Time	A	B	C	D	E	F	G	H	I	J	K	Att.
1	Владислав Харалампиев	10	1161	5 (0)	11 (0)	43 (0)	47 (1)	176 (1)	- ()	96 (2)	69 (0)	293 (1)	53 (0)	263 (0)	15
2	Стефан Аврамов	8	776	6 (2)	13 (1)	26 (0)	64 (0)	243 (1)	- (5)	133 (0)	96 (0)	- ()	111 (0)	- ()	17
3	Даниел Балчев	8	1105	9 (1)	20 (1)	159 (0)	95 (3)	- (6)	- ()	73 (0)	231 (4)	- ()	109 (0)	225 (0)	23
4	Никола Таушанов	8	1488	7 (0)	29 (1)	53 (0)	182 (6)	- ()	- ()	198 (4)	91 (4)	- ()	207 (0)	296 (6)	29
5	Красимир Георгиев	7	557	9 (0)	19 (1)	83 (0)	132 (1)	- ()	- ()	144 (0)	56 (0)	- ()	70 (0)	- (2)	11
6	Иван Георгиев	7	683	9 (1)	20 (0)	37 (1)	97 (4)	- ()	- ()	141 (0)	129 (0)	- ()	106 (1)	- (5)	19
7	Николай Хубанов	7	984	83 (1)	15 (0)	107 (0)	162 (1)	- ()	- ()	222 (4)	53 (0)	- ()	219 (0)	- ()	13
8	Иван Тодоров	6	552	18 (0)	13 (0)	48 (1)	171 (1)	- ()	- ()	165 (1)	75 (0)	- ()	- ()	- ()	9
9	Николай Русев	5	629	9 (0)	19 (1)	92 (1)	- ()	- ()	- ()	202 (5)	- ()	- ()	166 (0)	- ()	12
10	Борислав Вълков	4	234	36 (2)	8 (1)	68 (1)	- ()	- ()	- ()	- ()	- (2)	- ()	41 (0)	- ()	10
11	Калоян Йовчев	4	305	9 (0)	21 (0)	163 (0)	- ()	- ()	- ()	- ()	- (2)	- ()	71 (2)	- (5)	13
12	Александър Тодоров	4	368	45 (1)	31 (2)	65 (0)	- (1)	- ()	- ()	- ()	- ()	- ()	166 (0)	- ()	8
13	Румен Палетов	4	564	37 (4)	46 (0)	224 (0)	- ()	- ()	- ()	- (9)	- (6)	- ()	157 (1)	- ()	24
14	Александър Маринов	4	851	30 (1)	72 (4)	237 (6)	- ()	- ()	- ()	- ()	- ()	- ()	271 (1)	- ()	16
15	Мария Железова	3	143	22 (0)	9 (0)	- ()	- (3)	- ()	- ()	- ()	- ()	- ()	110 (0)	- ()	6
16	Рали Емилов	3	246	30 (2)	54 (0)	- ()	- ()	- ()	- ()	- ()	- (1)	- ()	121 (0)	- ()	6
17	Ангел Василев Николов	3	315	38 (3)	20 (1)	- (6)	- ()	- ()	- ()	- (1)	- ()	- ()	176 (0)	- ()	14
18	Мая Лекова	3	339	24 (1)	42 (3)	- (2)	- ()	- (2)	- ()	- (1)	- ()	- ()	192 (0)	- ()	12
19	Александър Иванов	3	387	16 (2)	207 (3)	- ()	- (7)	- (1)	- ()	- (1)	- ()	- ()	43 (1)	- ()	18
20	Благой Борисов	2	138	32 (0)	86 (1)	- (1)	- ()	- (2)	- ()	- ()	- ()	- ()	- ()	- ()	6
21	Свилен Андонов	2	240	34 (4)	65 (3)	- (2)	- ()	- ()	- ()	- (3)	- ()	- ()	- ()	- ()	14
22	Атанас Керезов	2	254	72 (1)	101 (3)	- (1)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	7
23	Пламен Начев	2	320	132 (6)	68 (0)	- ()	- ()	- ()	- (2)	- (1)	- ()	- ()	- (2)	- ()	13
24	Тодор Бончев	2	400	15 (1)	265 (5)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- (5)	- ()	13
25	Михаил Петкош	2	433	62 (4)	190 (5)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- (2)	- ()	13
26	Христо Георгиев	1	19	19 (0)	- (1)	- ()	- ()	- ()	- (2)	- (2)	- ()	- ()	- ()	- ()	6
27	Красимир Петров	1	145	45 (5)	- ()	- (3)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	9
28	Теодор Ангелов	1	215	195 (1)	- (4)	- ()	- ()	- (2)	- ()	- ()	- ()	- ()	- ()	- ()	8
29	Димитър Калудов		0	- (1)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	1
30	Йордан Стоянов		0	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- (2)	- ()	2

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

	Name	Solved	Time	A	B	C	D	E	F	G	H	I	J	K	Att.
1	Веселин Георгиев	9	601	6 (0)	9 (0)	26 (1)	46 (0)	119 (0)	- ()	72 (0)	89 (0)	- (3)	50 (0)	158 (0)	13
2	Атанас Вълев	8	740	6 (0)	12 (0)	25 (0)	64 (1)	212 (0)	- ()	167 (2)	117 (0)	- ()	74 (0)	- (4)	15
3	Румен Христов	5	358	20 (0)	26 (0)	24 (0)	- ()	- ()	- ()	- ()	- ()	155 (5)	32 (0)	- ()	10
4	Антон Димитров	5	1253	210 (1)	217 (0)	245 (0)	- ()	- ()	- ()	274 (3)	- (2)	- ()	224 (0)	- ()	11
5	Момчил Иванов	4	267	11 (0)	45 (0)	98 (0)	- ()	- ()	- ()	- ()	- ()	- ()	111 (0)	- ()	4
6	Йордан Чапъров	3	125	34 (0)	38 (0)	- ()	- (4)	- ()	- ()	- ()	- (1)	- ()	52 (0)	- ()	8
7	Мартин Маринов	3	239	81 (0)	102 (0)	- (7)	- ()	- ()	- ()	- ()	- ()	- ()	55 (0)	- ()	10
8	Georgievbg	3	516	80 (0)	143 (7)	- ()	- ()	- ()	- ()	- (1)	- (2)	- ()	152 (0)	- ()	13
9	Иван Камбуров	1	54	34 (1)	- ()	- ()	- ()	- (5)	- (1)	- (3)	- ()	- ()	- (1)	- ()	12
10	Петър Петров	1	155	135 (1)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- (1)	- ()	3
11	Владимир Начев	1	211	191 (1)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	2
12	Андрей Лалев	1	273	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	273 (0)	- ()	1

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

Можете да разгледате пълното класиране за повече информация.

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

Задачите бяха подготвени от мен (Александър Георгиев) и бяха разпределени по сложност, включващи две тривиални задачи, две лесни, пет средни и две трудни. Застъпени бяха темите Цикли и Масиви, Сортиране, Графи (Търсене в Дълбочина и Дейкстра), Двоично Търсене, Геометрия (пресичане на прави, намиране на разстояние от точка до права), Математика (комбинации без повторение, факториел, модулна аритметика), Пълно Изчерпване, Динамично Оптимиране и една задача с не особено стандартна структура данни.

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

Collatz

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Easy, Search, Iteration
Statement | Archive | Online Judge

A.Collatz

Първата задача в темата не изискваше никакви по-специфични знания – просто трябваше да се имплементира това, което е описано в условието. Самото условие е базирано на Collatz Conjecture - сравнително известно предположение, което някои от състезателите най-вероятно са виждали и преди. Интересното в случая е, че знаенето за въпросното твърдение може само да навреди на състезателите.

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

Реално това е вярно за всички числа до 10 * 2⁵⁹ (поне за тях е проверено), а ако предположението е вярно – за всички числа... с изключение на две. Ако началното число е 1, то цикълът е 1, 4, 2, 1, ..., тоест отговорът е 1. Също така ако началното число е 2, то цикълът е 2, 1, 4, 2, ..., тоест отговорът е 2.

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

При решението чрез симулация единият вариант беше посетените числа да се пазят в STL-ски set, а другият – просто в масив. Неочевидно е, че максималното число, което можем да достигнем, е 250,504 (започвайки от 703). Така че е възможно да получим runtime error ако не заделим достатъчно голям масив. Този тест, а както и числото, което образува най-дълга редица (с дължина 179, започвайки от 871) присъстваха в тестовете.

Решението с 3 if-а е със сложност O(1), докато това със симулацията, ако ползваме set да пазим вече посетените числа, би имало сложност O(L∙logL), където L е дължината на редицата, която се образува.

Orderings

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Easy, Simple Math, Bruteforce
Statement | Archive | Online Judge

B.Orderings

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

Броят подреждания на N предмета от един тип и M предмета от друг тип би било същото като да наредим N предмета в N + M позиции. Тъй като комбинациите без повторения са симетрични, то това също така е еквивалентно на това да намерим по колко начина можем да наредим M предмета в N + M позиции. Така от нас се очаква да сметнем C(N, N + M), което е (N + M)! / (N! * M!).

Забележете, че ако сметнем отговора директно по формулата, трябва да изчислим (N + M)!, което в най-лошия случай е 22!. Това с малко прехвърля 64-битовите типове на компютрите и ще overflow-не.

За сметка на това можем леко да модифицираме формулата, като извършим делението на N! (или M!) докато смятаме (N + M)!. Тоест ще започнем цикъла, който смята (N + M)! от N + 1 вместо от 1 и така ще симулираме деление на N!. Така избягваме overflow-а, което беше и единственото трудно нещо в задачата.

Решението има сложност O(N + M), което определено не е проблем за дадените ограничения.

FightClub

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Easy, Sorting, Greedy
Statement | Archive | Online Judge

C.FightClub

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

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

Тоест, ако сортираните сили на участниците са S₁, S₂, ..., S_K, то цената на турнира ще е S₂ – S₁ + S₃ - S₂ + ... + S_K - S_K-1. Ако разгледаме тази сума, това е точно разликата между най-силния и най-слабия робот в турнира. Очевидно е изгодно робот със сила B да участва в турнира, ако участват роботи със сила A и C, ако A < B < C.

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

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

Решението има сложност O(N∙logN) за да сортираме по сила роботите и O(N) за да намерим интервала, обхващащ най-много на брой от тях.

Забележете, че поради сравнително малките сили на роботите (до един милион) можем да ползваме сортиране чрез броене (Counting Sort) и така да постигнем сложност O(M) за сортирането. Това, обаче, в случая не е нужно (двата алгоритъма дават сходни времена), така че и O(N∙logN) и O(M + N) вършеха работа.

Famous

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Medium, Graphs, BFS, STL
Statement | Archive | Online Judge

D.Famous

Първата задача, определена като "Medium" по сложност, беше от тема Графи. Въпреки че в условието се пита за оптимална подредба на съобщенията, сравнително лесно се вижда, че просто greedy води до нея – няма смисъл да се пращат съобщения между непопулярни ученици, ако единият от тях може да стане популярен преди това.

Така стигаме до просто търсене в ширина – в началото вкарваме в опашката всички първоначално популярни хора. Изпращаме всички съобщения, единият от чиито участници е в опашката. Така евентуално сме получили нови популярни хора в училището. Вкарваме и тях в опашката и продължаваме този процес докато можем. За всеки човек трябва да пазим с колко популярни хора е общувал и в момента, в който този брой стане равен на K, трябва да го обявим за популярен (да го включим в отговора) и да го вкараме в опашката.

Има две неща, за които трябва да внимаваме. Първото е, че някои от популярните хора може да комуникират с K или повече популярни – трябва да внимаваме да не ги включим два пъти в отговора. Второто (и по-вероятно за бъркане) нещо е, че спокойно може да има повече от едно съобщение между двама души (тоест графът е мултиграф). Трябва да внимаваме как броим популярните хора, с които е общувал всеки ученик (или просто да премахнем повтарящите се ребра преди да започнем BFS-то). Това беше нещо, което докара по няколко Wrong Answers на голям брой състезатели. Само двама от десетте човека, които предадоха успешно задачата, я предадоха от първи път.

Освен тези подводни камъни, други големи трудности в задачата нямаше. Входът и изходът бяха дадени по такъв начин, че да насърчават ползването на STL и по-точно queue, string, и set. Сложността на решението е O(N + M), което е нормалната сложност за BFS. При използване на set за пазене на съседите тя нараства до O(N + M + M∙logN), но ограниченията бяха достатъчно малки това изобщо да не повлияе на времето за изпълнение.

DeansCup

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Medium, Dynamic Programming
Statement | Archive | Online Judge

E.DeansCup

Тази задача също беше включена като "Medium" в темата, но се оказа значително по-сложна от предходната. Това малко ме учуди (очаквах повече хора да се досетят за решението), но явно или големият брой задачи, или това, че състезателите не са виждали подобен тип задачи, доведе до само четирима души с правилно решение – двама от online и двама от onsite състезанието. По стечение на обстоятелствата тези четирима души бяха и първите четирима в смесеното класиране.

Самата задача беше усложнена версия на задача, давана в Topcoder (SRM 504, Div1 250). Единствената разлика беше, че докато там ограниченията за дължина на стринга бяха до 100,000, в тази задача бяха до 100,000,000.

Наивното решение с проста симулация води до O(N2∙M2) решение, което е много далеч от приемливо - даже в по-простия вариант на TopCoder нямаше да мине. Това решение, обаче, лесно можеше да се оптимизира, като забележим, че не трябва да извършваме всичките операции, които са описани при вадене на бяла или черна топка. Достатъчно е да пазим два флага – един, който отбелязва дали топките са обърнати наобратно, и един, който отбелязва дали цветовете им са сменени. Така решението става O(N∙M) и минаваше в TopCoder.

В дадения от мен вариант, обаче, това решение също не върви достатъчно бързо! Че как може да преброим броя черни топки в произволна редица за под линейно време!? Можем, след като забележим, че редицата не е толкова "произволна", колкото пише в условието. Де факто, тя ни е зададена чрез повтаряне на един и същ, сравнително кратък стринг. Ще използваме този факт за да напишем дори по-бързо решение.

Нека началният стринг е BWBB от който имаме десет повторения. Нека разгледаме изпълнението на алгоритъма (подчертания символ е "началото" на стринга):

1. BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB (answer: 1)
2. BWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW (answer: 2)
3. BB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB (answer: 3)
4. W+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW (answer: 3)
5. WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW (answer: 3)
6. WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBW (answer: 3)
7. BWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBW (answer: 3)
8. BWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WB (answer: 4)
9. BB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BW (answer: 5)
10. W+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WB (answer: 5)
11. WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WB (answer: 6)
12. BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+BWBB+B (answer: 7)
13. WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBWW (answer: 7)
14. WBWW+WBWW+WBWW+WBWW+WBWW+WBWW+WBW (answer: 7)

Забележете постановката в ред шест и ред четиринадесет: и в двата реда стрингът започва с "WBWW" и завършва с "WBW". Единствената разлика е, че в ред шест посредата имаме седем повторения на първоначалния стринг, докато в ред четиринадесет имаме пет. Това е "цикъл" в изменянето на стринга – можем да предположим, че на ред двадесет и две ще имаме три повторения по средата и отговор единадесет, на ред тридесет ще имаме едно повторение по средата и отговор петнадесет. Така можем да продължим итерацията за намиране на отговора:

30. WBWW+WBWW+WBW (answer: 15)
31. BWW+WBWW+WBW (answer: 15)
32. BWW+WBWW+WB (answer: 16)
33. BB+BWBB+BW (answer: 17)
34. W+WBWW+WB (answer: 17)
35. WBWW+WB (answer: 18)
36. BWBB+B (answer: 19)
37. WBWW (answer: 19)
38. WBW (answer: 19)
39. BW (answer: 19)
40. B (answer: 20)

Така, веднъж открили цикъла, можем много лесно да съкратим търсенето, премахвайки много повторения на стринга едновременно с константна сложност. Накрая остават сравнително малко топки, които можем да обработим по линейния начин. Важното е, че съкратихме огромна част от работата, намирайки цикъла. В дадения пример, вместо 4 * 10 = 40 итерации направихме само 25, но ако имахме, например, 100 повторения на стринга, (вместо 10), щяхме отново да имаме 25 итерации, вместо 400.

Сега да видим колко итерации ще ни трябват за да намерим цикъл. Ситуацията на стринга определихме от 4 неща:

• На коя позиция сме в най-лявото (незавършено) повторение на стринга;
• На коя позиция сме в най-дясното (незавършено) повторение на стринга;
• Флаг дали топките са обърнати;
• Флаг дали топките са със сменен цвят.

Тъй като дължината на стринга е най-много 1000, логично е да намерим цикъл след най-много 1000 * 1000 * 2 * 2 итерации. За всеки state трябва да пазим по две неща:

• Колко топки е имало при първото му срещане?
• Какъв е бил отговорът при първото му срещане?

Забележете, че след намиране на цикъл и премахването му, оставащия брой топки е не повече от 1000 * 1000 * 2 * 2 (големината на стейта). Така решението, използващо тази оптимизация, има сложност O(N2).

RandomSums

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Hard, Data Structures
Statement | Archive | Online Judge

F.RandomSums

Задачата Random Sums беше една от двете, оприличени като "Hard". Наистина, нейното решение изобщо не е лесно – нито за измисляне, нито за писане.

Простата симулация беше обречена на неуспех – това трябваше да е ясно на мнозинството от състезателите. Значително по-неясно беше дали решение с балансирани двоични дървета би минало. Поради типа на състезанието (ACM) не бяха дадени нито time limit-и на задачите, нито пък големината на тестовете, съответно беше почти невъзможно да се предположи дали това е решението или не.

Четирима от състезателите пробваха да предадат решение по време на състезанието, като решението на Стефан Аврамов е почти вярно, с изключение на това, че не сумира отговора в long long, и е 4-5 пъти по-бавно от time limit-а, тъй като двоичните дървета вкарват в сложността логаритъм, който го няма в авторското решение.

Истинското решение на задачата използва структурата данни Tiered Vector. Тя е структура за съхранение на елементи, която предоставя следните сложности:

• O(N∙logN) за строене на структурата от N елемента;
• sqrt(N) за добавяне и изтриване на елемент, където N е броят елементи, които се пазят в момента;
• O(1) за питане кой е k-тият по големина елемент;
• O(log(sqrt(N)) за питане дали (и ако да – къде) се съдържа даден елемент по неговата стойност.

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

Нека разгледаме накратко и самата структура данни. Основната ѝ идея е да държим елементите (числата) в bucket-и от по приблизително sqrt(N) елемента. В случая, тъй като трябва всички bucket-и да са с еднаква големина, то можем да изберем някоя степен на 2, която е близка до корен от най-големия брой елементи, който може да имаме. Тъй като този брой беше малко повече от 100,000, можеше да ползваме големина на бъкетите 256 или 512. В една по-добра имплементация големината на бъкетите би се променяла според броя вкарани елементи, но в случая това не беше нужно да бъде имплементирано (тъй като усложнява ненужно кода).

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

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

Нека видим как бихме намерили k-тия по големина елемент. Знаем, че той ще е в бъкет с индекс k / sqrt(N). Също така, в самия бъкет, елементът ще е с индекс k % sqrt(N) (индексирано от итератора за начало на цикличния списък). Както бъкетите, така и индексите в тях, можем да индексираме константно. Следователно можем да намерим k-тия елемент с O(1).

Добавянето на елемент става малко по-сложно. Първо, трябва да намерим в кой bucket да го добавим. С двоично търсене можем да направим това за O(logN). След това, трябва да намерим коя позиция би заел той. Вътре в бъкета го слагаме след последния (най-големия) елемент, или, ако бъкетът е пълен, запазваме най-големия елемент в допълнителна променлива и го заместваме с новия елемент. Това, евентуално, би нарушило наредбата на елементите, затова го разменяме с други елементи "наляво" докато той е по-малък от тях. В най-лошия случай го разменяме с всички елементи в бъкета, тоест това изисква O(sqrt(N)) разменяния.
Също така, ако бъкетът е бил пълен (тоест е нямало място, където да го сложим) трябва да намерим място за изхвърления най-голям елемент. Тъй като всички елементи от следващия бъкет са по-големи или равни на него, то го слагаме на първо място в следващия бъкет (като преместваме итераторите за най-малък и най-голям елемент в съответните бъкети). Ако и той е пълен, махаме неговия най-голям елемент и го местим в по-следващия бъкет, и т.н., докато не стигнем до бъкет, който не е пълен (това е последния бъкет). Тоест, при местене на най-големия елемент на един бъкет в следващия бъкет, този елемент става най-малък негов елемент. Тъй като имаме sqrt(N) на брой бъкета, то в най-лошия случай трябва да напраим толкова на брой константни премествания. Така insert-ът става със сложност O(logN + sqrt(N) + sqrt(N)), тоест O(sqrt(N)).

След като инсъртът е със сложност O(sqrt(N)) тогава няма ли целият алгоритъм да е O(N∙sqrt(N))?

Не, защото мнозинството от тези N елемента ни се задават съвсем в началото преди query-тата. Така можем да ги insert-нем по-бързо – просто ги сортираме и ги вкарваме линейно.
Едно възможно място, откъдето можете да прочетете повече за Tiered Vector е в темата за тази структура данни на сайта, а друго би бил pdf-ът, от който аз я научих.

Popcounts

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Easy, Preprocessing, Arrays, Binary Numbers
Statement | Archive | Online Judge

G.Popcounts

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

Глупавото решение: ползваме вградената функция __builtin_popcount(). Оказва се, че в по-новите версии на G++ е реализирана по-добре и можете да напишете решение, което е точно на ръба (но минава). Дори малки забавяния обаче ще накарат решението да TL-тне. По-лошото е, че няколко последователни събмита на един и същ код може да не минат, докато следващият на същия код да мине.

Умно решение: можем да преизчислим в масив по колко бита има всяко число в интервала [0, 32767] с (дори не много бърза) функция popcount(). След това, popcount на едно 30-битово число (според ограниченията на задачата числата се събират в 30 бита) става като разделим числото на две 15-битови такива и ползваме вече преизчислените стойности.
Нека MAX = 32768, и сме изчислили теглата на всички до-15-битови числа в масива weight[MAX]. Тогава popcount(A) == weight[A & (MAX - 1)] + weight[A >> 15];.

DJKrisaT

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Medium, Graph, Dijkstra, Binary Search
Statement | Archive | Online Judge

H.DJKrisaT

Дори името на задачата трябваше да говори на състезателите "Dijkstra" (DJKrisaT всъщност е анаграма на DiJKsTra). Реших в темата да има и една по-стандартна задача за да видим кой си е учил теорията. Единствената дребна врътка беше също толкова стандартното двоично търсене по отговора, което ни казва кои ребра можем да ползваме и кои не. Сложността на решението беше O(logK∙(N∙logN + M)).

WinterGames

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Hard, Dynamic Programming
Statement | Archive | Online Judge

I.WinterGames

(автор на анализа: Владислав Харалампиев)
Първото нещо, което трябва да се запитаме, е какво множество от числа (височини) може да се среща в оптималното решение. Очевидно, началните височини може да се срещат. Още повече, поне една от началните височини задължително не се променя в оптималното решение (иначе можем или да прибавим към всички 1, или да извадим 1 - една от тези две операции ще намали цената на решението) . Ако позицията Т с височина А не се променя, то за тази вляво има смисъл или също да не се променя, или да стане А+1, или А-1 (иначе можем да подобрим отговора, като сменим височината с някоя от тези три). С аналогични разсъждения може да се покаже, че ако avb е обединението на целите числа в интервалите [А_i-51, А_i+51] за всяко А_i от входа, то множеството от височини от оптималното решението се съдържа в avb. Т.к. |avb| < 6000, то ни върши работа (иначе можеше още да се намаля). Доста писане излезе за доста глупаво наблюдение.

След като сме построили avb, има смисъл да го сортираме (и да изключим повторенията). Сега можем да формулираме такива функции:

• OPT(pos, groups): минималната цена да разбием всички числа до позиция pos на groups групи. Това прилича на търсената стойност и OPT(N - 1, K) е точно тя (N е количество числа на входа, а K е на колко групи да ги разбием).
• DP(pos, groups, height, type): минималната цена да разбием всички числа до позиция pos на groups групи, като последната група е растяща, ако type е 0, и намаляваща, ако type е 1. Височината на елемента на позиция pos в отговора трябва да е ≤ avb[height], ако type = 0, и ≥ avb[height], ако type = 1.

Последната функция може да изглежда малко странно, но се оказва удобна за смятане. Работата идва от това, че pos * groups * height * type ≈ 25*10⁶, т.е. функцията трябва да се обновява за О(1). Ако, например, type = 0, то за предпоследния елемент на последната група трябва височината му да е по-малка от височината на последния. Удобно е информацията за всички такива по-малки предпоследни елементи да стои на едно място.

Сега формулите за преход (нека височините, зададени на входа, се пазят в Н[]):

• OPT(pos, groups) = min(DP(pos, groups, height, type)), за height = 1...|avb| и type = {0, 1};
• DP(pos, group, height, type) = min:
  1. abs(H[pos] - avb[height]) + OPT(pos - 1, group - 1)
  2. abs(H[pos] - avb[height]) + DP(pos - 1, groups, height +/- 1, type)
  3. DP(pos, groups, height +/- 1, type)

В горните формули:

1. Съответства на поставянето на елемента на последна позиция в самостоятелна група с височина avb[height].
2. Съответства на създаването на нова група, в която последният елемент е с височина avb[height]. Ако type = 0, то използваме варианта с height - 1 (предишният елемент е по-малък). Иначе използваме height + 1.
3. Съответства на това последният елемент да не е с височина avb[height]. Ако type = 0, то остава височината на последния да е avb[height-1] и използваме този вариант. Иначе използваме варианта с height + 1.

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

Тези рекурентни формули стават за динамично оптимиране. Единственото неприятно нещо е, че таблицата ще заема прекалено много памет. Това лесно се оправя, защото за да сметнем DP(pos, ...) ни трябват само стойностите за DP(pos - 1, ...) и OPT(pos - 1, ...), т.е можем да пазим само тези два "реда" (≈ 2 * 50 * 6000 * 2 ≈ 1,500,000 елемента, което е OK). Отговорът ще е числото в OPT(N - 1, K).

FactorialRoot

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Easy, Math, Ad-hoc, Brute Force
Statement | Archive | Online Judge

J.FactorialRoot

Тази задача беше последната, която беше оприличена като „Easy", макар и не "Trivial"... Тя имаше почти толкова решения, колкото и Orderings, ставайки третата най-ревашана задача в темата.

Да видим какво ни трябва за да я решим. Очевидно, да намерим N! би отнело много време и памет, да не говорим, че би изисквало дълги числа. А при толкова хора, които са я решили, трябва да има и нещо по-лесно. Нека си разпишем на листче (или напишем проста програма за) отговорите за числата от 1 до 10:

1. DR(1!) = 1
2. DR(2!) = 2
3. DR(3!) = 6
4. DR(4!) = 6
5. DR(5!) = 3
6. DR(6!) = 9
7. DR(7!) = 9
8. DR(8!) = 9
9. DR(9!) = 9
10. DR(10!) = 9

Хм, странно. От 6 нататък изглежда всички отговори са 9. Наистина, ако предадем програма, която печата 1 за 1, 2 за 2, 6 за 3 и 4, 3 за 5 и 9 за всяко друго число, тя ще има OK.

Защо се получава така? Един факт за digital root, който някои хора може би знаеха, беше, че DR(N) = (N % 9 == 0 ? 9 : N % 9) – тоест дигиталният корен е равен на остатъка на числото при деление на 9, или 9, ако този остатък е 0. Това е така, тъй като всяко число можем да представим като a * 1 + b * 10 + c * 100 + .... И тъй като събираме самите цифри, тоест независимо една цифра дали е в единици, десетици, стотици и т.н. (тоест на коя позиция в десетичния запис на числото е), тя допринася по един и същ начин към отговора, то 10^X % 9 ≡ 1 ни дава възможност да вземем самото число по модул 9.

Как ни помага това за съответната задача? Ами, факторизирайки шест факториел получаваме 6! = 1 * 2 * 3 * 4 * 5 * 6 = 1 * 2⁴ * 3² * 5. Той, а както и всеки следващ факториел, съдържа 3 на поне втора степен в разлагането си, следователно се дели на 9, следователно отговорът е 9.

Geometry

Dean's Cup 2011

Author: Alexander Georgiev
Tags: Medium, Geometry, Line-Circle Intersection
Statement | Archive | Online Judge

K.Geometry

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

Нека разгледаме времето. В смисъл в задачата. Ако снаряд ще се блъсне в правата, то във всеки момент след това той ще се е блъснал (duh). Следователно имаме някаква функция (на блъснатостта на снарядите с правата), която известно време е 0, след това става 1 и остава така завинаги. Задачата изисква да намерим момента, в който функцията става 1. Е, имаме и варианата, в който никой от снарядите не се блъска в нея. Него ще го разгледаме малко по-късно, като видим, че можем лесно да го включим в решението (да не го разглеждаме като частен случай).

Видяхме, че имаме някаква монотонна функция. Можем да направим binary search по нея (тоест по отговора (времето)).

Нека на текущата стъпка пробваме дали снаряд ще се е блъснал с правата във време t. Координатите на i-тия снаряд са (X_i + t * DX_i, Y_i + t * DY_i). Как можем да проверим дали снарядът е пресякал правата (ако за момента игнорираме окръжността около него)? Ами началната точка (X_i, Y_i) и крайната точка (X_i + t * DX_i, Y_i + t * DY_i) трябва да са от различни страни на правата – следователно трябва да дават различни по знак насочени лица спрямо отсечката (LX₁, LY₁), (LX₂, LY₂).

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

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

Забележете, че даже не е нужно да ползваме epsilon-и за тези сравнения – дори те да са неточни, binary search-ът ще намери малко по-голям отговор, който ще е достатъчно малко по-голям за да е все още верен.

Колко може да е максималният отговор? Тъй като всички входни числа са целочислени, то можем да направим наблюдението, че ако някой снаряд пресича по някое време правата, то с всяка единица време той се приближава с поне една единица разстояние. И тъй като координатите са в интервала [-10000, 10000], то, логично, максималният отговор би бил 20000. Следователно можем да ограничим binary search-а да търси в интервала [0, 20002]. Забележете, че ако никой от снарядите не пресича правата, то така намереният отговор ще бъде 20002. Следователно, можем просто преди да изпечатаме отговора, да проверим дали той е по-голям от 20001, и ако да -- да изпечатаме "NEVER".

Последното нещо, което е стандартно при binary search с нецели числа, е да не правим стандартния while (left <= right) цикъл на binary search-а, ами да правим определен брой итерации. В случая 100 итерации са повече от достатъчни за намиране на достатъчно точен отговор. Така описаното решение е със сложност O(I∙N), където I е броят итерации, които изпълняваме за двоичното търсене (в случая 100).