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

Dean's Cup, 2012

Противно на очакванията ми, задачите се оказаха по-сложни отколкото предполагах, като първенецът беше със седем от общо десет задачи. В края на състезаниетозадачата SnowCleaning остана нерешена, задачите Achievements и BankRobbery бяха решени само от по един човек, а задачата Mice - едва от двама. Никое от тези четири решения не беше от един и същ човек, затова цели трима човека бяха с равен брой задачи на първите три места.

За решаването на всички задачи не помогна и проблемът със сървъра, който възникна около четвъртия час на състезанието и продължи близо половин час. Тъй като задача H имаше сравнително голям тайм лимит (7 секунди), бяхме предположили, че това може да се случи, при което изрично бяхме помолили състезателите да не пращат решения със сложност O(N∙log(N)) и нагоре. Това не повлия особено на състезателите и все пак големият брой предадени time limit-ващи решения (в някои случаи по няколко едно след друго от един и същ човек) срутиха сървъра :) Това ще ми е за урок да не давам задачи с голям тайм лимит.

Победители

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

В официалното състезание шампионът от миналата година Влади Харалампиев защити титлата си и отново грабна първото място. За това му помогнаха както доброто начало с първа предадена задача едва в петата минута, така и решаването на геометрията (задача Bank Robbery), като той беше единственият, който успя да се пребори с нея. На второ място този път се класира Даниел Балчев и прекъсна серията на Стефан Аврамов от четири поредни години на второ място в турнира. Третото място пък беше за шампиона от 2010-та година - Иван Георгиев.

Онлайн състезание

С относително по-добро време от победителя в официалното състезание беше победителят от онлайн варианта му - Атанас Вълев. Той пък беше единственият, който успя да се справи със сравнително трики задачата Achievement Unlocked. На второ място застана Румен Христов, който въпреки неудобния час (за него състезанието започна в 4 през нощта) успя да реши 6 задачи за час, да пробва две от сложните и след това си легна, като пропусна последните два часа и половина от състезанието. На трето място беше шампионът от 2006-та година Веселин Георгиев, който, за съжаление, се отказа от състезанието поради проблемите със сървъра.

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

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

	Name	Solved	Time	A	B	C	D	E	F	G	H	I	J	Att.
1	Владислав Харалампиев	7	718	5 (0)	128 (0)	15 (0)	47 (0)	- ()	- ()	276 (2)	108 (0)	- ()	96 (0)	9
2	Даниел Балчев	7	867	18 (0)	48 (1)	24 (0)	121 (4)	- ()	- ()	- (1)	152 (0)	238 (1)	123 (1)	15
3	Иван Вергилиев	6	465	18 (0)	42 (0)	11 (1)	63 (1)	- (2)	- ()	- ()	152 (1)	- ()	96 (1)	12
4	Иван Тодоров	6	915	10 (0)	117 (0)	23 (0)	141 (9)	- ()	- ()	- (1)	207 (5)	- ()	95 (2)	23
5	Владимир Владимиров	5	327	15 (0)	83 (0)	20 (0)	122 (1)	- (1)	- (3)	- ()	- ()	- ()	66 (0)	10
6	Никола Таушанов	5	346	18 (1)	79 (0)	11 (0)	37 (1)	- (7)	- ()	- ()	- (3)	- ()	119 (2)	19
7	Стефан Аврамов	5	620	11 (0)	62 (0)	55 (0)	135 (9)	- ()	- ()	- ()	- (8)	- ()	156 (1)	23
8	Тодор Бончев	5	737	20 (0)	52 (1)	30 (1)	144 (14)	- (2)	- ()	- ()	- (2)	- ()	169 (0)	25
9	Ясен Трифонов	5	864	142 (0)	157 (0)	148 (0)	187 (0)	- ()	- ()	- ()	- (4)	- ()	206 (1)	10
10	Румен Палетов	5	1150	22 (0)	207 (2)	32 (1)	272 (13)	- ()	- ()	- ()	- (1)	- ()	275 (1)	23
11	Николай Русев	4	349	23 (0)	68 (1)	76 (0)	- ()	- ()	- ()	- ()	- (7)	- ()	141 (1)	13
12	Георги Стоянов	4	424	16 (0)	- ()	23 (0)	56 (0)	- ()	- ()	- ()	- ()	- ()	248 (4)	8
13	Александър Димитров	3	173	6 (0)	- ()	16 (0)	- (2)	- ()	- (2)	- ()	- ()	- ()	150 (0)	7
14	Елица Христова	3	317	15 (0)	- ()	38 (0)	- ()	- ()	- ()	- ()	- (3)	- ()	223 (2)	8
15	Ангел Николов	3	334	20 (1)	- (6)	94 (0)	- (7)	- ()	- ()	- ()	- ()	- (2)	198 (0)	19
16	Василина Татарлиева	3	424	28 (2)	- ()	90 (0)	- (11)	- ()	- ()	- ()	- ()	- ()	226 (2)	18
17	Христо Георгиев	3	466	24 (0)	- (1)	106 (0)	- (10)	- ()	- (2)	- ()	- ()	- ()	295 (2)	18
18	Георги Йорданов	2	116	43 (0)	- (1)	72 (0)	- (8)	- ()	- ()	- ()	- ()	- ()	- ()	11
19	Георги Иванов	2	198	61 (1)	- ()	117 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	3

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

	Name	Solved	Time	A	B	C	D	E	F	G	H	I	J	Att.
1	Атанас Вълев	7	521	15 (0)	58 (0)	20 (0)	41 (1)	154 (3)	- (1)	- ()	83 (0)	- ()	68 (0)	12
2	Румен Христов	6	283	10 (0)	42 (0)	24 (0)	49 (2)	- ()	- (2)	- ()	62 (0)	- (1)	53 (0)	11
3	Веселин Георгиев	6	366	9 (0)	18 (0)	21 (0)	31 (1)	- ()	- ()	- ()	166 (1)	- (3)	77 (0)	11
4	Йордан Чапъров	6	454	14 (0)	30 (0)	35 (0)	41 (0)	- ()	- (4)	- ()	- (1)	254 (0)	77 (0)	11
5	Стефан Иванов	5	466	8 (0)	138 (1)	55 (0)	75 (2)	- ()	- ()	- ()	- ()	- ()	108 (1)	9
6	Енчо Мишинев	5	525	5 (0)	181 (0)	15 (0)	31 (1)	- ()	- ()	- ()	- (1)	- ()	271 (0)	7
7	Герасим Велчев	5	1069	205 (0)	183 (0)	191 (1)	156 (2)	- ()	- ()	- ()	- ()	- ()	272 (0)	8
8	Христиан Христов	4	208	12 (0)	116 (0)	17 (0)	- (2)	- ()	- ()	- ()	- ()	- ()	61 (0)	6
9	Иво Дилов	4	320	11 (0)	146 (0)	42 (0)	100 (1)	- ()	- ()	- ()	- ()	- ()	- (4)	9
10	Димитър Драгостинов	4	337	18 (0)	192 (0)	22 (0)	- (16)	- ()	- ()	- ()	- (2)	- ()	105 (0)	22
11	Валентин Борисов	4	369	5 (0)	112 (0)	92 (0)	- (8)	- ()	- ()	- ()	- ()	- ()	158 (0)	12
12	Даниел Дакев	4	428	28 (0)	134 (5)	50 (0)	75 (2)	- ()	- ()	- ()	- ()	- ()	- ()	11
13	Елица Банкова	4	550	67 (3)	110 (0)	119 (0)	- (2)	- ()	- ()	- ()	- ()	- ()	193 (0)	9
14	Андрей Лалев	3	222	23 (0)	- ()	55 (0)	123 (1)	- ()	- ()	- ()	- ()	- ()	- ()	4
15	Димитър Карев	3	223	63 (0)	- (1)	97 (0)	- (3)	- ()	- ()	- ()	- ()	- ()	41 (1)	8
16	Александър Георгиев	3	283	66 (2)	- ()	35 (0)	- (10)	- ()	- ()	- ()	- ()	- ()	141 (0)	15
17	Иван Ганчев Ганев	3	308	25 (0)	- ()	35 (0)	- (3)	- ()	- ()	- ()	- ()	- ()	227 (1)	7
18	Ванеса Любенова	3	330	46 (1)	- ()	38 (0)	- ()	- ()	- ()	- ()	- ()	- ()	226 (0)	4
19	Иван Камбуров	3	405	28 (4)	- ()	66 (0)	- ()	- ()	- ()	- ()	- ()	- ()	190 (2)	9
20	Владимир Начев	3	444	40 (0)	- ()	68 (0)	- (4)	- ()	- ()	- ()	- ()	- ()	275 (3)	10
21	Мира Росенова	3	554	233 (3)	- ()	40 (0)	- ()	- ()	- ()	- ()	- ()	- ()	220 (0)	6
22	Петър Петров	3	771	199 (10)	- (8)	63 (0)	- ()	- ()	- (1)	- ()	- ()	- ()	289 (1)	23
23	Камен Кънчев	2	33	12 (0)	- ()	20 (0)	- ()	- ()	- ()	- ()	- (1)	- ()	- (1)	4
24	Пламен Комитов	2	45	14 (0)	- ()	30 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	2
25	Илия Божинов	2	75	44 (0)	- (1)	31 (0)	- (2)	- ()	- ()	- ()	- (1)	- ()	- ()	6
26	Симеон Стойков	2	81	34 (0)	- (1)	46 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- (1)	4
27	Илия Манолов	2	86	37 (0)	- (1)	49 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	3
28	Андрей Андреев	2	86	29 (0)	- ()	57 (0)	- (2)	- ()	- ()	- ()	- ()	- ()	- ()	4
29	Пламен Начев	2	113	36 (1)	- (1)	57 (0)	- (6)	- ()	- ()	- ()	- ()	- ()	- ()	10
30	Цветан Ангелов	2	147	35 (0)	- (1)	72 (2)	- (7)	- ()	- ()	- ()	- ()	- ()	- ()	12
31	Иван Димитров	2	147	60 (2)	- ()	47 (0)	- (3)	- ()	- ()	- ()	- ()	- ()	- ()	7
32	Момчил Вилиянов	2	183	114 (1)	- ()	49 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	3
33	Мартин Чиков	2	188	112 (1)	- ()	55 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	3
34	Никола Красимиров	2	190	129 (0)	- ()	61 (0)	- (2)	- ()	- ()	- ()	- ()	- ()	- ()	4
35	Димитър Димитров	2	198	22 (0)	- (1)	95 (4)	- ()	- ()	- ()	- ()	- ()	- ()	- (2)	9
36	Димитър Линов	2	240	111 (0)	- ()	129 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	2
37	Георги Стоянов	2	427	184 (8)	- ()	82 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- (3)	13
38	Зелен Кроки	2	432	252 (0)	- ()	180 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	2
39	Григор Колев	2	487	236 (0)	- ()	251 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	2
40	Илиян Йорданов	2	714	288 (2)	- ()	286 (5)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	9
41	Васил Маринков	1	61	- (1)	- (2)	61 (0)	- (1)	- ()	- ()	- ()	- ()	- ()	- ()	5
42	Миглен Евлогиев	1	77	- (6)	- (4)	57 (1)	- ()	- ()	- ()	- ()	- ()	- ()	- (4)	16
43	Иван Андреев	1	78	- (7)	- ()	78 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	8
44	Георги Синеклиев	1	80	- ()	- ()	80 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	1
45	Илияна Витанова	1	198	- ()	- (2)	198 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	3
46	Васил Сарафов	1	242	- (2)	- ()	242 (0)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	3
47	Димитър Николов	1	287	287 (0)	- (1)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	2
48	Александър Стоянов	0	0	- (3)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	- ()	3
49	Стефан Николов	0	0	- (8)	- (1)	- (1)	- ()	- ()	- ()	- ()	- ()	- ()	- ()	10

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

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

1. Класиране към 55-та минута
2. Класиране към 75-та минута
3. Класиране към 105-та минута
4. Класиране към 155-та минута
5. Класиране към 180-та минута
6. Класиране към 200-тна минута
7. Класиране към 300-тна минута

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

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

Choco

Dean's Cup 2012

Author: Alexander Georgiev
Tags: Trivial, Iteration, Simple Math
Statement | Archive | Online Judge

A.Choco

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

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

Trololo

Dean's Cup 2012

Author: Alexander Georgiev
Tags: Medium, Ad-Hoc, Iteration
Statement | Archive | Online Judge

B.Trololo

Оригинално задачата (тогава именувана EllysPopcounts) беше предвидена и предложена в TopCoder за Div1 250 (SRM 543), но на нейно място беше ползвана малко по-лесна такава.

След осмисляне на задачата можем да забележим, че тя се свежда до това да се преброят единиците в двоичния запис на числата в интервала [A, B]. Този брой, също наричан popcount (population count), е сравнително известен и съществуват различни начини да бъде намерен ефективно за едно цяло число. Някои от по-ефективните алгоритми използват едва няколко операции. Подобна задача имаше и миналата година, но там беше върху рандом числа и трябваше да се използва именно някой от тези алгоритми.

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

Хмм, а възможно ли е да направим алгоритъм за броене на единиците в двоичния запис на число за под една операция на число? Всъщност не.

Ъъ, тогава как да решим задачата?

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

За простота, вместо да мислим такъв алгоритъм за произволен интервал [A, B], ще измислим такъв за [1, N]. Това е често срещан трик, тъй като за да намерим ans([A, B]) е достатъчно да изчислим ans([1, B]) - ans([1, A-1]). Тъй като числото 0 не добавя нищо към отговора, можем да разглеждаме и интервали [0, N], вместо [1, N].

Първо ще разгледаме малко по-простия вариант, в който N е степен на две, минус едно, тоест търсим сумата на попкаунтите на числата в интервала [0, 2^K - 1]. Това е по-лесно, тъй като всички числа са с еднаква дължина в двоичен запис и можем да имаме всяка една комбинация от нули и единици за всеки един бит.

Нека разгледаме първите няколко:

1. [0, 1] = 1
2. [0, 3] = 4
3. [0, 7] = 12
4. [0, 15] = 32
5. [0, 31] = 80

Като цяло, ans([0, 2^K-1]) = K * 2^K-1.

Това, ако се замислим, е логично. В число с K бита, всеки бит може да е или 0, или 1, като е 0 в половината от всички възможности и 1, в останалите. Половината възможности (тоест тези, в които е 1) са 2^K-1. Следователно общият брой единици е K * 2^K-1 (K пъти това число - по веднъж за всеки бит).

Това ни е достатъчно да решим и опростената задача за [0, N], където N е произволно естествено число. Нека представим N в двоичен запис. За пример ще ползваме N = 1337₍₁₀₎ = 10100111001₍₂₎.

В колко от числата най-старшият бит е 1? Логично, в тези от 000000000₍₂₎ до 100111001₍₂₎ или 314 на брой. Тоест толкова на брой, колкото е N без най-старшия си бит плюс едно. При всички предходни е бил 0, като всички предходни са... именно степен на две. Значи можем да прибавим и тях (ползвайки горната формула) към отговора и да не ги мислим повече.

Сега остава да видим какво се случва в числата от 10000000000₍₂₎ до 10100111001₍₂₎, като вече сме преброили най-старшия бит, както и всички числа с по-малък брой двоични цифри. Но след като сме го преброили, то може просто да го игнорираме. Следователно, остава към отговора да прибавим същата подзадача, само че за числата от [000000000₍₂₎, 100111001₍₂₎]. Което, ако забелязвате, е отново задача от същия тип и можем да решим рекурсивно. Базисните случаи са (примерно) число с една единствена двоична цифра.

Това е! Единствено трябва да внимаваме, че макар и входът да не надхвърля 32-битов int, то отговорът би могъл. Следователно трябва да ползваме long long за да сумираме броя битове.

Сложността на това решение е O(log(N)) за да намерим ans([0, N]), тъй като в най-лошия случай трябва да разгледаме всеки от битовете на числото. Тъй като във всеки тест ползваме тази функция точно два пъти: ans([0, B]) - ans([0, A-1]), то сложността на целия алгоритъм за всеки тест е O(log(N)).

EGN

Dean's Cup 2012

Author: Alexander Georgiev
Tags: Trivial, IO
Statement | Archive | Online Judge

C.EGN

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

Snowy Roads

Dean's Cup 2012

Author: Alexander Georgiev
Tags: Easy, Graph, Binary Search, BFS
Statement | Archive | Online Judge

D.SnowyRoads

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

По-дългият, но по-стандартен такъв, е да ползваме двоично търсене по отговора. На всяка негова стъпка строим граф, съдържащ само първите mid ребра (където mid е текущата стойност от двоичното търсене). В този граф ползваме или BFS или DFS за да проверим свързаността. Очевидно това би работело, тъй като ако графът е свързан с mid ребра, то той ще е свързан и с mid+1 ребра. Обратно, ако не е свързан с mid ребра, няма да бъде свързан и с mid-1 ребра. Следователно функцията е монотонна и двоично търсене може да бъде приложено.

Така сложността би била O(log(M)∙(N + M)) на тест. Тъй като и Binary Search и BFS/DFS са доста стандартни алгоритми, предполагам повечето по-неопитни състезатели ще се спрат на това решение.

Забележете, че ако при горното решение не ползваме двоично търсене, а пускаме BFS/DFS след всяка стъпка, то решението ни би Time Limit-нало. С малко наблюдение, обаче, можем да забележим, че всъщност не ни трябва да чистим масива с посетените върхове на всяка стъпка - ако те са били посетени при предходната, то ще бъдат посетени и при текущата! Следователно можем да решим задачата и в O(N + M) на тест с инкрементално пускане на BFS/DFS след всяко добавено ребро. Това решение е не само по-бързо, но и по-кратко, тъй като липсва кода за двоично търсене. За сметка на това трябва да внимаваме да обикаляме само непосетени до сега върхове, а също така дали новодобавеното ребро свързва вече посетени, все още непосетени или един посетен и един непосетен връх.

Всъщност съществува и друг алгоритъм, който е още по-кратък и предполагам повечето от добрите състезатели ще предпочетат. Тъй като ни интересува само кога графът става с една единствена свързана компонента, то можем да ползваме структурата disjoint-set forest за да пазим свързаността на графа. Добавяйки ребро, или не правим нищо (ако двата свързани върха са вече в една компонента), или ги обединяваме в структурата данни. Този алгоритъм също е (съвсем малко по-бавен) от O(N + M).

Achievement Unlocked

Dean's Cup 2012

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

E.Achievements

Първата по-сложна задача в темата беше Achievements (или Achievement Unlocked). Тя беше подвеждаща по няколко причини, но също така частично стандартна, така че не би трябвало да е твърде костелив орех за най-добрите състезатели.

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

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

Първото наблюдение, което трябва да направим, е да видим, че 125,000 минути са ни излишно много. Въпреки че 50 (нива) * 50 (ачийвмънта) * 50 (минути за игра) дава точно толкова, то реално няма да ползваме повече от 50 (ачийвмънта) * 50 (минути за игра). Тъй като 50 минути на игра е максимума, то ще можем да изгираем всяко от нивата с ачийвмънт за толкова време. Започвайки от най-сложните нива ще можем да вземем ачийвмънтите и за по-простите такива безплатно, като така се оказва, че ако Ели има 2500 минути или повече, то тя може (гарантирано) да вземе всичко.

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

Донякъде очевидно е, че спокойно можем да играем нивата в нарастващ ред на сложност. Така гарантирано ще можем да изиграем всяко от тях по максимален брой пъти. Като цяло яко. Това, обаче, не ни помага да избегнем проблема с големия стейт, тъй като трябва да пазим кои от тях са изиграни и по колко пъти, за да можем да изчисляваме отговора правилно.

Да видим какво става, ако играем нивата в намаляващ ред. Изглежда, че е окей, тъй като можем да пазим следния стейт: на кое ниво сме в момента, колко пъти сме изиграли нива с по-голяма сложност и колко време ни остава. Така стейтът може да бъде [50][51][2500], което е сравнително малко откъм памет, а също така дава еднозначен отговор оттук нататък. Всъщност той е и достатъчен за да решим задачата.

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

Без да променяме стейта, ще позволяваме да играем дадено ниво (до броя ачийвмънти в него) дори ако "вече" сме изиграли някакви по-сложни нива. Това е еквивалентно на първоначалната ни идея да играем нивата в нарастваща сложност, като, обаче, правим динамичното в изглеждащо намаляваща. Малко втф момент, което е и сложното (готиното?) нещо в задачата =)

Вътре във всеки стейт трябва да решим колко пъти ще изиграем текущото ниво. Това може да е между 0 и броя ачийвмънти на нивото, включително. Хмм, така, обаче, се появява нов проблем. Какво става, ако до сега сме изиграли 42 нива и решим да изиграем текущото 13 пъти? Така общият брой изиграни нива става 55, тоест > 50, което ни прецаква стейта. С малко мислене виждаме, че това всъщност не е от значение - за по-лесните нива няма значение дали сме изиграли 50 или 55 от по-сложните. Можем да ограничим втория аргумент на динамичното до 50 без да загубим информация.

В тялото на динамичното правим O(Qi) операции, където Qi беше броят ачийвмънти на нивото. Тъй като и то е ограничено до 50, то цялата сложност на алгоритъма ни е O(N∙Qi∙min(M, 2500)) (за таблицата) * O(Qi) (за тялото), или O(N∙Qi2∙min(M, 2500)).

Snow Cleaning

Dean's Cup 2012

Author: Alexander Georgiev
Tags: Hard, Graph, Matching, Eulerian Tour
Statement | Archive | Online Judge

F.SnowCleaning

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

Зад условието на задачата се крие това да намерим Ойлеров цикъл в смесен граф. И докато има лесни алгоритми както за насочен граф, така и за ненасочен такъв, този вариант е значително по-сложен.

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

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

Свързаността можем да проверим лесно, като считаме всяко ребро за двупосочно. Ако имаме недостижим връх, в който влизат или излизат ребра, очевидно няма как да ги обходим и трябва да върнем NO. Забележете, че графът може да е несвързан (по върхове) и все пак да има отговор! Тъй като искаме само да обходим всички ребра, това, че няма да сме минали нито веднъж през даден връх не ни притеснява.

Също очевидно е и това, че трябва и броят инцидентни ребра (сумарно насочени и ненасочени) на всеки връх да е четен, тъй като в противен случай няма как да са по равен брой след насочването на ненасочените. Ако това не е изпълнено, също връщаме NO.

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

Първо, трябва да преброим колко насочени ребра влизат и излизат във всеки от върховете на графа. Това по принцип се нарича степен (degree) на върховете, като отрицателна стойност означава, че повече върхове влизат, отколкото излизат, а положителни - че повече върхове излизат, отколкото влизат (може и обратно, зависи каква нотация предпочетем да използваме). Стойност 0 означава, че броят им е равен (балансиран). Крайната ни цел degree-то на всеки връх да стане 0 след насочване на ненасочените ребра.

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

И все още не е гарантирано, че ще имаме отговор. Сега, обаче, вече знаем за всеки връх колко от инцидентните му ненасочени ребра трябва да насочим като влизащи и колко - като излизащи. Това е само малко неочевидно.

Прост пример: имаме връх с 5 влизащи, 3 излизащи и 6 ненасочени инцидентни ребра. Неговата степен е -2, тоест трябва да ползваме две от ненасочените ребра като "излизащи" за да я направим нула. Обаче остават още 4 ненасочени ребра (гаранитрано е, че оставащият брой ненасочени ще е четен, тъй като по-горе направихме проверка за тази четност). За да запазим степента 0, трябва 2 от тях да са влизащи, а другите две - излизащи. Следователно от 6-те ненасочени ребра ще ни трябват 4 излизащи и 2 влизащи.

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

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

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

Правим следния двуделен граф. От едната страна поставяме всички ненасочени ребра в графа. От другата страна - всички върхове. Свързваме всяко ребро от лявата част с точно два връха от дясната - двата върха, които свързва в оригиналния граф. Ще направим мачинг, като в крайния граф реброто ще "влиза" в мачнатия връх. Добавяме изкуствен връх (source), който има ребро до всеки връх в лявата част (тоест до всяко ненасочено ребро) с капацитет едно - все пак всяко ребро може да бъде насочено към максимум един връх. От десните върхове (сиреч върховете в оригиналния граф) добавяме ребро към друг изкуствен връх (sink) с капацитет броя влизащи ребра, които трябва да бъдат създадени от ненасочените ребра (това, което определихме малко по-горе). Ако съществува perfect matching в създадения граф, то задачата има решение. Нещо повече, в зависимост кой връх от лявата страна (ненасочено ребро) сме свързали в дясната част (връх от оригиналния граф) знаем и как да насочим ребрата за да постигнем Ойлеров граф!

Ако нямаме perfect matching (тоест flow с пропускливост броя ненасочени ребра), печатаме NO. В противен случай имаме решение и печатаме YES.
Единственото, което остана, е да насочим наистина ребрата и да пуснем (сравнително простия) алгоритъм за намиране на Ойлеров цикъл. Правим това, печатаме пътя, и сме готови!

Сложността на задачата се доминира от мачинга. Най-бързият алгоритъм за него е O(N∙M), като в случая N ни е общият брой върхове в двуделния граф (в нашия случай това е броят на върховете + броя ненасочени ребра в оригиналния граф), което е О(N + M). Тъй като всяко ненасочено ребро добавя по две ребра в двуделния граф, то броят ребра там е 2 * M. Следователно сложността на matching-а (flow-a) е O((N + M)∙M), игнорирайки константите. Тъй като N можеше да бъде едва до 100, а M - до 1000, това върви относително бързо. Допълнително можем да приложим редица дребни оптимизации, като например да правим greedy pre-matching, който съкращава работата ни поне на половина.

Bank Robbery

Dean's Cup 2012

Author: Alexander Georgiev
Tags: Hard, Geometry, Probability
Statement | Archive | Online Judge

G.BankRobbery

Макар и геометрична и първоначално замислена като една от най-сложните задачи в темата, няколко неща, които реших да направя за нейното опростяване я правят сравнително лесна (даже е по-скоро medium, отколкото hard).
В нея се изисква да се изчисли вероятността произволна точка във фигура да може да бъде свързана с права линия с всяка точка от контура на фигурата, без да напуска очертанията й. Всъщност, тъй като се пита какъв е шансът пазачът да не вижда Ели, отговорът е 1 минус тази вероятност.

Изискването в задачата, впрочем, звучи като дефиницията за изпъкнал многоъгълник, с тази разлика, че при изпъкнал многоъгълник се изисква всяка точка от вътрешността да е такава. Съответно, ако входната фигура е изпъкнал многоъгълник, то отговорът ще е 1 - 1 = 0 (което беше показано и в единия от примерните тестове).

Как да се справим с неизпъкнали многоъгълници, обаче?

Първото нещо, което трябва да забележим е, че ако има две точки, в които се намира пазачът и вижда цялата стая, то те ще се виждат и една-друга. Нещо повече, всяка точка от линията между тези две точки ще вижда цялата стая, тъй като обратното би довело до противоречие с това, че и двете точки виждат всяка точка от стаята. Принципно имам доказателство за това, но не мисля, че има нужда да усложнявам едиториала с такива работи (I have discovered a truly remarkable proof which this margin is too small to contain). Можете да си го нарисувате и ще видите че е така :)

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

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

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

Ще приложим следния алгоритъм - ще започнем с някаква произволна изпъкнала фигура, която със сигурност съдържа отговора. Да кажем, това е квадратът с долна лява точка (-1, -1) и горна дясна точка (1001, 1001). Всяка от стените на входната фигура ни задава ограничение в коя полуравнина спрямо стената се намира гардът. Следователно, можем да обходим всички стени и да "сечем" досегашната фигура, като оставяме само тази нейна част, която е от правилната страна на стената. Улеснението, което беше дадено тук, е че е казано, че входната фигура е обходена в обратен на часовниковата стрелка ред - така директно знаем кои точки от изпъкналата фигура са в "правилната" полуравнина и кои - не. Остава да имплементираме пресичане на права с отсечка (един лесен начин е чрез binary search, като така избягваме няколко частни случаи). Тоест, за всяка стена от входната фигура:
а) премахваме всички точки от досегашния отговор, които лежат от "грешната" страна на стената
б) потенциално добавяме две нови точки, ако правата пресича досегашната фигура.

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

Сложността на горния алгоритъм е O(N2), където N е броят стени на началната фигура (или броя точки, тъй като двете са едно и също). Моята имплементация ползва 100 итерации за двоичното търсене, което до известна степен забавя бързодействието на алгоритъма, но пресичането може да бъде реализирано с O(1), с което би била постигната тази сложност.

K-th Element

Dean's Cup 2012

Author: Alexander Georgiev
Tags: Medium, Partial Sorting
Statement | Archive | Online Judge

H.KthElement

Това беше една от хитрите задачи в темата. Нейното решение е лесно за имплементиране и сложно за измисляне.

Главният проблем беше огромният вход. Така де. Кайнд ъф. Макар и само 6 числа, можеше да генерира до 20 милиона такива. И макар на spoj0 да няма memory limit (недостатък на системата), то има time limit, който реших да експлоатирам за компенсация (нях нях) :)

Първо да кажем, че съществува особено лесна имплементация, ако познавате стандартната библиотека. Функцията nth_element() върши точно това, което се изисква в задачата. При това го прави бързо (ползва идеята на Merge Sort, но не сортира всички числа). Повече информация как да я ползвате можете да научите тук.

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

Най-най-очевидното решение е да генерираме числата, да ги сортираме и да върнем K-тото по големина. Всъщност, кажи-речи това се искаше в условието. Това, обаче, изисква O(N∙log(N)) време за сортирането и мнооого памет (която, обаче, имаме). Все пак, O(N∙log(N)) на тест води до приблизително 20,000,000 * 25 = 500,000,000 операции на тест. Което е много. Реално зад сортиращия алгоритъм има и константа, която, макар и малка, също влияе забележимо тук. Значи това не става.
Принципно би било окей ако можехме да приложим O(N) сортиращ алгоритъм (който не е базиран на сравнения), като например Counting Sort, но пък входните числа можеха да са до около 1,000,000,000, което правеше това също невъзможно.

Втора идея: Двоично Търсене! Няма проблем да правим повече от един пас над числата. Ако имаме хипотеза какъв е отговорът, то можем да преброим колко числа са стрикто по-малки от него и колко равни на него и така да знаем дали то е K-тото по големина. При това - с константна памет! Найс. Обаче отново биваме спънати от O(N∙log(M)), (където M е максималното число, което може да присъства във входа). Този път имаме 20,000,000 * 30 = 600,000,000. Даже по-зле, макар и тук константата да е по-малка.

Хммм... Then what?
Ще приложим хитро решение, което комбинира (донякъде) идеята от първото и второто. Вече казахме, че не можем да ползваме Counting Sort, който е един от най-разпространените сортиращи алгоритъма, които не са базирани на сравнения (и, съответно, не е обвързан с долната граница от O(N∙logN)). Защо, обаче, не ползваме друг подобен алгоритъм? В случая ще приложим Bucket Sort отново за O(N).

Под "бъкет" ще разбираме клетка от масив, която брои колко числа в даден интервал има. Например, ако входните ни числа бяха в [0, 100), можеше да направим 10 бъкета, отговарящи за, съответно, [0, 9], [10, 19], [20, 29], ..., [90, 99]. Така както 42, така и 47 биха попаднали в един бъкет (и биха увеличи една и съща стойност - стойността на 4-тата (индексирано от нула) клетка в масива). 9 и 13, от друга страна, биха попаднали в различни бъкети (увеличавайки нулевата и първата клетка, съответно).

Първо обхождане
Раделяме възможните числа на sqrt(M) бъкета, всеки с големина sqrt(M) + 1. Така, очевидно, можем да разпределим числа с големина до M в бъкетите. За всеки бъкет единствено броим колко числа са попаднали в него, без да пазим кои са те.

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

Второ обхождане
При второто обхождане ни интересуват само тези от числата, които са попаднали в бъкета, където се намира и отговорът. Вътрешно в този бъкет правим Counting Sort на числата, попадащи в него. Сложността тук отново е O(N), защото не сме запазили кои числа са попаднали в този бъкет - само колко на брой са те. Но дори да ги пазехме по някакъв начин, то е възможно всички входни числа да попаднат в един единствен бъкет, така че няма как да избегнем повторното им обхождане в най-лошия случай.

Вече, обаче, не търсим K-тото число в бъкета, ами K'-тото, където K' = K минус броя на числата, в бъкети по-малки от този на K-тото. Намирането на K'-тото по големина число във въпросния бъкет може да стане с O(sqrt(M)). И сме готови!

Общата сложност на алгоритъма е O(N + sqrt(M)). Сложността по памет пък е едва O(sqrt(M)).

Забележете, че генерирането на числата е относително бавно, тъй като трябва да ползваме long long и имаме mod на всяка стъпка, което е сравнително бавна операция. Дори при само две генерирания на числата е по-добре при първото да ги запишем в масив, като изхабим известно количество памет. Но пък така няма да се налага да ги генерираме втори път и ще си спестим над 30% време! Все пак авторското решение не ползва тази оптимизация за да позволи да минат и "оптимални" по памет и време решения.

Mice

Dean's Cup 2012

Author: Alexander Georgiev
Tags: Hard, Graph, Matrices, Fast Exponentiation
Statement | Archive | Online Judge

I.Mice

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

Първо, очевидно задачата беше графова. Второ, клонирането на мишките и тръгването по всеки път беше много слаб опит за дегизиране на това, че се пита колко пътища има с дължина до K от началния до крайния връх. А алгоритъм за намиране на този брой има.

Добре де, поне има за намиране на броя пътища с дължина точно К. Алгоритъмът е следния: взимаме графа, представен като матрица на инцидентност, чиято стойност в клетка (i, j) е 0, ако нямаме ребро, и 1, ако имаме такова между върховете i и j. Тази матрица вдигаме на степен K, за да намерим колко пътя има с дължина точно К между произволни два върха. След вдигането на степен, клетка (i, j) дава именно броя пътища с дължина точно K от връх i до връх j.

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

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

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

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

Обаче. Ели не пуска мишки и във времена, кратни на 7. Това решаваме точно като горния проблем, само че пътят от началния връх до себе си ще е с дължина 7.

Обаче. Сега пък Ели не пуска по две мишки във времена, кратни на 28 (4 * 7). За да се справим с това пък ще прибавим броя мишки, които биха излезли ако се появяваха по веднъж на всеки 28 секунди.

И вече сме готови. Реално правим включване/изключване със само две числа - 4 и 7. Така де, и 1. Прибавяме 1, вадим 4, вадим 7, и прибавяме 28. Това е така, понеже 1 има само един множител (самото 1), 4 има два множителя (1 и 4), 7 има два множителя (1, 7) и 28 има три множителя (1, 4, 7). Както знаем, при метода на включването и изключването, прибавяме нечетните и вадим четните.

Трик: Вместо да пускаме вдигане на матрица на степен четири пъти - по веднъж за всяка от съпките на включването и изключването - можем да направим малко по-голям граф, чиято матрица да вдигнем на степен само веднъж. Така, макар и правейки матрицата малко по-голяма, реално алгоритъмът върви около два пъти по-бързо (0.75s срещу 1.53s при time limit 2.0s).

Cars

Dean's Cup 2012

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

J.Cars

Като последна задача в темата беше скрита една от лесните задачи. Тя е по-скоро аналитична, отколкото кодерска - идеята ѝ отнема много повече време от имплементацията (подобно на KthElement).

Първото нещо, което трябва да видим, е какво точно се иска от нас. Дадена е пермутация на числата от 0 до N, искаме да направим пермутацията (0, 1, ..., N), като можем да разменяме местата на нулата и произволно друго число.

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

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

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

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

1. Ако нулата участва в цикъла, то просто местим колите една по една, местейки и нулата. В края всяка кола ще си е на мястото, както и нулата ще си е на мястото. За цикъл от този тип ни трябват точно толкова местения, колкото коли има (тоест броят на елементите в цикъла минус едно).
2. Ако нулата не участва в цикъла, то нямаме свободно място и трябва да мръднем една от колите на мястото на нулата (независимо къде се намира тя в момента). След това местим всички останали коли в цикъла. Накрая връщаме колата, която сме преместили в началото, на вече освободеното ѝ крайно място. Така нулата се връща обратно там, където е била в началото. За цикъл от този тип ни трябва 1 месетене в началото + местене на всички коли без тази, която сме преместили в началото + още едно местене на първата. Тоест общо дължината на цикъла + 1.
3. Коли, които вече са си на мястото образуват цикъл с дължина 1, но тях не трябва да броим, тъй като изобщо не се налага да ги местим.

Ии това е. Просто трябва да преброим циклите в пермутацията с дължина по-голяма от 1, да проверим, дали нула присъства във всеки от тях и да прибавим съответния брой операции, които са ни нужни, за да фикснем всеки от тях. Сложността на този алгоритъм е O(N), където N е броят коли.