ТопКодер

TopCoder

Какво е TopCoder? Състезания и рейтинг. Тренировка и практис руумове. Как да участваме? Какво представлява арената?

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

TopCoder

Въпреки, че е американска компания, в последни години състезанията са насочени главно към останалия свят - особено Европа, Русия и Азия. Администраторите (по-точно хората, които подбират и тестват задачите) в момента са Японец, Беларуснак и Словак, което показва интернационализацията на компанията. Това е една от причините състезанията там да са адски популярни сред хора от целия свят. Друга причина, разбира се, са интересните задачи и забавния (макар и много брутален) формат на самите състезания.

Сайт

Макар и сайтът на самата компания да е www.topcoder.com, реално състезателната част (и единствената, която ви интересува) е www.topcoder.com/tc. Там можете да намерите всичко - от новини, през форум, линк към арената, стари състезания, рейтинг на състезателите, едиториали, туториали и т.н.

Tracks

В TopCoder има няколко основни вида състезания (наричани tracks). Основните два, който ще следите, са Algorithm и Marathon. Те представляват алгоритмични състезания съответно за много кратко време (около два часа) в Algorithm, и за повече време (около две седмици) в Marathon. Освен тях има няколко други трака: Design and Development, Mod Dash, Bug Races и т.н. Те задават проблеми от реалния живот, за които различни фирми плащат на TopCoder да реши. Това е и основният начин TopCoder да печелят пари - от Algorithm и Marathon, макар и далеч по-интересни, те не печелят нищо.

Начин на състезаване

SRM

Най-важното нещо, което трябва да научите за TopCoder, е какво е SRM. SRM е съкращение от Single Round Match - това са (почти) седмичните състезания, които се провеждат на тяхната система. Те ще са и основния начин да тренирате - както на провеждащите се в момента такива, така и на вече минали, стари SRM-и.

Дивизии

Поради богатата си аудитория, нетурнирните състезания (SRM-ите) са разделени в две дивизии (divisions) - първа и втора. В първа дивизия се състезават по-добрите състезатели, докато във втора - по-слабите. Разделянето се прави на базата на TopCoder Rating-а на състезателите, като новите състезатели се слагат автоматично във втора дивизия. Това позволява по-неопитните състезатели също да могат да се изявят. Целта на участниците във втора дивизия е да се представят добре в собствената си дивизия, като така получат рейтинг и заслужат място в елитната първа дивизия. Малко повече за това как рейтингът влияе на разпределението на състезателите по дивизии ще видим малко по-късно.

Задачи

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

Ограничения по време

Ограничението по време за всяка задача е 2 секунди на тест. Сървърите на TopCoder са сравнително бързи и авторските решения винаги вървят за под секунда на Java, така че обикновено ако сте измислили правилното решение, Time Limit-ът няма да е проблем дори ако не прилагате някакви дребни оптимизации - примерно да ползвате масиви вместо вектори.

Ограничения по памет

Ограничението по памет за всяка задача е 64 мегабайта на тест.

Формат (накратко)

Регистрация

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

Room Assignment

Състезателите биват разпределени по "стаи" с между 19 и 25 човека.

Coding Phase

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

Intermission

Между двете "основни" фази на състезанието има 5 минути почивка.

Challenge Phase

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

System Testing

Решенията на участниците биват тествани върху пълния набор от тестове.

Final Standings

Изготвя се крайно класиране за всяка от дивизиите.

Rating Update

На базата на класирането се ъпдейтва рейтингът на състезателите, участвали в мача.

Формат (детайли)

Регистрация

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

Room Assignments

Между края на регистрацията и началото на самото състезание има 5 (в днешно време 15) минутна фаза, в която състезателите биват разпределени по "стаи". Всяка от стаите съдържа между 19 и 25 човека (максимум 20 за SRM, и 25 за турнирни състезания). Разделянето по стаи е направено единствено с идеята да не става мазало по време на Challenge фазата.

Coding Phase

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

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

Всяко състезание се състои от точно три задачи - една сравнително лесна (наричана "easy"), една средно сложна (наричана "medium") и една трудна (наричана "hard"). Обикновено лесната е за (максимум) 250 точки, средната е за 500 и трудната е за 1000, като съответно често ще чуете състезателите да ги наричат спрямо тяхните стандартни точки (примерно "абе, Румене, к'во пишеш на 500?"). Понякога се правят дребни вариации на точките (примерно 550 вместо 500) ако задачите са малко по-лесни или по-трудни от нормалното. Задачите са ограничени и отдолу, като най-често точките, които можете да получите, са в интервалите [75, 250], [150, 500], [300, 1000] (тоест долната граница е 30% от горната).

Малък парадокс е, че на практика е невъзможно да получите 250 точки на задача за 250 точки, освен ако не чийтвате. Тъй като ви е нужно известно време да прочетете и решите задачата, това време ще намали нейната стойност. По принцип средните точки за предаване на задача за 250 точки са между 180 и 220 точки, като бързите състезатели получават 240-245 точки. Това, разбира се, много зависи от самата задача.

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

TopCoder е състезание, в което бързината е особено важно качество. Ако забелязахте, може да сте умни и да измислите и направите 500 за 200 точки (сравнително бавно), а някой друг да направи много по-лесната 250 за 230 точки (сравнително бързо) и така да е пред вас в крайното класиране.

Може би най-бруталното нещо в TopCoder състезанията е това, че задачите се оценяват едва след края на състезанието, като получавате нула точки ако програмата ви не реши дори само един от тестовете. Това е съчетание на ACM и IOI стиловете, като взима сложните неща от двете страни. Като частична компенсация за това, задачите обикновено имат по няколко (4-7) примерни теста, вместо стандартните 1-2.

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

Intermission

Intermission-ът по принцип е предвиден за почивка между coding и challenge фазите. На практика, много от добрите състезатели го ползват за да подготвят тестове за challenge фазата, за да могат по-бързо да свалят решения, съдържащи специфична (предвидима) грешка - примерно overflow или tricky частен случай.

Challenge Phase

В тази фаза състезателите не могат да променят или челънджват собствените си решения.

Тъй като те все още не са тествани на "истинските" тестове, в решенията на състезателите е възможно да има грешки. Вие имате право да съставите тест (отговарящ на ограниченията на задачата) и да "challenge-нете" всяко едно от решенията във вашата стая. Ако решението извади грешен резултат, time limit-не или crash-не, вие получавате 50 допълнителни точки. В противен случай, обаче, вие губите 25 точки.

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

За да имате право да челънджвате, то трябва моментните ви точки да са неотрицателни.

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

System Testing

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

Final Standings

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

Състезания

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

SRM

Стандартно състезанията се провеждат (в момента) по три пъти на месец - веднъж в час, удобен за Азия (и що-годе Европа), веднъж в час, удобен за Европа (и що-годе Азия) и веднъж в час, удобен за САЩ (и неудобен за всички останали). Преди няколко години бяха значително по-чести, като имаше по 5 или 6 състезания на месец, но икономическата криза прекрати този хубав период.

Задачите в Division 1 са с приблизителна сложност {easy = C/B група, medium = B/A група, hard = А+ група}.
Задачите в Division 2 са с приблизителна сложност {easy = D/C група, medium = C/B група, hard = B група}.

TCO

Освен стандартните състезания, веднъж в годината се провежда TopCoder Open (TCO) - "голямото" състезание на фирмата, което е и едно от най-популярните международни състезания по програмиране. След известен брой квалификационни кръгове, най-добрите състезатели се класират на присъствен финал, който се провеждаше в Лас Вегас, а наскоро беше преместен във Флорида.

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

TCHS

TopCoder High-School пък е ученическа версия на TopCoder Open, която почти по нищо не се различава от TCO, освен, разбира се, че е предвидена за ученици. Всяка година по-младите състезатели са поканени да участват в редица квалификационни мачове, кулминирайки в присъствен или (след кризата) онлайн финален кръг.

Задачите на квалификационните кръгове са малко по-лесни от Div2 SRM, като на финалния кръг са малко по-лесни от Div1 SRM.

Рейтинг

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

Рейтинг на състезатели

?Рейтингът в TopCoder до такава степен точно показва колко сте "добри", че бива използван от големи фирми като Facebook и Google като критерии за това кои кандидати да бъдат поканени на интервю за работа.
Поради формулата, по която се определя той, последните няколко (десетина) състезания указват огромно влияние колко е текущият ви рейтинг. Това, ако участвате сравнително редовно, са 3-6 месеца, което е що-годе адекватна апроксимация на моментната ви форма.

Рейтингът е цяло число между 0 и (на теория) +inf, като реалната горна (все още недостигана) граница е около 4000. За простота той е разбит на прагове, всеки от които е асоцииран със съответен цвят.
  • [unrated], бял цвят, Division 2
  • [0, 899], сив цвят, Division 2
  • [900, 1199], зелен цвят, Division 2
  • [1200, 1499], син цвят, Division 1
  • [1500, 2199], жълт цвят, Division 1
  • [2200, 2999], червен цвят, Division 1
  • [3000, 4000+], target, Division 1
Последната граница (target) не е точно цвят - в арената е отбелязан като червен с бял кръг по средата (като мишена). Това е много трудно достижимо и едва няколко човека (около 20 в момента, но до преди няколко години едва 2-3) са такива по едно и също време. Идеята е състезателите да се "целят" да станат толкова добри.

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

Ако забелязахте, Division 2 покрива доста по-малък интервал - едва от 0 до 1199, докато Division 1 от 1200 до близо 4000. Донякъде иронично, всъщност броят участници в Division 2 е с 50-100% повече от тези в Division 1 почти всеки мач. Реално има много повече състезатели със сравнително нисък рейтинг, отколкото high-rated такива.

Рейтинг на държави

?Рейтинга на България като страна (и състезателите в нея) можете да намерите ето тук.
Базирано на рейтинга на участниците от дадена страна се съставя и рейтинг по държави. Учудващо, макар и много малка страна, България се нарежда доста напред. Към края на 2011, началото на 2012-та година страната ни беше на девето място в света. Формулата за рейтинг на държава е такава, че десетте участника с най-висок рейтинг допринасят за 90% от рейтинга на държавата.

Рейтинг на учебни заведения

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

Арена

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

Как да участваме?

Как можем да участваме в състезанията на TopCoder?

Регистрация

Първо трябва да се регистрирате на сайта на TopCoder (линк "Register Now" има горе вдясно). Това ще ви отнеме 5-10 минути.

Регистрация за всяко състезание

Преди всяко състезание трябва да се регистрирате за него и в Арената. Това става много бързо - просто влизате в арената, намирате съответното състезание горе в менютата (Active Contests -> избирате състезанието -> Register). Състезанията биват добавени в Active Contests обикновено 3 часа преди началото - когато започва и самата регистрация.

Арена

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

Влизане в стаята

Задачите могат да бъдат достъпени само от стаята, в която сте били "назначени". За да стигнете до там, минавате през Active Contests -> избирате състезание -> Enter. Ако тренирате, трябва да изберете състезанието от Practice Rooms.

Вътре в стаята

Веднъж влезли в стаята, можете да направите няколко неща. От падащото меню Select One можете да изберете една от трите задачи. От Summary можете да отворите класирането за стаята. От Messages можете да достъпите съобщенията от администраторите. Обикновено те се появяват като попъп прозорец, така че не трябва да следите кога се "появяват" такива - ако има нови съобщения, ще разберете за това :) Също така има информационно поле, в което се показва комуникацията между хората в стаята, извършвани действия и други.
Най-важното нещо, разбира се, е да отворите някоя от задачите.

Задачи

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

Първото е бутонът за компилация. Ако кодът ви не се компилира не можете да го предадете. Така се избягва "compilation error" възможността.

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

Така може да проверите дали той time limit-ва или crash-ва на тяхната система (на съответния тест). Другото полезно е, че проверява теста ви за валидност (дали спазва всички ограничения на задачата) - така, примерно можете да видите, че програмата ви вади грешен отговор, защото тестът е невалиден, а не защото тя самата е грешна. Допълнително, така можете да сте сигурни, че тестът е готов за challenge фазата.

Предаван код и класове

За разлика от повечето други състезания, входът не се чете нито от файлове, нито от конзолата. В случая, вие имплементирате само клас, съдържащ метод с точно определено име, получаващ точно определени аргументи. Чрез тези аргументи се задава входът. Return стойността на метода пък е изходът от програмата. Повече информация за класове можете да намерите в тази статия.

Силно препоръчително е да пробвате поне 1-2 задачки от някой от Practice Room-овете преди първото си състезание. Така няма всичко да е тотално ново и шокиращо по време на и без друго краткото състезание.

Summary

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

Division Summary

Малко по-трудно за достъпване, но по-полезно е общото класиране на всички състезатели в дивизията. Това става през Current Contests -> избирате състезание -> Division Summary. В него можете да видите реално къде се нареждате сред всички състезатели за момента, като това дава по-реална оценка как се представяте за момента, а също така кои задачи са направими/лесни и кои не.

Плъгини

TopCoder разрешава инсталирането на различни плъгини към арената, които правят някои от нещата по-лесни. Прост пример е генерирането на "boilerplate" кода за всяка задача - след като е зададено точно как трябва да се казва класът, който пишете, както и точно как да се казва метода, който трябва да имплементирате, а също така и какви да са неговите аргументи, то защо да го пишете вие? Това няма никаква алгоритмична стойност и всеки може да го напише - следователно плъгините могат да създадат автоматично този код, от една страна спестявайки ви писането на глупости, от друга, намаляйки времето за имплементиране на задачите.

Друг пример за полезен плъгин е такъв, който "вкарва" всички тестове от задачата в кода ви и така ги прави лесни за тестване с едно единствено стартиране на програмата ви (в много IDE-та - с натискане на едно единствено копче).

Налични плъгини

Има различни плъгини, които вършат различни неща. Някои от тях можете да намерите ето тук, тук, и тук. Последните два плъгина добавят примерните тестове от условието на задачата, изпълнявайки решението ви върху тях. Също така сравнява отговорите по начина, по който TopCoder ги сравняват, и допълнително засича времето за изпълнение. Fushar's TesterDream добавя и колко точки ще имате, ако предадете в момента на изпълнението на тестовете. Допълнително, което е може би и най-големият плюс, е че всеки тест се изпълнява в отделен процес (което премахва нуждата да инициализирате глобалните променливи).

Кои плъгини да инсталирате и как точно да ги настроите зависи от много неща - например езика, на който пишете, операционната система, редактора, а както и лични предпочитания. Разгледайте ги и инсталирайте тези от тях, които ви се струва, че ще са ви най-полезни на вас.

Примерна инсталация

Като пример как се инсталират и ползват, тук съм описал начина, по който ги ползвам аз. Той е сравнително непретенциозен откъм това каква операционна система ползвате или кой редактор (с изключение на Visual Studio).
Ще инсталираме три плъгина:
  1. TesterDream: за бързо изпълнение върху примерите, а както и добавяне на собствени тестове;
  2. PopsEdit: за създаване на първоначалния код - класа и метода, които трябва да имплементирате, както и допълнителен код, който вие задавате и искате да присъства (най-често хедъри и макроси);
  3. CodeProcessor2.0: осъществява взаимодействието между арената и плъгините.
Следват детайлни инструкции за инсталация:
  1. Изтеглете трите плъгина (.jar) и ги сложете в някаква директория (примерно /topcoder/plugins): TesterDream, CodeProcessor, и PopsEdit;
  2. Логнете се в Arena-та (mirror). Цъкнете Options->Editor.
  3. Цъкате Add.
    • Name: CodeProcessor2.0
    • EntryPoint: codeprocessor.EntryPoint
    • Class Path: (браузвате CodeProcessor.jar, PopsEdit.jar, TesterDream.jar)
    Пътищата до файловете в последното поле ще се разделят с ';'.
  4. Цъкате Save и чеквате Default и At Startup на реда, който току-що добавихте. Ако някой от другите редове има чекнато някое от тези ги махнете оттам.
  5. Селектвате новодобавения ред и му давате Configure. Горе в EntryPoint трябва да е popsedit.EntryPoint. В ProcessorClass добавете fushar.TesterDream
  6. Натискате Verify. Трябва да ви изпише на първия ред нещо за TesterDream, след което 3 неща found.
  7. Цъкате Cofigure на PopsEdit. Излиза меню с много неща, като най-важното от тях е табът Code Template. Отваряте го, селектвате езика, на който пишете, и пльосвате това. Форматирате по ваш вкус, без да променяте нещата, оградени с доларчета.
  8. Давате Save и затваряте, докато стигнете до главното меню на арената.
  9. Затваряте арената и я стартирате наново. Вече трябва плъгините да са активни. Пробвайте в произволен Practice Room!
Това, което тези настройки правят, е да създават основните неща от кода, който трябва да напишете. Допълнително създава main() функция, която стартира кода ви на примерните тестове.

Как работи всичко това? Когато отворите задача, в полето за код вече ще има написан част от него. Копирайте го в редактора, който ползвате по принцип (примерно Code Blocks или DevC++). Допишете решението си. Стартирайте програмата - тя ще се рънне автоматично на тестовете.

След като сте готови с имплементацията, все пак трябва да я предадете. Жизненоважно е да не копирате целия код обратно в арената - копирайте само класа и библиотеките (това е от коментара //Copy everything above this нагоре). Изчистете досегашния код от полето в арената и пейстнете копирания. Компилирайте. Ако се компилира успешно можете директно да предавате (без да пускате тестовете един по един). За допълнителна сигурност може да пуснете най-големия от тях - понякога, макар и много рядко, се случва при вас да върви, а при тях - не. Примери кога може да стане това е ако излизате извън масив (което на C++ понякога не се хваща под Windows), или пък ползвате твърде много памет.

Practice Rooms

Practice Rooms са, накратко, стари състезания. В тях можете да отваряте задачите колкото си пъти искате, да ги предавате колкото си пъти искате и да пускате System Testing по колкото си пъти искате. Също така в тях можете да гледате кода на другите състезатели, а дори и да ги челънджвате. Като цяло, това е перфектното място за тренировка. Там не сте притиснати от време, не ви пука за точки (тъй като те не влияят на рейтина), а също така можете да научите много от по-добрите състезатели. В техните решения често можете да намерите хитри трикове или кратки имплементации, които да ви помогнат за вбъдеще.

За разлика от стандартните състезания, тук има няколко допълнителни опции. В менюто горе, при тренировъчните състезания (Practice Rooms) има допълнително поле - Practice Options. От него можете "изчистите" кода и точките си на всички задачи (за стаята) с избиране на Clear All Problems, както и на специфични такива чрез Clear Problem(s).

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

Третата опция в Practice Options е Run System Test, която пък проверява верността на задачата ви на базата на истинските тестове, а както и тестовете, добавени по време на challenge фазата. Нещо повече, ако задачата ви е грешна или бавна, системата ви връща точно на кой тест става това. Така лесно можете да си дебъгнете задачата (поне по-лесно, отколкото в системи от типа на Timus).

Разбира се, най-добрият начин за тренировка е първо да направите всички задачи, да пуснете System Testing-а и чак тогава да оправяте проблемите по тях. Така тренировката ви ще е по-близо до истинско състезание, което, очевидно, е плюс. Вижте примерните тренировки (1 и 2) за повече информация как да тренирате.

Editorials

Повечето от проведените състезания имат "едиториал" - тоест кратко резюме на състезанието, както и решение на всяка от задачите. Обикновено едиториалите са много полезни, особено за задачи, които не можете да решите. В тях често има трикове, които не знаете, или идеи, за които не сте се сетили. Те са нещото, от което съм научил най-много неща.
Editorial-ите се помещават в секцията Algorithm Problem Set Analysis.

Tutorials

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

Forums

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

TopCoder Cookbook

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

TopCoder съвети

Регистрация за състезание

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

Отваряне на задачи

Често най-добрата стратегия е да отваряте задачите в реда на тяхната трудност (easy-medium-hard). Някои от най-добрите състезатели ползват други стратегии (например easy-hard-medium или hard-medium-easy), но това не е препоръчително за неопитни хора.

Зарязване на гадни задачи

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

Ако попаднете на задача, която дори след 15-20 минути нямате ясна идея как да решите, ви съветваме да отворите някоя от другите задачи. Около веднъж на няколко състезания се случва medium да ви е по-лесна от easy или пък hard да ви е по-лесна от medium. Отново - това може да не е заради сложността на самите задачи, а заради задачите, които вие сте виждали и решавали преди. Ако не знаете как се решава и по-сложната задача, винаги може да се върнете и продължите да мислите по по-простата такава.

Division Summary

Хвърляйте по един поглед на Division Summary-то през 10-20 минути, а също така след предаване на задача. От него можете да намерите важна информация, като, например, че някоя задача е по-лесна, отколкото е оценена. Например много предавания по 500 и не чак толкова, или за сравнително ниски точки на червените състезатели по 250 могат да ви подскажат, че може би си заслужава да зарежете 250 (ако още не сте я направили) и да пробвате 500.

Преписване на кодове

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

Отваряте произволно решение, което мислите, че може да падне. Това обикновено са решенията, предадени от хората с най-нисък рейтинг в стаята или решения, предадени съвсем в края на coding phase-а. Предпочита се да изберете задача, за която имате хитър тест и отговор за него, или задача, за която има решение, което може би ще time limit-не.

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

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

Ако върви за над X секунди на някой от тестовете (независимо дали вашите или тези от задачата), то може да челънджвате за Time Limit. За това не е нужно да имате правилния отговор за съответния тест - big random би свършил работа. Тук е добре да знаете що-годе колко бърз е вашият компютър спрямо тези на TopCoder. След определен брой решени, или по-скоро нерешени задачи ще можете да определяте това. Примерно на моят компютър решение, което върви за над секунда, най-вероятно ще Time Limit-не на TopCoder-ските сървъри. На стария ми компютър пък, ако върви за под 3-4 секунди то най-вероятно няма да Time Limit-не. Изцяло зависи от отношението на вашата машина към тези на TopCoder.

Ако пък решението крашне на някой от вашите тестове (и, отново, минава примерните), погледнете защо точно може да крашва. Малки масиви? Прекалено дълбока рекурсия? Макар и това да не е много по-различно от нормалния начин за челънджване, поне имате насока за какво да търсите грешка. Забележете, че излизане извън масива с едва няколко елемента често крашва при вас, но не и на сървърите на TopCoder. Не челънджвайте такива решения на C++.

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

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

Допълнителни материали

  1. Основна страница за състезания
  2. Форум на TopCoder
  3. Информация и правила за участие
  4. TopCoder Editorials
  5. TopCoder Tutorials
Страницата е посетена 2932 пъти.