##### _**Бахыт Маткаримов _

----------------**

Подготовка к школьным олимпиадам по информатике

Программирование является популярным предметом для проведения конкурсов и олимпиад, например, International Olympiad in Informatics (IOI) и Всероссийская командная олимпиада школьников по программированию (ВКОШП) для школьников, ACM International Collegiate Programming Contest (ACM ICPC) для студенческих команд, Top Coder и другие интернет олимпиады для всех желающих. Соревнования по программированию весьма разнообразны, от традиционных олимпиад по решению алгоритмических задач до конкурсов по дизайну, разработке и тестированию программных проектов. У каждой олимпиады или конкурса есть своя специфика, более того редко встречаются универсалы, такие как Филипп Вольски, абсолютный чемпион IOI 2006 и абсолютный чемпион ACM ICPC 2006-2007, одинаково хорошо выступающие в олимпиадах, различающихся по правилам решения задач и проверки решений. Многие тренеры Российских команд ACM ICPC часто выражают мысль, что победители IOI далеко не всегда побеждают в ACM ICPC. Подготовка к конкретной олимпиаде требует развития специфических для данной олимпиады навыков, например, сравним самотестирование решений в олимпиадах IOI и ICPC: в IOI задачу можно сдать фактически лишь один раз и участнику необходимо полностью и самому тестировать свое решение, в ICPC можно сделать множество попыток сдачи задачи и необходимо уметь найти заведомо существующую ошибку или неучтенный вариант в своем или чужом или даже совместном решении. Мне непросто объяснить в чем тут собственно разница, но мой опыт показывает, что если к олимпиаде IOI готовить по тренировочным турам ICPC, то можно забыть широко известные трюки IOI: if n < N then решение на 50 баллов else решение на 100 баллов, вывести YES на все тесты и т.п. На ICPC подобные трюки не имеют смысла, разве что иногда имеет смысл написать простое полу-решение для перекрестной проверки основного решения по большому множеству тестов.

Как тестировать свое решение? Скачайте любой архив Российских олимпиад по информатике, там будут практически все необходимые утилиты и примеры. Я всегда предлагаю 1) создать отдельные директории для всех задач, 2) в директории для задачи создать директорию для тестов tests и скрипт автоматической проверки решений, например, для ОС Windows шаблон выглядит примерно так

 @echo off

 if exist "X.exe" (del /F a.exe 2> nul)

 fpc X.pas

 if not exist “X.exe” do (exit)

 for %%t in (tests\??) do (

  cls

  echo ------------------------------ TEST %%t

  del /f X.out X.in 2> nul

  copy %%t X.in > nul

  X.exe

  fc.exe %%t.a X.out

  pause

 )

В приведенном примере 1) компилируется решение 2) решение запускается по набору тестов, которые лежат в файлах с маской ?? (т.е. имя файла состоит из одной-двух букв), имя файла ответа на тест дополнительно содержит суффикс «.a», 3) на каждом тесте запускается проверяющая программа. Если в задаче один единственный ответ, то в качестве проверяющей программы вполне подойдет fc.exe – file compare, по умолчанию она сравнивает два файла с точностью до пробельных символов, fc.exe /b сравнивает файлы бинарно. По российскому стандарту проверяющих программ testlib, проверяющая программа запускается с 3-ми обязательными аргументами командной строки – последовательно имя файла входных данных, имя файла ответа, имя файла жюри (далее в командной строке может быть задано имя файла результата проверки и другие параметры); кроме того, проверяющая программа возвращает число, зависящее от результата проверки: 0 ОК, 1 – неверный ответ и т.п. Программа fc.exe не может принять в качестве первого аргумента входной файл, более того она всегда возвращает 0, независимо от того, одинаковы файлы или нет. В отличие от Windows в среде UNIX более развитая система утилит командной строки (wc, diff, sed, awk, time и др.) и более развитый интерпретатор командной строки, позволяющий, например, выполнять арифметические действия и создавать свои функции. Например, LINUX /usr/bin/time показывает время выполнения программы – встроенный аналог в ОС Windows отсутствует.

Понятно, что тренированный участник потратит не более пяти минут на создание директорий и скриптов тестирования, не понятно, зачем это делать? В IOI самотестирование обязательно, и я часто наблюдал такую картину тестирования: создается один файл, открытый в окне редактора, типа notepad.exe, этот файл соответствует файлу входных данных. В этом файле находится штук 5 разных тестов, некоторые из которых при тестировании перетаскиваются (copy/paste) наверх и запускается решение. Далее просматривается вывод программы и проверяется в уме по воспоминаниям об ответе на только что перенесенный тест, или этот тест опять же в уме решается заново, или ниже текста теста в отдельной строке лежит ответ (возможно, здесь есть еще какие то варианты). Видя такую картину, я всегда думаю, не лениво ли человеку этим заниматься, можно ведь просто в командной строке нажать стрелку вверх и enter, далее по желанию медленно или быстро пробежаться по тестам. Удивляет еще то, что подобный вид тестирования наблюдается у людей, свободно работающих в командной строке. Вот что серьезно плохо, copy/paste теста никогда не выполняется для всех тестов – в результате зачастую наблюдается такая картина: программа заваливается на 10-м тесте, потом на 30-м, потом на 1-м, т.е. программу насмерть исправили. При этом еще забывают вовремя сохранить старый вариант программы, потом долго и мучительно вспоминают, где и что исправляли.

Конечно, я не думаю, что чемпионы решают все задачи с использованием скриптов тестирования, более того подобное тестирование для хорошо известной задачи на ACM ICPC лишь увеличит штрафное время. Но я считаю, что на IOI из трех задач тура как минимум одна должна оказаться незнакомой, иначе либо тур «нате вам, per favore», либо вы почти чемпион, осталось лишь сдать все задачи на 100 с первой попытки. А вот когда задача незнакомая, то прежде чем в уме выдумывать алгоритм решения, я думаю, имеет смысл заняться рисованием на бумаге и написанием нескольких сравнительно несложных программ, полностью или хотя бы частично моделирующих задачу. Когда не видишь способа решить, надо его найти, а это делается совсем не так, как решается задача с известным алгоритмом решения. Понятно, что решение алгоритмических задач проходит в трех основных этапах, разработка алгоритма, реализация, тестирование и оптимизация решения. Вопрос лишь в том, насколько вы используете свои реализационные навыки на этапах разработки алгоритма и тестирования – в самом простом приближении на этих двух этапах не надо писать программ (можно обойтись пристальным всматриванием и тонизирующим copy/paste), но на самом деле правильно поставленные вопросы на этапе обдумывания задачи могут привести к написанию небольших программ для проверки появившихся гипотез, а генерация тестов и кросс проверка может отловить упущенные варианты и ошибки в реализации! Будете ли вы это делать или пожалеете свои силы и время? Процесс поиска решения требует помимо обдумывания еще и «общупывание», т.е. написание кучи различных тестов/программ цикла математического моделирования: модель –> прогноз –> проверка прогноза –> дополнительные факты –> модель. Если задача новая и неожиданная, то любая придуманная модель решения должна быть максимально критически проверена, нельзя цепляться за то, что вам показалось правильным (когда найдете ошибку, может не хватить времени на исправление), модель должна эволюционировать – это и происходит в цикле математического моделирования. Основной механизм эволюции модели – это составление гипотезы/теста и проверочной программы. При этом вы должны быть психологически готовы поменять любой тест, любой ответ к тесту, любую программу проверки гипотез – ведь это все вспомогательное! Если вы ошиблись в тестах и ответах – вы неправильно поняли задачу, на мой взгляд, это менее обидно, чем получить ноль баллов за недостаточно протестированное решение, в которое вы сильно поверили и на которое рассчитывали. Среди дополнительных к основному решению программ должны быть скрипт проверки, чекеры (проверяющие программы), генераторы тестов (генератор файлов тестов, или некая программа, перебирающая малые входные данные и сравнивающая ответ от двух решений, одно на 50, другое на 100 баллов), решение на 50 баллов (зачастую это переборное решение). Для быстрого выполнения подобного плана действий необходимо быть хорошим реализатором, т.е. простые программы должны писаться вслепую автоматически и без ошибок. При написании простого кода голова может думать об основной задаче – говорят, есть люди, пишущие один сегмент кода и одновременно думающие о совершенно другом сегменте кода.

В IOI есть существенное ограничение – квалификационный вопрос по задаче принимается в течение первого часа, т.е. за час желательно прочитать и понять все три задачи тура. В процессе обдумывания задачи необходимо составить тесты, по ходу решения задачи и тесты и ответы на них, конечно, могут меняться, например, если вы обнаружили, что первоначальное понимание задачи было неправильным. Я редко вижу, чтобы тесты составлялись в момент чтения задачи, хотя, что такое решение алгоритмической задачи – ведь это прохождение тестов и ответов жюри! Тесты должны быть составлены и составляются, следуя известным правилам – перечисляются имеющие смысл частные случаи, граничные значения, генерятся (с помощью «простой» программы генератора тестов) большие и обязательно максимально возможные по условию тесты. Максимальные тесты имеет смысл создать (даже если вы не знаете ответа на них), чтобы хотя бы оценить время работы программы и если повезет удалить некоторые run-time error, которые обычно не возникают на маленьких тестах, например, переполнение стека при рекурсивных вызовах. Если не получается написать генератор теста, подумайте, возможно имеет смысл запустить программу хотя бы на случайном наборе данных? В задачах на планиметрию/стереометрию есть правило – хороший чертеж составляет половину, если не все решение. В задачах по информатике, я думаю, может сильно помочь разноцветное рисование на бумаге, на олимпиаду надо взять разноцветную ручку.

Если за час продуманы алгоритмы и созданы базовые тесты, то реализовать решения надо за час-два часа, тестировать и оптимизировать надо три-два часа. Я так думаю потому, что обычно после тура, когда ход решения объясняется, каждый участник понимает, что вполне мог бы реализовать это достаточно быстро. Одной из причин, почему иногда тратится куча времени на решение задачи, является излишняя спешка – представьте себе, что вы быстро начали писать первое, попавшее на ум, решение, потом обнаружили, что оно полностью или частично неверное, но груз уже написанного мешает и висит в виде мусора, который совсем нелегко выбросить в условиях дефицита времени. В этот момент могут помочь продуманные тесты, но их нет, поскольку вместо составления тестов вы бросились писать чепуху. Возникает куча вариантов дальнейших действий – начать писать новое решение, начать исправлять существующее, делать тесты, подумать или порисовать – по большому счету это нормальный процесс, вот только ощущение напрасно потерянного времени в условиях цейтнота может вызвать панику и спровоцировать еще большее количество ошибок. Тактика решения задач по правилам ACM ICPC не годится для IOI – в ACM ICPC есть вторая попытка, есть два друга рядом – можно позволить себе поторопится, но в IOI нет второй попытки, нет никакой помощи извне, лучше хорошо продумать, сделать множество тестов и вспомогательных программ и быстро реализовать решение, чем быстро реализовать решение без обдуманного набора тестов и вспомогательных программ, рискуя при этом попасть в ситуацию исправления замеченной ошибки в условиях паники. Выделение половины времени тура на тестирование поможет вам сделать виртуальный второй сабмит – если вам повезет, и вы сами найдете ошибку в неправильном первоначальном решении.

На этапе отладки программы я рекомендую использовать GNU debugger, gdb.exe – в процессе отладки не следует полностью полагаться на быстрый палец и окно просмотра, имеет смысл составлять отладочные скрипты – это уже программирование в GDB. Таким образом, решая задачу по информатике на языке Паскаль, вы пишите множество кода на скриптовых языках и возможно еще привлекаете в помощь язык Java – это нормальная ситуация, посмотрите архивы решений жюри!

Конечно, все, что написано выше вам уже часто говорили, вы все равно склонны решать в привычном стиле, но если вы тестируете задачи без скрипта и на одном локальном тесте, то я не устану упрекать вас в этом. Для примера посмотрите на олимпиады по математике и физике – им дают одну тетрадку, половина которой черновик, половина чистовик. Если участник, не обдумав хорошенько план изложения, сразу начнет писать в чистовик, затем обнаружит ошибку или недостаток, то исправить ему это будет совершенно невозможно. Ваш чистовик – это ваше решение на тот бал, на который вы рассчитываете, ваш черновик это тесты, рисунки к тестам, полу-решение и вспомогательные программы и скрипты. Без черновика чистовик у вас может получиться качественным лишь для хорошо известной вам задачи, а организаторы IOI сильно стараются, чтобы вероятность появления такой задачи была совсем не велика. В заключение приведу список олимпиад для обязательного участия и еще пару рекомендаций:

Где тренироваться:

1. Top Coder – www.topcoder.com
2. Интернет олимпиады, Санкт Петербург –neerc.ifmo.ru/school/io/index.html
3. Test the Best, Белоруссия – www.ttb.by
4. USACO, USA – train.usaco.org
5. Открытый кубок МГУ/CBOSS – www.opencup.ru
6. Проект CHAS - homepages.compuserve.de/chasluebeck/

Что не читать, что не делать: не читать книг, в которых вы не можете прочитать сразу залпом десять-сто страниц, не решать задачи без тестов или без возможности проверки решения на Online Judge. Мне лично не нравится книжка Окулова, а классический учебник MIT «Алгоритмы, построение и анализ» не вызывает моего восхищения. Надо сказать, что учебник MIT по Дискретной математике практически тех же авторов заметно лучше читается.

Что читать: коды решений жюри для различных олимпиад. Читайте статьи и форумы в сети, книги которые захватывают, если вы не прочитали книги Шень «Программирование в теоремах и задачах», Ахо, Ульман «Структуры данных и алгоритмы», Липски «Комбинаторика для программистов», я их рекомендую для начала.

Что решать:

1. Архивы на neerc.ifmo.ru, neerc.ifmo.ru/school, Летняя компьютерная школа, архивы национальных и региональных олимпиад по ссылкам с olympiads.win.tue.nl/ioi/ и региональных результатов icpc.baylor.edu
2. Online Judge acm.sgu.ru, acm.timus.ru, www.spoj.pl, acm.uva.es, acm.pku.edu.cn

Что делать, если нет Интернета: надо искать Интернет, например, в областном государственном университете, иначе реально подготовится к олимпиадам по информатике не получится – все задачи и материалы в основном скачиваются из сети! По запросу я могу выслать небольшой архив по электронной почте, или скачать по заданной ссылке большой файл, потом его можно будет скопировать.