Състезания и тренировъчни системи
Contests and Training Sites
Какво представляват състезанията по информатика?
Как да тренираме сами? Какво е тренировъчна система?
Популярни състезания и тренировъчни системи.
Как да тренираме сами? Какво е тренировъчна система?
Популярни състезания и тренировъчни системи.
Едно от нещата, в които най-силно сме се убедили като състезатели е, че не може да станете добри без да тренирате. Многото задачи са единственото нещо, което може да ви направи бързи както в измислянето, така и в имплементацията на алгоритми и структури данни. Също така, опитът ще ви спаси от някои видове често-допускани грешки. Затова тук ще поговорим малко къде и как можете да тренирате самостоятелно (а често това е най-доброто, което можете да направите, особено в по-високи състезателни групи като Б и най-вече А).
Какво представляват състезанията по информатика?
Както при повечето спортове, то и при състезателната информатика основният начин за определяне "кой е по-по-най" е чрез състезания (уау, какво прозрение). В тях се фиксира време, през което участниците могат да прочетат, решат и предадат задачите, като обикновено (при ученическите състезания) времето е между 3 и 5 часа, през които трябва да бъдат решени 3 или 4 задачи. В почти всички видове състезания задачите са с различна трудност, което помага за по-добро "разслояване" на състезателите (тоест води до по-добро класиране). Повече за формата на състезанията ще поговорим малко по-късно.Допълнителна тренировка
Някои от вас може би имат късмета да имат учител, който да ги наставлява или школа, която да посещават. Това е страхотно начало ако искате да станете състезател, но помага само "до едно време". Ако искате да бъдете най-добрите, ще трябва да се занимавате много повече, отколкото време и сили могат да отделят преподавателите ви. А и (без да искаме да обидим учителите) съществуват неща, на които те просто не могат да ви научат.? | Често задачите в тренировъчните сайтове съдържат различни "врътки", които правят решавания проблем по-интересен или по-сложен. Много полезно е да сте виждали тези трикове, преди те да ви се паднат на важно състезание. |
Как да тренираме сами
Стандартната тренировка (която практикуват мнозинството от състезателите) се състои от два редуващи се етапа: научаване на нова теория и решаване на задачи, свързана с нея.? | Състезателната информатика се "концентрира" върху дадени популярни теми и много рядко изникват задачи, чието решение разчита на друга теория. Научавайки "популярните" теми вие ще сте подготвени за над 90% от задачите, които могат да ви се паднат. Нещо повече, някои състезания специфично казват кои теми могат да се паднат и кои не. Например IOI дълго време имаше syllabus, който указва каква теория е нужна на състезателите. |
Стандартна тренировка
Няколко полезни съвета как да тренирате:- Решавайте по-трудни задачи от собственото ви ниво. Ако веднага след прочитането на задачата знаете как да я решите, то най-вероятно тя не би била добра тренировка.
- Тренирайте редовно. Така ще напредвате по-бързо и ще се чувствате във форма. По-добре е да отделяте по 3 часа на ден 3 пъти в седмицата, отколкото 10 часа в един ден.
Поставяйте си разумни срокове, в които да решите задачата, с която се захващате. Всички състезания протичат в определен период от време, който в общия случай е сравнително кратък (обикновено между 75 и 300 минути). Дори да можете да решите всяка задача от дадено състезание, ако го правите по-бавно от самото състезание, то няма да постигнете големи успехи.? Чрез поставяне на срокове ще се научите да мислите как по-бързо да се справяте с даден проблем, а също така ще се опитвате да измисляте по-кратки за имплементация (и все пак верни) идеи.
Не губете твърде много време за да решите дадена задача. Губенето на цял месец да се справите с даден проблем може би не винаги е добра идея. Въпреки че това понякога би ви научило на някоя хубава техника, също така е възможно накрая да се окаже, че сте пропуснали нещо просто, не сте разбрали условието правилно, или нещо друго от този сорт. Погледнете решението (или по-добре: поискайте малък хинт от някой по-добър състезател) след не повече от седмица (сериозни) мъки със задачата.? Определянето на това колко време да си оставите преди да погледнете решението на дадена задача е много трудно. Някои задачи просто са трудни и изискват време (повече от няколко часа, ако ги пишете за първи път). В други, просто не уцелвате правилния подход в началото, задълбавайки в грешна посока, която би решила по твърде сложен (ако изобщо) начин задачата. - Решавайте задачи от теми, в които не се чувствате добри. Няма нужда да тренирате нещо, в което сте добри, ако има такова, в което не сте. Може да сте богът на динамичното оптимиране, но ако не знаете индексни дървета и се падне такава задача, то няма да я решите.
- Ако има обяснение на задачата, задължително го погледнете. Дори да сте успели да я решите, в него може да има предложени различни, по-лесни за имплементиране, по-ефективни, или по-нетрадиционни алгоритми, които да ви свършат работа в бъдеще.
- Дорешавайте! Сблъскали сте се със задача, с която сте се мъчили две седмици и накрая сте погледнали как се решава? Няма проблем! Никой не знае всичко. Изключително важно е, обаче, да я напишете сами от край до край (дори след като сте видели как става тя). Това ще ви помогне да изчистите детайли от идеята, както и ще ви даде увереност, че вече сте я правили, следващия път, когато я срещнете.
- Дорешавайте! Направили сте състезание, в което сте решили някои задачи, но не сте успели други? Явно това са задачите, които ви затрудняват. Седнете на спокойствие и ги решете (дори това да ви отнеме много повече време, отколкото е продължило самото състезание).
Не се предавайте! Всеки от добрите състезатели е минал не през един или два периода на отчаяние. Те са нормални, не може от нищото да станете най-добрите, или пък винаги да сте първи. "Winners never quit. Quitters never win."? На пролетния турнир през 2003-та година Ивайло Рисков има едва 20 точки, като така става един от последните в състезанието. По-малко от три месеца по-късно успява да стане втори в света.
Тенировка преди състезание
Освен горния вид трениране "за научаване на нови неща" има и друг вид, който пък помага за "влизане във форма". При него се решават по-прости задачи, но при по-екстремни условия (повече задачи, по-малко време).? | 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 квалификации и присъствен финал.? | Форматът на тези състезания е изключително тежък, но в същото време много интересен (забавен, зарибяващ?). От една страна бинарният резултат "вярно/невярно" и липсата на информация преди края на състезанието стимулира много внимателно писане код и тестване. От друга, кратката продължителност на състезанието, заедно с класирането по време, подтикват към възможно най-бързо предаване на решенията. Това води до чести грешки дори при много добри състезатели. |
Финалите на 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.
Състезания: Има.
За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 11705 пъти.