Отборна работа при състезания по програмиране: 3 * 1 = 4

The following text is a translated and addapted excerpt from a 'Crossroads' article. Copyright (C) 1998, ACM. Information used with permission.

Addapted by Flip Flop

Въведение
Всяка година от 1977, ACM (the Association for Computer Machinery) организира международно състезание по програмиране, което се провежда в USA и е едно от най-престижните събития от своя род. Състезанието, което се състои от регионално квалификационно ниво и Финали, предоставя на ученици от целя свят възможност да покажат и усъвършенстват своите знания и умения по програмиране и информатика. По време на състезанието, отбор състоящ се от три състезателя и един компютър, трябва да реши колкото се може повече от зададените задачи в продължение на 5 часа. Отборът с най-много решени задачи е победител, където 'решени задачи' означава програми които генерират правилен изход за набор от (тайни) тестови входни данни. Въпреки че индивидуалните умения на състезателите са много важни, за добро представяне са изключително необходими умения за колективна работа и разпределение на ресурсите в тим. В тази статия, трима от участниците във финалите през 1994, и 1995 г. (Fabian Ernst, Jeroen Moelands, и Seppo Pieterse), описват своите наблюдения от различни състезания и очертават някои общи характеристики на работата в отбор при състезания от подобен род.

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

- Познание на широк спектър от стандартни алгоритми и умение да се прилагат точно необходимите алгоритми за всяка една от дадените задачи;

- Умения за ефективно и качествено реализиране на алгоритми чрез средствата на някои от позволените програмни езици;

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

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

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

2. Задачи за графи. Тези видове задачи имат специфична структура, и за тяхното решение има голямо разнообразие от стандартни алгоритми от теория на графите, които просто трябва да се познават и да бъдат правилно прилагани;

3. Геометрични задачи - задачи, занимаващи се с геометрични форми, прави, ъгли, и др. Общи познания по аналитична геометрия, тригонометрия, и линейна алгебра са от съществено значение при подобен род задачи. В тази категория в редки случаи се дават и задачи, изискващи основни познания по фрактална геометрия;

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

5. Нестандартни задачи.

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

Друг важен елемент които трябва да се практикува е ефективното програмиране. Това не означава да се пише със 120 cps, всеки втори натиснат клавиш да е , и да се изразходват 87/100 от времето в дебъгване и пренаписване. Вместо това, повече време трябва да се отдели на внимателно обмисляне на проблема и всички възможни ситуации, които може да възникнат. Чак след това може да се започне програмирането на проектирания алгоритъм, без да се бърза, и с тенденция програмата да работи правилно от първия път и да се прекарва минимално време в дебъгване. Дебъгването често е сам по себе си объркващ процес и винаги отнема много ценно време.

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

Отборна стратегия: Теорията.

Важно е да се изгради правилна отборна стратегия по няколко причини. Първо, на състезанието има само един компютър, и той трябва да бъде поделян. Второ, задачите трябва да бъдат разпределени някак си. Поради това, съвместното действие, което винаги е в наличие при работата в отбор, е изключително полезно. 'Специализацията' е добър начин това съвместно действие да бъде оползотворено. Ако всеки участник от отбора е експерт в дадена област, той най-вероятно ще даде най-добро решение на проблем от неговата област, и сигурно ще програмира алгоритъма по-бързо от останалите. Специализация е възможна и в друг смисъл. Може би един от участниците е добър програмист, но има не толкова добри аналитични умения, докато друг участник е много добър при избирането и създаването на алгоритми, но му е трудно да пише бързо програми без бъгове. Комбинирането на тези умения води до добри решения на сложни проблеми, без бъгове.

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

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

Други елементи които трябва да се вземат под внимание

Понеже победителите в конкурса се определят по максималния брои решени задачи и (в случаи на равенство) по общото време за изпълнение на програмите. Отборът трябва да изработи стратегия, която максимизира броя на решените задачи в пет часа, и да разгледа общото време за изпълнение на програмите като вторичен фактор, ако е възможно. В много състезания има някои отбори които са в 'топ 6' през първите три часа, а накрая не са дори в 'топ 10'. Обратното също се случва. Така, че е важно отборната стратегия да се възползва максимално от цялото налично време - всичките 15 човекочаса, и 5 компютърни часа. Общото време на изпълнение на програмите не е от толкова голямо значение, и състезателите не бива да се тревожат за времето, което им е отнело решаването на първите две задачи например.

За да се оптимизира малкото време, добра идея е участниците да се опитат да решат напълно всяка задача, която започнат. 99% решена задача не носи никакви точки. Препоръчва се да се отдели малко време в началото да се анализират внимателно всички задачи, за да се избегне харченето на повече време от колкото е абсолютно необходимо при решаването на задачите, както и да се избегне оценяването на лесни задачи като твърде трудни и обратното. Много важно е да се определи правилно точно колко трудна е дадена задача, защото само така може да се подсигури пълното решение на всички започнати задачи и да се изберат точно тези задачи, които могат да бъдат решени за 5 часа.

Понеже участниците никога нямат пълна и перфектна информация, често се налага да поемат рискове. Ако се поеме рискът да се работи едновременно над много задачи например, отборът може да свърши някъде на дъното на класацията със всяка задача 90% решена, но пък може да бъде и победител. От друга страна, ако се поеме рискът да се решат напълно няколко задачи в първите 4:30 часа, а останалото време е твърде малко за да се започне и завърши цяла една задача, то ще се окаже че отборът е прахосал 10% от ценното време.

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

Разбира се, правилното разпределение на използване на терминала е също толкова важно. Въпреки, че повечето програми обикновено са доста малки (рядко повече от 100 реда програмен код), терминалът често е "тясното място": всеки иска да го използва по едно и също време. За да се избегне това е хубаво да се запомни следното: използвайте стола пред терминала само за писане, а не за мислене. Ако се случи така, че някой използва терминала в момента, останалите, ако нямат над какво друго да работят, би трябвало да седнат и да си напишат програмата на хартия, до последната точка и запетайка. По този начин състезателят има много по-добър общ поглед над програмата и може да обмисли всички възможни разклонения и изключения, без някои да му диша до врата, копнеещ да се добере до клавитурата. Щом веднъж програмата е написана на хартия, писането на терминала съвсем не отнема толкова много време, колкото изглежда. Въпреки че трябва да се избягва дебъгване (това Е възможно, ако програмата е внимателно планирана на хартия), когато това се налага, трябва да се върши по същия начин. Съберете колкото е възможно повече данни от програмата, принт-нете ги, и ги анализирайте на хартия, заедно със листинга на програмата. Реал-тиме дебъгинг е най-големият грях, колкото и странно да звучи!

1. Проста Стратегия

Тази стратегия е полезна за начинаещи отбори, както и за тези които не искат (или нямат възможност) да отделят много време за тренировки и fine-tuning на отборната стратегия. Съответно, това не е оптималното решение. Основната идея е да се работи колкото се може по-индивидуално за да се минимизира обмена на всякакви видове (объркващи) идеи. Всеки прочита няколко задачи, избира си някоя която му харесва, и започва да работи над нея. Когато задачата е решена, се избира нова и т.н. Предимство на този подход е, че е необходима само малко практика. Общото отнето време ще е минимално, тъй като най-лесните задачи са решени първи. Има обаче и сериозни недостатъци. Тъй като най-лесните задачи обикновено имат еднакво ниво на трудност, всички участници ще свършат долу-горе по едно и също време. В последствие, терминалът ще си седи неизползван първите два часа (понеже всеки е работил на хартия), и в следващия момент ще има опашка пред клавитурата. Освен това, само лесните задачи ще са решени, защото не е останало време за по-трудните. Като цяло, ако уменията по програмиране на отбора които следва тази тактика са достатъчно добри, те сигурно ще свършат с три или четири решени задачи, и може би ще се класират в Топ 10, но едва ли в Топ 3.

2. Човек зад Терминала!

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

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

3. Think Tank

Стратегията, която авторите на тази статия са избрали при тяхното участие на финалите на АЦМ през 1995, е т.н. Think Tank стратегия. Те вярват, че избирането и анализирането на задачите е толкова важна част в началото на състезанието, че не може да бъде оставена само на един човек. Двамата участници, които са най-добри в анализирането на задачи формират Think Tank и започват да четат задачите. През това време третият участник, които е програмистът, написва набързо някои полезни библиотеки и въвежда (примерните) тестови данни, като внимателно ги проверява. След около 15 минути, Think Tank обсъжда бързо задачите, и избира тази която е най-подходяща за програмиста. След като основната идея е била обяснена на програмиста, той може да започне да работи по задачата. След това Think Tank разглежда останалите задачи и написва основните идеи на алгоритмите на хартия. Авторите са забелязали, че когато двама души работят над дадена трудна задача, често се получават много сполучливи и изобретателни решения. След около един час, Think Tank е добил пълна представа за всички задачи, и обикновено някакъв алгоритъм е намерен за всяка от тях. Следващото решение е колко точно задачи отборът би искал да реши. Най-лесните и кратки задачи се дават на програмиста, докато Think Tank разпределя трудните задачи помежду си.

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

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

Някои други трикове

Може много да тренирате за състезание по програмиране, и стратегията ви може да е много добра. Късметът обаче, винаги има някаква роля в състезанието и трябва да се научите да живеете с това. Не бива да се притеснявате от него (или пък от липсата му). Играйте си собственото състезание. Никога не поглеждайте положението на другите отбори, освен може би да видите дали някои отбор е решил някоя задача, която вие си мислите, че е трудна, неочаквано бързо. Ако журито откаже някоя програма, не се паникьосвайте. Опитайте се да намерите грешката - тя винаги е там някъде. Обърнете внимание на границите на вашата програма, и опитайте да разберете при какви обстоятелства тези граници ще бъдат преодолени. Не е важно да предадете правилно написана програма. Важно е само да дадете програма, която генерира правилен изход за входа, който журито ще даде. Така че програмата ви би трябвало да е ясна и чиста, а не с хиляда вида оптимизации за размер и скорост. Размерът и скоростта са от много малко значение. И винаги помнете, че състезанията по програмиране са голям FUN! ;-)

Заключаващи коментари

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

Повече информация за състезанието на ACM може да намерите на адрес http://www.acm.org/~contest.
Подробен репорт за стратегиите използвани от авторите на финалите през 1994 и 1995 се намира на http://www.cs.vu.nl/~acmteam/.

За авторите

Фабиян Ернст е 26 годишен студент в Техническия университет в Делфт, Холандия. В момента той учи математика с приложение при физиката, и се надява да си вземе PhD-то. Той е бил на ACM финалите през 1995 като част от отбора на ВУ Амстердам. Неговият адрес е ernst@math.tudelft.nl.

Jeroen Moelands е 23 годишен студент по информатика във Vrije университетът в Амстердам, Холандия. Той е участвал във ACM финалите през 1994 и през 1995. Неговият адрес е jeroenm@cs.vu.nl.

Сеппо Пиетерсе е 24 годишен студент по информатика и икономика във Vrije университетът в Амстердам. Той е участвал във ACM финалите през 1994 и 1995, като през 1995 се класира на пето място. Адресът му е spieters@cs.vu.nl.

Статията е преведена и адаптирана от jdimov@acm.org с разрешение от ACM. Прекодирането с букви от българската азбука е дело на nkirov@math.bas.bg.

Всякакъв вид разпространение на този текст с комерсиална цел ще бъде преследвано от правителството на Съединените Американски Щати и ФБР.