Подготовка

Тук можете да навлезете в света на състезателната информатика като учите и тренирате върху задачи, групирани по теми, в нарастваща сложност. Темите са така подредени, че да изискват само материал, който е покрит в по-предни. Разбира се, очаква се да можете да владеете основи на програмирането (на C++, Java, или Python), което включва как да стартирате програма, вход и изход, типове данни, променливи, масиви, условни оператори, и цикли.

В случай, че сте състезател или подготвяте състезатели, ориентировъчно темите са подходящи за следните групи:

Implementation, Corner Cases, Recursion & Backtrack, Bruteforce, и Sorting са подходящи за ученици от D група и нагоре.
Greedy, Math, Simple Data Structures, Simple Graphs, Binary/Ternary Search, Dynamic Programming, Bucketing са подходящи за ученици от C група и нагоре.
Iterative DP, Sliding Window, Bitmask DP, Game Theory, Advanced Data Structures, Strings, Geometry, и Medium Graphs са подходящи за ученици от B група и нагоре.
Meet-in-the-Middle, Probability, Inner Cycle Optimization, Sweep Line, Advanced DP, и Advanced Graphs са подходящи за ученици от А група.
Various задачите са предимно Ad-hoc или такива, съчетаващи няколко различни теми.

Implementation

Секцията покрива вход и изход от програма, работа с масиви и символни низове. Упражняват се лесни задачи, които изискват директна имплементация на описана процедура.

Corner Cases

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

Recursion & Backtrack

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

Bruteforce

Секцията покрива задачи, които се решават с "груба сила" - обикновено пълно изчерпване или поне изчерпване на част от задачата за опростяване на остатъка от нея, както и генериране на малките отговори за стигане до наблюдение.

Sorting

Секцията покрива темата за сортиране - "бавни" (O(N²)) и "бързи" (O(N * log(N)) сортирания, както и сортирания, които не са базирани на сравнения (например counting sort).

Greedy

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

Math

Секцията покрива относително прости математически похвати, които се срещат често в състезателни задачи. Голяма част от тях се учат в училище и са на ниво 5-6 клас. Покрита е и малко по-сложна математика, която е нужна за алгоритми, които ще разгледаме по-нататък.

Simple Data Structures

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

Simple Graphs

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

Binary & Ternary Search

Секцията покрива най-популярната форма на "Разделяй и Владей": двоично търсене, а както и неговата модификация - троично търсене - което решава проблема с намирането на екстремум на изпъкнала функция.

Dynamic Programming

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

Bucketing

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

Iterative Dynamic Programming

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

Sliding Window

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

Bitmask Dynamic Programming

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

Game Theory

Секцията покрива теория на игрите: какво е оптимална игра, минимакс стратегия, и Sprague-Grundy числа. Ще бъдат разгледани стандартни задачи, както и стандартни задачи с някакви усложнения, като например търсене на цикъл или ползване на динамично оптимиране.

Advanced Data Structures

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

Strings

Секцията покрива работа със символни низове: алгоритъм на Кнут-Морис-Прат, хеширане и хештаблица, префиксен и суфиксен масив, алгоритъм на Ахо-Корасик, както и модифициране на вече разгледани структури данни за стрингове.

Geometry

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

Medium Graphs

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

Meet in the Middle

Секцията покрива едно красиво приложение на техниката "Разделяй и Владей" - така нареченото "срещане в средата" или "meet-in-the-middle". С него можем да намалим на половина степента на някои задачи с експоненциална сложност.

Probability

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

Inner Cycle Optimization

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

Sweep Line

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

Advanced Dynamic Programming

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

Advanced Graphs

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

Various

Секцията покрива задачи, които не са със специфична тематика ("Ad-hoc" задачи) или пък такива, които съчетават няколко различни техники или алгоритми. Тук сме включили и задачи, за които решението е добре скрито и не искаме да ви разваляме удоволствието да го намерите =)

Мрън!