Елена Андреева

Советы участникам соревнований :-)

1. Состав команды

Для слаженной работы команды во время олимпиады по программированию и достижения максимально возможного результата рекомендуется формировать команду в следующем составе:

а) "Диктатор", он же капитан команды, он же генератор идей, по темпераменту - желательно сангвиник или флегматик. Решения, принимаемые капитаном во время тура, не подлежат обсуждению и выполняются немедленно. Хорошо также, если "диктатор" будет полностью осведомлен о круге задач, который близок по духу тому или иному члену команды, об их интеллектуальных способностях и скорости машинописи на языке Computer English.

Здесь и далее по тексту под термином "член команды" подразумеваются все три участника, включая самого капитана.

Сгенерировав ту или иную идею, "диктатор" отдает ее на доработку наиболее подходящему для достижения этой цели "члену команды".

б) "Реализатор", он же секретарь-машинистка, он же гениальный мгновенный воплотитель своих и чужих идей, холерик по темпераменту. Главная его задача - не подпускать во время тура других членов команды к клавиатуре компьютера. Неплохо, если "реализатор" сможет сразу и без посторонней помощи запрограммировать самую легкую задачу, предоставив тем самым своим товарищам время подумать над остальными задачами. Хороший "реализатор" способен с полуслова стенографировать в терминах известного ему языка программирования бредовые идеи остальных членов команды, попутно доводя эти идеи до ума.

в) "Сомневающийся", он же главный "тестер" (не путать с тостером), лучше, если он же является главным математиком команды, по темпераметру - меланхолик. Его предназначение - внимательно изучать условие задачи, которая в данныый момент набивается и/или отлаживается "реализатором", и придумывать исчерпывающий набор тестов, на котором созданную программу необходимо проверить. Желательно, чтобы система тестов содержала все вырожденные и критические случаи, а также, чтобы ответы на предложеные тесты были "сомневающемуся" несомненно известны. Главная линия поведения "тестера" - все время сомневаться в правильности программы, созданной совместными усилиями команды, и желанть эту программу на чем нибудь "подловить". Если ему это ни разу не удастся, то можно начать сильно сомневаться в качестве самого тестера, и, следовательно, программа будет "поймана" жюри, что ведет в к негативным последствиям, а именно - к увеличению штрафного времени даже при окончательном благоприятном исходе для данной программы. На совести "сомневающегося" - также контроль педантичности следования "реализатора" формату входных и выходных данных, поскольку за "реализаторами" данное качество замечается весьма редко, да еще въедливые вопросы для жюри по поводу различных нюансов в формулировках задач (в понимании условий всегда лучше переесть, чем недоспать).

Примечание. Если к моменту изучения данного руководства команда уже была неосмотрительно сформирована и исправлять что-либо в составе участников поздно, то, в случае равномерного распределения перечисленных выше качеств среди членов команды, они могут во время тура изменять свои роли путем циклического сдвига во время перехода от решения одной задачи к другой. Например, "реализатор" отлаживает первую задачу, "диктатор" думает над второй, "сомневающийся" пишет тесты для первой, а после успешной сдачи первой задачи, бывший "диктатор" воплощает свои мысли по второй задаче на компьютере, бывший "сомневающийся" думает над третьей задачей, а освободившийся "реализатор" становится тестером по задаче номер два.

2. Подготовка к соревнованиям

Желательно, чтобы подготовка к соревнованиям проходила в течение как минимум двух-трех лет, предшествующих олимпиаде, причем без существенных перерывов, в том числе и на обед, так как спортивная форма имеет обыкновение утрачиваться. Хорошую форму позволяет поддерживать участие во Всероссийских и Международных личных и командых состязаниях для школьников и студентов по информатике, сетевых олимпиадах, межвузовских и внутривузовских командных соревнованиях по программированию. Последние можно проводить практически еженедельно (недельный перерыв между соревнованиями необходим для того, чтобы наиболее сознательные участники смогли наконец-то решить задачи, предлагавшиеся на предыдущей олимпиаде). Кроме того, чтобы необходимые для решения задач на олимпиаде алгоритмы не стали откровением во время тура, члены команды все вместе или каждый по отдельности должны знать курс высшей математики (включая линейную и не только алгебру, математический анализ, теорию вероятностей, аналитическую и неаналитическую геометрию и т.д. и т.п.), булевскую алгебру, теорию графов, курс численных методов, методы решения задач оптимального управления и исследования операций.

Неплохо также ознакомиться с теорией построения трансляторов, компьютерной геометрией, алгоритмами сортировки и поиска, классом NP-полных задач, программированием различных комбинаторных конфигураций, методом backtracking, методом ветвей и границ, динамическим программирование, а также решить проблему распознавания образов путем написания программы для собственного сканера. Логическим завершеним теоретической подготовки к соревнованиям является составление программы для игры комьпютера в преферанс с одним или двумя пользователями или какой-либо другой более сложной с точки зрения разрабоки компьютерной стратегии игры, диcассемблирование и изучение компилятора с любимого языка программирования, а также просто игра в MINESWEEPER, но не в DOOM.

Если же названия большинства упомянутых выше алгоритмов и теорий вы слышите впервые, то ни в коем случае не следует отчаиваться и пытаться ознакомиться с ними в срочном порядке в оставшиеся до соревнований часы, особенно отрывая их от сна. Что именно может пригодиться на конкретной олимпиаде - предсказать достаточно сложно, и здоровье может быть подорвано понапрасну. Кроме того, большинство предлагаемых на такого рода соревнованиях задач предполагают лишь наличие у участников здравого смысла, сообразительности и некоторой математической и программистской культуры, последняя же является результататом большого опыта работы, и привить ее за несколько дней до тура невозможно. С другой же стороны, знание огромного количества различных алгоритмов и приемов программирования часто может оказать медвежью услугу участникам, направляя их мысли лишь на проторенные пути, в то время когда истина в олимпиадной задаче может лежать и в стороне от известных дорог.

Если же во время подготовки к соревнованиям у вашей команды возникло ощущение всемогущества или мания величия, то ни в коем случае не следует заранее обсуждать, как лучше распорядиться будущими призами. Практика показывает, что в этом случае призы достанутся вашим соперникам.

3. Стратегия и тактика повединия во время тура

Цель: создать у жюри иллюзию о решении вами как можно большего количества задач путем подгона программ под заданную систему тестов.

Средства: в достижении указанной цели все средства хороши.

1) При внимательном рассмотрении текстов "правильных" программ, решающих олимпиадные задачи, несложно убедиться, что в них довольно много общего. Поэтому, в самом начале тура "рeализатор" должен набить следующую универсальную программу, особое внимание обратив на директивы компилятора (текст программы приведен на языке TURBO-PASCAL, если вы программируете на C++, то переведите его на ваш "иностранный язык" заранее, записав дословный перевод на листе бумаги):

{$A+,B-,D+,E+,F+,G-,I+,L+,N+,O-,R+,S+,V+,X+}
{$M 65520,0,655360}
var i, j, k: integer;
procedure readdata;
var f: text;
    a: longint;
begin
  assign (f,'INPUT.TXT');
  reset (f);
  while not seekeof (f) do read (f, a);
  close (f)
end;
procedure outdata;
var g:text;
begin
  assign (g, 'OUTPUT.TXT');
  rewrite (g);
  close (g);
end;
procedure initial;
begin
end;
procedure run;
begin
end;
BEGIN
   readdata;
   initial;
   run;
   outdata;
END.

Обратите внимание, что программа получилась работающая. То есть ее можно запускать на выполнение, и при наличии в текущей директории файла INPUT.TXT (даже пустого) все должно быть в порядке. Далее необходимо скопировать эту программу столько раз, сколько задач вам предлагается на туре, называя каждый полученный файл так, как это требуется по условиям соревнований. Ну вот, теперь у вас все задачи уже решены, хотя и в первом приближении. Теперь дело за малым - постараться не испортить эти работающие программы в процессе добавления к ним новых кусков. Ведь лучшее - враг хорошего!

2) Пока "реализатор" занимается "решением" всех задач одновременно, остальные члены команды знакомятся с текстами предложенных задач и "диктатор" должен принять решение - какая задача будет программироваться первой, какая второй и кто именно этим будет заниматься. Выкрики остальных членов команды: "Я, я, я знаю как решается эта задача, да я ее за пять, две или даже одну минуту решу", должны приниматься только к сведению, а не как руководство к немедленному действию. В большинстве случаев первой должна программироваться задача, для решения которой требуется написать самую маленькую программу, и, следовательно, ошибок в которой должно быть меньше. Во вторую очередь следует заняться разработкой текста программы для очевидной и легкой (на первый взгляд) задачи, программирование которой заключается во внимательном учете всех возможных случаев, и требует некоторой техники реализации пришедших в голову идей.

3) Если вы приступили к решению задачи (сразу на компьютере или без него), внимательно прочитайте ее условие и постарайтесь правильно (!!!) понять, в чем заключается задача. Если есть хоть капля сомнения, в том числе и по форме ввода-вывода, то лучше немедленно задать вопрос жюри, а не членам своей или соседней команды. Член команды, который в данный момент не допущен до клавиатуры "диктатором", должен обязательно записывать текст программы для решаемой задачи на бумаге (столе, стуле, ладони и т.п.), даже если в голове у него уже есть готовые конструкции будущей программы. Во-первых, если вылить содержимое вашей головы на бумагу, то путем пристального взгляда вам наверняка удасться его улучшить (все улучшения также должны быть произведены в письменном виде), а, во-вторых, набивать текст программы, какой бы ясной для вас она не была, в 1,5 - 3 раза быстрее с бумаги, чем из головы.

4) Рекомендации по процессу практического программирования олимпиадной задачи:

а) завершить программирование процедуры readdata ввода данных, согласно требованиям решаемой задачи;

б) в процедуре initial следует обнулить или присвоить соответствующие начальные значения всем (!!!) глобальным переменным;

в) сделать вывод результата в процедуре outdata так, как это требуется в условии задачи, это поможет дальнейшей отладке программы и не потребуется потом "простой" вывод переделывать в "правильный" (в процессе отладки имя выходного файла можно заменить на CON, тогда не придется каждый раз открывать выходной файл для просмотра результатов работы программы); в результате вы будете иметь все еще "работающюю" программу, она по-крайней мере должна компилироваться, считывать данные и выводить результат, пусть и нулевой;

г) запрограммируйте решение задачи в виде вызовов процедур и функций, которые пока следует описать в виде заглушек (мнимого или пустого действия или имитации настоящего действия, которое должна выполнять ваша программа); так вы можете отладить логику вашей программы, оставляя ее "работающей".

д) затем следует по-одной набивать и отлаживать описанные процедуры и функции, добиваясь, чтобы свое действие каждая из них выполняла правильно в любом случае, например, поиск максимумов, соритировка массивов, комбинаторные подпрограммы и т.п.; особое внимание следует уделять программированию вырожденных случаев, так, если у вас в программе встречается деление, то сразу подумайте, не делитете ли вы на ноль и обойдите это; при программировании циклов старайтесь, чтобы зацикливание не происходило ни при каких начальных данных;

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

5) И вот, наконец, "реализатор" завершил свою работу по программированию очередной задачи (вернее думает, что завершил). Теперь главным действующим лицом становится "сомневающийся", который к этому своему звездному часу (или минуте) уже должен подготовить исчерпывающую систему тестов, которая и позволит "сомневающемуся" показать некомпетентность "реализатора". Если же данная система тестов не поставила "реализатора" в тупик и позволила ему быстро устранить все мелкие ошибки в решении задачи, то, прежде чем окончательно cоздавать exe-файл, замените следующие директивы компилятора: D-,I-,L-,R- и скорректируйте размер стека. Постарайтесь запустить полученный *.exe файл из DOS хотя бы для одного теста, чтобы убедиться в работоспособности программы не только в среде программирования, а затем еще раз перечитайте условие: а ту ли задачу вы решали? Если никакие сомнения не омрачают радостную атмосферу в вашем временном трудовом коллективе, то "диктатор" может дать команду отправить вашу программу на растерзание жюри и команда может приступить к реализации следующей программы, текст которой в идеале уже существует в письменном виде.

6) Как бороться со штрафным временем

Любую, даже самую опытную команду, может постигнуть неудача при тестировании ее программы жюри. Если тестирующая программа оказалась недовольна форматом вывода или не прошел один из первых тестов, чаще всего связаный с вырожденными случаями (например, нулями и единицами), то "диктатор" может позволить "реализатору" вернувшейся программы исправить ошибки, если они очевидны, прервав при этом решение следующей задачи. Если же не прошел один из последних тестов или превышено время тестирования, то следует усомниться в оптимальности алгоритма и даже в его правильности. В этом случае, разрешать ошибшемуся "реализатору" немедленно исправлять задачу не рекомендуется ни в коем случае: пусть сначала на бумаге разработает план изменения программы или убедится, что он это сделать не в состоянии. Недостаток работы "сомневающегося" в этом случае также очевиден. Он должен постараться дополнить свои тесты новыми, в том числе и "большими". Ситуация несколько упрощается, если ответом на любые входные данные должно быть одно из двух указанных в тексте задачи слов. Например, "correct" или "incorrect". В этом случае следует лишь добиться, чтобы ваша программа выдавала ответы всегда в одном и том же порядке при запуске ее на одной и той же последовательной системе тестов (вопрос, как это сделать, оставим открытым, чтобы описанные ниже злоупотребления не оказались на совести автора данного руководства). Тогда, если вам было указано, что неверным является ответ на тест 3, то следует изменить третий элемент в последовательности ответов на противоположный и т.д. Так как с вероятностью 1/2 вы будете выдавать правильные ответы на тесты, то из 8 тестов вам останется исправить ответы всего в четырех (в худшем случае пяти) тестах, то есть достаточно послать вашу программу жюри 5 раз и без труда заработать еще одну зачтенную задачу, хотя и с большим штрафным временем.

7) Как потратить последние 15 минут тура. Так как перед смертью все равно не надышишься, а результаты соревнований практически уже всем известы, в том числе и вашей команде, "диктатор" должен помочь всей своей команде сконцентрироваться и довести до результата одну из "не совсем правильно" решенных задач. Конечно, если это еще возможно. В этом случае команда сможет максимизировать количество полученных баллов. И наоборот, роковой ошибкой является доработка каждым из членов команды "своей задачи".

4. Как вести себя после тура

Однозначно ответить на этот вопрос невозможно. Все зависит от того, выиграли вы соревнования или проиграли.

1) Линия поведения для победителей. Во-первых, ни в коем случае нельзя зазнаваться и вообще дразнить судьбу, так как в победах на олимпиадах есть и доля случайности (рекомендуется как-нибудь отблагодарить судьбу, которая на этот раз была к вам благосклонна). Во-вторых, надо дорешать те из предложенных задач, которые все-таки не покорились вам во время тура, и тщательно проанализировать почему это произошло: не хватило времени, знаний, умений и чего-либо еще и постараться устранить недостатки в вашем коллективе до следующих соревнований. И главное, теперь требуется не терять набранную к данному туру спортивную форму (см. пункт 2 настоящего руководства).

2) Линия поведения проигравших. Если вы не выиграли данные соревнования, то, значит, неверно выполняли рекомендации п. 1-3 настоящего руководства, так что придется перечитать их еще раз и сконцентрироваться на исправлении допущенных ошибок. Кроме того, любой проигрыш всегда относителен. Возможно, есть команды, набравшие еще меньше баллов, чем вы. А может, вы сумели решить на туре задачу, подобных которой в вашей практике еще не было, тогда данные соревнования можно рассматривать как собственную победу. Но, вероятно, данные соревнования помогут вам более объективно оценить свои способности и возможности, что тоже немаловажно. Как говориться, важна не победа, а участие. Надеюсь, что данные соревнования не окажутся для вас последними, а данное руководство позволит на высоком уровне подготовиться к следующим.