Състезания и тренировъчни системи

Contests and Training Sites

Едно от нещата, в които най-силно сме се убедили като състезатели е, че не може да станете добри без да тренирате. Многото задачи са единственото нещо, което може да ви направи бързи както в измислянето, така и в имплементацията на алгоритми и структури данни. Също така, опитът ще ви спаси от някои видове често-допускани грешки. Затова тук ще поговорим малко къде и как можете да тренирате самостоятелно (а често това е най-доброто, което можете да направите, особено в по-високи състезателни групи като Б и най-вече А).

Какво представляват състезанията по информатика?

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

Допълнителна тренировка

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

?	Често задачите в тренировъчните сайтове съдържат различни "врътки", които правят решавания проблем по-интересен или по-сложен. Много полезно е да сте виждали тези трикове, преди те да ви се паднат на важно състезание.

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

Как да тренираме сами

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

?

Състезателната информатика се "концентрира" върху дадени популярни теми и много рядко изникват задачи, чието решение разчита на друга теория. Научавайки "популярните" теми вие ще сте подготвени за над 90% от задачите, които могат да ви се паднат. Нещо повече, някои състезания специфично казват кои теми могат да се паднат и кои не. Например IOI дълго време имаше syllabus, който указва каква теория е нужна на състезателите.

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

Стандартна тренировка

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

• Решавайте по-трудни задачи от собственото ви ниво. Ако веднага след прочитането на задачата знаете как да я решите, то най-вероятно тя не би била добра тренировка.
• Тренирайте редовно. Така ще напредвате по-бързо и ще се чувствате във форма. По-добре е да отделяте по 3 часа на ден 3 пъти в седмицата, отколкото 10 часа в един ден.

• ?	Чрез поставяне на срокове ще се научите да мислите как по-бързо да се справяте с даден проблем, а също така ще се опитвате да измисляте по-кратки за имплементация (и все пак верни) идеи.

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

• ?

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

  Не губете твърде много време за да решите дадена задача. Губенето на цял месец да се справите с даден проблем може би не винаги е добра идея. Въпреки че това понякога би ви научило на някоя хубава техника, също така е възможно накрая да се окаже, че сте пропуснали нещо просто, не сте разбрали условието правилно, или нещо друго от този сорт. Погледнете решението (или по-добре: поискайте малък хинт от някой по-добър състезател) след не повече от седмица (сериозни) мъки със задачата.
• Решавайте задачи от теми, в които не се чувствате добри. Няма нужда да тренирате нещо, в което сте добри, ако има такова, в което не сте. Може да сте богът на динамичното оптимиране, но ако не знаете индексни дървета и се падне такава задача, то няма да я решите.
• Ако има обяснение на задачата, задължително го погледнете. Дори да сте успели да я решите, в него може да има предложени различни, по-лесни за имплементиране, по-ефективни, или по-нетрадиционни алгоритми, които да ви свършат работа в бъдеще.
• Дорешавайте! Сблъскали сте се със задача, с която сте се мъчили две седмици и накрая сте погледнали как се решава? Няма проблем! Никой не знае всичко. Изключително важно е, обаче, да я напишете сами от край до край (дори след като сте видели как става тя). Това ще ви помогне да изчистите детайли от идеята, както и ще ви даде увереност, че вече сте я правили, следващия път, когато я срещнете.
• Дорешавайте! Направили сте състезание, в което сте решили някои задачи, но не сте успели други? Явно това са задачите, които ви затрудняват. Седнете на спокойствие и ги решете (дори това да ви отнеме много повече време, отколкото е продължило самото състезание).

• ?	На пролетния турнир през 2003-та година Ивайло Рисков има едва 20 точки, като така става един от последните в състезанието. По-малко от три месеца по-късно успява да стане втори в света.

  Не се предавайте! Всеки от добрите състезатели е минал не през един или два периода на отчаяние. Те са нормални, не може от нищото да станете най-добрите, или пък винаги да сте първи. "Winners never quit. Quitters never win."

Тенировка преди състезание

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

?	TopCoder е изключително подходящо място за такъв вид тренировки.

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

Важно!

Резултатите от тренировките рядко си проличават по време на самата тренировка. Нещо повече, докато тренирате, мозъкът ви се затормозява със задачи и нивото ви може привидно да падне (например да губите рейтинг в TopCoder или да не се представяте добре по състезания). Истинската полза от тренировката започва да се усеща едва няколко седмици след завършването на самата тренировка (тоест след като сте спряли да решавате). Тогава мозъкът ви е усвоил новите неща и се е "изчистил" от остатъчни задачи. Именно за това се препоръчва и да не правите сложни тренировки точно преди важни състезания.

Видове състезания

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

Ученически

Това са индивидуални състезания, предвидени за ученици до 12-ти клас. Те обикновено са с продължителност между 3 и 5 часа, като съдържат 3 или 4 задачи. Често те са разделени на възрастови групи, тъй като в ученическите години най-силно се усеща разликата в опита.

?

Поради наличието на IOI и BOI отбори, които се формират от А група, както и отбор за "малкaтa олимпиадa" JBOI (тоест съответстващото на BOI състезание за ученици до 15 години и половина), които се формират от С група, често състезателите на ниво B група се явяват или в А или в C (когато това е възможно) на по-важните състезания. Тази тенденция има шанс да доведе до премахването на тази възрастова група и разширяването на A и C.

В България разделението е в 5 групи: А (11-12 клас), B (9-10 клас), C (7-8 клас), D (6 клас), и Е (4-5 клас), като обикновено най-сложната задача от дадена възрастова група е с почти същата трудност като най-простата задача от следващата (по-горна) група. Автори на задачи са учители от цяла България, преподаватели в школи и университети, както и състезатели, които вече не са ученици. Най-големите състезания през годината са Есенните (в края на Ноември), Зимните (между края на Януари и началото на Март), Националната Олимпиада (края на Април - началото на Май), и Пролетните (към средата на Юни).

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

Студентски

Обикновено студентските състезания се състоят от повече задачи (8 до 14) за 5 часа, като състезателите участват в отбори от трима души на един компютър.

?	В последно време се наблюдава тенденция за по-слаби изисквания отборите да са от точно трима души. Много състезания (примерно OpenCup и IPSC) разрешават участието на отбори до трима души.

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

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

?	Макар и студентско състезание, често по-добрите ученици участват неофициално в тях за тренировка.

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

?	Често за състезания, където точките се дават за всеки минат тест, а не за цяла задача, се наричат "IOI style", а тези, в които се изисква да бъдат минати всички тестове за да се получат точки - "ACM style".

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

На международно ниво най-елитното студентско състезание е ACM ICPC (International Collegiate Programming Contest), което обикновено е и мястото, където се дават най-бруталните задачи по информатика през годината.

Смесени

Има състезания, които не са предвидени нито само за ученици, нито само за студенти. Те обикновено се организират от частни фирми (като TopCoder, Google, Facebook) и се състоят от редица online квалификации и присъствен финал.

?

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

Те са предимно индивидуални състезания, като съдържат между 3 и 5 задачи със силно-oсезаема разлика в сложността и трябва да бъдат решени за много кратко време (обикновено между 75 и 150 минути, с изключение на финалите, които могат да са до 180-240 минути). По много неща те приличат на студентските състезания (тъй като по-голямата част от участниците се очаква да са студенти или професионалисти), с дребни модификации. Най-основната от тях е, че се получават точки само за изцяло решена задача но без да се разбира дали дадено решение е вярно или не преди края на състезанието.

Финалите на TopCoder Open, Google Code Jam, и Facebook Hacker Cup са може би най-интересните събития в състезателната информатика през годината, тъй като релаксираните им ограничения за участие събират буквално най-добрите състезатели от цял свят и Румен.

Популярни състезания и тренировъчни системи

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

TopCoder

Изключително полезен сайт. Пробвайте го. Ама наистина. Румен предложи да го пиша него и да пропусна останалите. Той ще е основна част от тренировките, които ще ви предложим по-нататък.

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

Теория: Има, писана е от състезатели, покрива всякакви теми. Има и така наречените "Recеpies", които са не задължително алгоритми или структури данни, а по-скоро какво да не правим на състезания, как да избягваме чести грешки, как да подхождаме към определен тип задачи и т.н. Недостатък е, че някои от статиите са много добри, докато други не са (в зависимост кой ги е писал и колко старание е вложил).

Задачи: Има (много), писани са от състезатели. Има различни "нива на сложност", което ги прави добро място за тренировка на състезатели от всякакво ниво (буквално от D до А+ група). Има система, която ви засича време и проверява коректността на решението ви. Почти всички задачи имат описание как се решават (едиториал), както и работещ код.

Състезания: Има, три пъти в месеца. Има две "дивизии" - за начинаещи и за по-напреднали състезатели. Всяка дивизия има по 3 задачи за 75 минути. След приключване на писането на код има специфична "challenge phase", тоест допълнителни 15 минути, в които можете да гледате код на други състезатели и, ако откриете грешки в него, да го съборите с ваш тест. Недостатък е, че някои от състезанията са в неудобно време (примерно 4 сутринта). Друг недостатък е, че понякога състезанията "се омазват" като или системата се чупи, или някоя от задачите е грешна, но това не е много често.

Timus

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

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

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

Състезания: Има две-три в годината (напоследък дори по-рядко).

USACO

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

Теория: Има, добре структурирана и засягаща основните теми в състезателното програмиране. Чудесна е за ученици и като цяло ненапреднали. Недостатък е, че за да стигнете до някоя тема трябва да минете предходните. Темите не покриват всичко, което може да ви се падне на IOI. Част от теорията по-добре да не я учите оттам (примерно динамично оптимиране или потоци).

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

Състезания: Има, веднъж месечно (с изключение на лятото), в IOI стил. Голямо предимство е класирането след всяко състезание, тъй като в него участват голяма част от хората, които бихте срещнали и на IOI и отразява моментната форма на повечето ученици-състезатели. Състезанията са направени така, че да можете да ги правите в удобно за вас време. Има три дивизии - бронзова, сребърна и златна - в зависимост от това на какво ниво сте. Май напоследък (сиреч последните 4-5 години) има и дивизия съвсем за начинаещи?

SPOJ

Една не особено популярна в България, но много използвана в целия останал свят Полска тренировъчна система. Да не се бърка с spoj0, което е системата на Мило (и се ползва за състезания в СУ).

Теория: Няма (или поне не знам да има).

Задачи: Ужасно много, всякакви задачи. Много удачна система, когато сте научили даден алгоритъм или структура данни и искате да ги тренирате върху най-стандартната задача (но с хубави тестове и удачни time limit-и).

Състезания: Има някакви.

COCI

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

Теория: Няма.

Задачи: Има, от стари състезания.

Състезания: Има, като повечето пъти темите са добри.

CodeForces

Руски състезателен сайт, много подобен на TopCoder. Също има рейтинг на базата на проведените състезания.

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

Задачи: Има, от стари състезания (не само от този сайт).

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

HackerRank

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

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

Задачи: Има, много, подредени удобно по тагове и сложност.

Състезания: Има няколко в месеца, от различни типове.

ProjectEuler

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

Теория: Няма, но ще научите много ако искате да решите някои от задачите xD.

Задачи: Има относително много (добавят се нови приблизително през седмица, с изключение на лятото). Почти само математика (както проста, така и много трудна), с редки превалявания на динамично оптимиране. Можете да решавате произволни задачи, така че по-сложните не ви пречат.

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

Тренировъчни системи на Български

Ако търсите къде да се подготвите с теми и задачи на Български език, изборът ви е относително ограничен:

informatika.bg

Разбира се, този сайт и прилежащата му грейдинг система целят точно това :)

Теория: Има, но не всички теми са написани.

Задачи: Има, за момента около 250, от най-различни теми и трудност. Има и групиране в теми (подобно на USACO).

Състезания: Няма (за сега).

arena.maycamp.bg

Може би най-популярната онлайн система за задачи в България.

Теория: Има под формата на видео лекции (не са покрити твърде много теми) и статии, писани от състезатели от ФМИ на Софийски Университет.

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

Състезания: Вече няма.

telerik-kids.com

Академията на Телерик. Насочена е предимно към деца (4-6 клас).

Теория: Има, под формата на присъствени лекции или онлайн материали.

Задачи: Има, доколкото виждам ползват системата BGcoder.

Състезания: Има.

предишна тема

версия за печат

следваща тема