Форум DL

Мой профиль

Заметки на Codeforces

«Три мудреца в одном тазу... »

Сразу после старта каждыи? участник выбирает себе задачу, с которои? в состоянии справиться, и начинает решать ее на отдельно взятом листочке. Выбравшии? себе самую простую задачу может решать сразу на компьютере. Для своеи? задачи каждыи? сам придумывает тесты, осуществляет отладку и сдачу. После посылки задачи на проверку жюри, участник за компьютером меняется, освободившии?ся выбирает себе новую за дачу, и так далее.

Достоинством стратегии является то, что все простые задачи будут решены (здесь и далее, слова «будут решены» означают, что сама стратегия направлена на решение этих задач, что никакие другие не могут быть решены, пока с простыми не покончено). Как показывает опыт, иногда этого достаточно для победы. Далее, когда двое будут решать две последних простых задачи, третии? игрок уже освободится, и сможет прорабатывать более сложную; освободившись, к нему может подключиться второи?, а при необходимости, и третии?, так что оставшееся после решения простых задач время команда может варьировать, чтобы в соответствии со своими возможностями решить еще одну или две задачи. Нетрудно показать, что простыe задачи выгоднее решать раньше. В самом деле, если сложная задача так и не будет решена, то предпочтительнее иметь результат, меньшии? по времени. Решенные на раннеи? стадии тура простые задачи дают меньшее время, чем те же задачи, решенные позднее — их вклад будет содержать в себе время на решение более сложных задач, по предположению о сложности — большее время. Данная стратегия всецело направляет игроков на решение задач в правильном порядке — от простых к сложным. Наряду с этим, она обладает рядом недостатков.

Во-первых, все три участника должны виртуозно владеть всеми стадиями программирования — от написания формальнои? постановки до завершающего тестирования; затягивая решение своеи? задачи, игрок задерживает еще сразу две другие задачи, Т.е. каждое время простоя (придумывание тестов, дополнительная отладка после неудачных попыток сдать задачу) умножается как минимум на три. Наряду с этим, как минимум один из игроков должен обладать глубокои? математическои? подготовкои?, что редко совместимо в одном человеке. Наконец, так как нет конкретного человека, принимающего решения о распределении работ, команда может (и, часто так и будет) оказываться в цеи?тноте: идея о консолидации сил для «добивания» однои?, последнеи?, задачи появится слишком поздно; пропадут впустую усилия двоих, решавших каждыи? свою задачу.

Кроме того, стратегия предполагает существенные накладные расходы при любых попытках взаимопомощи: человек, занятыи? (или которыи? только что был занят) решением собственнои? задачи, часто не в состоянии перебороть инертность мозга, и переключиться на другую задачу.

Между игроками должно также иметь место очень хорошее понимание друг друга на компьютере: настрои?ки среды программирования, клавиатуры, редактора, лучше иметь общие.

(Один за всех и все за одного)

В целом, стратегия кажется разумнои? для трех «звезд» — игроков, каждыи? из которых владеет программированием во всех стадиях, и дополнительно имеет глубокую математическую подготовку. Виртуозное владение техникои? программирования и его математическим аппаратом дадут команде большое преимущество и позволят успешно выступить, если команда обладает также высокои? коммуникабельностью. Но команды, сочетающие в себе все перечисленные качества, встречаются редко.

«Столичная» система

Такое название стратегия получила потому, что была впервые в России опубликована в информационнои? методичке регионального этапа чемпионата мира по программированию АСМ членом жюри Е.В. Андреевои?.

Во главе команды находится «диктатор» — генератор идеи?; кроме него, команда включает «реализатора» и «тестера», причем последние две роли могут меняться во время тура. Диктатор излагает алгоритмы решения задач, которые поступают на доработку к одному из участников (возможно, и к самому диктатору). Реализатор, он же — главныи? программист, занимается воплощением изложенных и доведенных до более или менее низкого уровня идеи? в машинныи? текст. К моменту окончания его работы над очереднои? задачеи? тестер уже должен иметь готовыи? набор тестов, позволяющии? быстро проводить отладку и тестирование программы. После этого программа посылается жюри, а команда переходит к следующеи? задаче, идея решения которои? уже некоторым образом оформлена диктатором.

К достоинствам стратегии относится то, что команда будет разумным образом управляться, так как есть участник, ответственныи? за это, и потому управлению будет уделено должное внимание. Более того, такая команда имеет все шансы решить все простые задачи за практически минимально достижимое время, и иногда уже этого будет хватать для победы. К тому же моменту, когда простые задачи будут решены, у вех будут свободные руки, а на бумаге -почти наверняка готов проект решения очереднои?, более сложнои? задачи. Если диктатор обладает глубокими познаниями в математике (а чаще всего, так и бывает), то команда имеет высокие шансы на решение математических задач турнира. Ролевое распределение во время тура решает задачу выбора работы для игроков. Наконец, такая команда едва ли может попасть в цеи?тнот в концовке, так как диктатор на чеку.

Недостатком схемы является чрезвычаи?но большая ответственность, которая ложится на диктатора. На нем — стыд или слава за все принятые решения, как по решению задач, так и по распределению работ. Человек, принимающии? на себя обязанности диктатора, должен быть весьма волевым, обладать большим личным опытом участия в соревнованиях, олимпиадах. Но даже если такого человека удалось отыскать (а это не так просто), каждая его ошибка будет сокрушительным ударом по собственнои? команде. А ведь помимо решения задач, в том числе, математических, на диктаторе лежит ответственность за оценку стоимости разработки тех или иных идеи?; когда задачи, посланные жюри, начнут возвращаться не зачтенными, ему придется экстренно решать, как с ними быть -продолжать отладку сеи?час или отложить, прерывать решение текущеи? задачи или вставить возвращенную задачу «в очередь». Помимо перечисленного, такая тактика предполагает, в целом, последовательное решение задач. Последовательныи? подход, безусловно, оправдан, когда речь идет о простых задачах, — таких, где на разработку алгоритма уходит 10-15 минут. Эти задачи следует решать за минимальное время и затраты на организацию параллельных работ в любом виде едва ли окупятся. Однако параллельное решение может оказаться выгодным для задач, требующих 1,5-2 человекочаса. Данныи? же подход не предусматривает распараллеливания, кроме как на капитана и двух других членов.

(Кадры решают все!)

Итого, стратегия является весьма подходящеи? (возможно, близкои? к идеальнои?) для команд, имеющих ярко выраженного опытного лидера. Как уже было отмечено выше, такие лидеры встречаются не столь часто. Попытка же применять такую стратегию в «ровнои?» команде часто обречена, так как ошибки капитана сведут на нет все старания его помощников.

Мой профиль

«Вместе весело шагать... »

Для контраста хочется привести еще пример — антипод для стратегии, где каждыи? решал свою задачу. Можно, наоборот, решать все задачи вместе, начиная с простых и постепенно переходя к сложным. При этом возникнет естественное ролевое распределение игроков внутри однои? задачи; игроки будут последовательно выполнят этапы реализации задачи, как они себе их представляют. Нет нужды говорить, что такая команда обязана процесс программирования представлять себе одинаково.

Недостатки стратегии явно видны: потери времени при решении задач никем не контролируются и могут принимать большие размеры. Параллельная работа над разными задачами отсутствует, что снижает общее число решенных задач; с другои? стороны, неконтролируемые временные потери ухудшают время зачета сданных задач.

Тем не менее, стратегия имеет и ряд достоинств, о которых не следует забывать тем, кто разрабатывает «лучшие» стратегии. Во-первых, за время всего тура, скорее всего, будут решены все простые задачи, и при этом, команда достаточно застрахована (если взаимопонимание между партнерами на высоком уровне, а это широко распространенное качество) как от ошибок в определении простоты задачи, так и от ошибок отдельных игроков; отдельные ошибки имеют высокую вероятность исправления другими членами команды. Во-вторых, наработка взаимопонимания, достаточного для применения такои? стратегии, требует весьма малого количества тренировок, лишь бы команда была «спаяна» достаточно крепко. В-третьих, для формирования команды вообще не требуются «звезды» — асы в программировании и математике.

(Логика, простота и ясность — три кита производства)

Более того, такая стратегия ценна еще и тем, что может быть применена большинством команд, как на тренировке, так и на соревнованиях. Ее применение будет всегда оправдано, если известно, что решения всех простых задач достаточно для прохождения в следующии? круг соревновании?. Другои? пример — когда вуз выступает впервые и время для тренировок весьма ограничено (или это может быть отборочныи? чемпионат вуза). Если команда решит для себя, что показать более чем пятидесятипроцентныи? результат, занять место в первои? четверти турнирнои? таблицы для нее важнее, чем рискнуть на первое место и проиграть, простая стратегия может стать оптимальным оружием.

Мой профиль

«Сумасшедшее чаепитие»

Эта стратегия, как и одна из приведенных выше, является ролевои?.

Остановимся на неи? подробнее, так как именно ее применяли команды Уральского университета в своеи? первои? поездке, именно она была выстрадана этими командами и о неи? мы можем сказать довольно много. (Название, безусловно, не лучшее, заимствовано из книги Льюиса Кэрролла «Алиса в стране чудес»), Тот факт, что весьма разные команды, применявшие эту стратегию, показали весьма близкие результаты, позволяет предположить, что результат есть не только следствие выбора команды, но и следствие выбора стратегии (это утверждение — попытка обосновать, почему столько внимания уделяется этому вопросу).

Команда должна быть дружнои? и иметь высокии? уровень коммуникабельности. Ничто не приносит столько бед, как прохладныи? психологическии? климат. Студенты на чемпионате подобны пилотам в кабине пассажирского лаи?нера -если между пилотами плохая атмосфера, лететь нельзя. Вместе с тем, каждыи? человек индивидуален, не похож на других, и ему приятно, если для реализации себя, в том числе, на соревнованиях, у него есть своя ниша. Тем самым высказана мысль, что люди, объединенные в одну команду, вполне могут обладать разными талантами. Для команды нам потребуется один ярко выраженныи? математик, один такои? же программист, и один, в более или менее равнои? степени владеющии? обоими ремеслами. Поясним чуть подробнее.

Математик призван видеть абстрактную суть вещеи?. Его стихия — обобщать, выписывать рекуррентные формулы, дифференцировать, доказывать оценки численных методов, получать функции общего члена, подсчитывать число сочетании? и порядок сходимости, брать первообразные и первые интегралы, работать алгебраическими методами над геометрическими фигурами и наоборот, выполнять дополнительные построения, применять разностные схемы. Его место там, где волшебная палочка математического аппарата превращает грозное условие в послушную двухпараметрическую игрушку. Он способен сделать бесконечное число шагов за ничтожное время, написав формулу суммы ряда или ортогонализацию Грама-Шмидта. Произведения, суммы, цепные дроби, векторная алгебра, геометрические методы — да разве можно перечислить весь его арсенал!

Программист являет собои? в некотором смысле противоположность математику. Он мыслит конкретно, его сырье -графы, цепи, циклы, очереди, стеки, массивы, списки, деревья, деки, правила вывода, ветвления, потоки, фаи?лы. Так же как и у математика, его вселенная необъятна и абстрактна, но каждая ее деталь подразумевает конкретное воплощение. Это огромная мастерская. Стоит программисту определить, какои? инструмент ему нужен, и начинается сборка, и вот уже слышно веселое жужжание новорожденного механизма, там, где математик видит нечто, ни на что не похожее, или где с его губ падает слово «тривиально», программист может наи?ти по горло работы. Виртуоз отладки, гении? трансляции — программист понимает каждое движение курсора, каждыи? машинныи? «вздох» и паузу не хуже, чем восклицания и плач партнеров. В душе, каждыи? программист немного хакер, но он старательно скрывает в себе это качество и может даже выучить наизусть теорию матроидов, если ему скажут, что это всего лишь объекты, двои?ственные графам.

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

Иначе говоря, творцы часто считают слишком многие вещи само собои? разумеющимиcя, и железная болванка «Intel» не всегда способна простить им это.

«Практик» кует железо, из которого потом рождаются строки кода под умелыми руками программиста; он спускает на землю написанные без разбиения на строки математические формулы; наконец, одна из самых важных его миссии? — он позволяет математику не отвлекаться на «ерунду» вроде составления тестов. И последнее: если программист в команде устанет, его мозг и пальцы перестанут деи?ствовать идеально согласованно, и еще в некоторых критических ситуациях, практик способен сеть за штурвал-клавиатуру и спасти судно.

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

После старта ближаи?шая цель команды — разделаться с простыми задачами. Следует, однако, понимать, что при таком разделении труда, какое описывается, простые задачи никогда не будут решены за минимально возможное время и весьма часто наи?дется команда, сдавшая эти задачи раньше. Не нужно горевать об этом. Нужно побеждать общим числом задач, или даже временем, но на следующем уровне. Чтобы этого достичь, нужно минимизировать время простоя отдельных игроков. В соответствии с этои? целью, программист немедленно начинает набивать общии? шаблон: ввод, обработка, вывод. Он же несет обязанность немедленнои? отладки шаблона, так как ошибку в шаблоне придется исправлять многократно. В силу того, что применение описываемои? тактики требует существенного числа тренировок, программист, как правило, будет знать искомыи? шаблон наизусть к началу соревновании?. Еще раз подчеркнем, что кроме специально оговоренных ниже случаев никто не должен лезть за клавиатуру. Компьютер -дом программиста, и никого больше.

Мой профиль

В то время, как программист занимается набором шаблона, математик и практик изучают условия задач. Цель этого изучения: обеспечить программиста и практика двумя самыми простыми задачами. Самая простая задача выдается программисту (обычно есть сомнения, и, когда простые задачи отделены, их список с минимальными комментариями представляется практиком программисту, и тот выбирает себе самую простую задачу). Следующая по простоте задача передается практику, которыи? на более или ме нее низкоуровневом псевдоязыке излагает с ходу ее решение. Пока эти двое (практик и программист) занимаются описанным процессом выбора двух задач, математик выбирает следующую по простоте задачу и принимает решение: оставить ее двум другим или взять себе. Нет однозначного рецепта для любои? ситуации. Главное, что должен обеспечить математик своим решением -минимизацию простоя. К тому моменту, как программист закончит свою задачу, практик уже составит к неи? некоторые тесты. В то время, как программист далее будет, обратно, тестировать свою задачу, а потом разбираться с задачеи? практика, практик должен иметь возможность приступить к третьеи? задаче. Это может быть либо никем не тронутая простая задача, либо математическая задача, разобранная математиком по косточкам, либо более сложная задача. Последняя ситуация соответствует случаю, когда простых задач не осталось, и математик собирается поменяться с практиком местами, когда участь первых двух задач будет решена.

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

То обстоятельство, что за компьютером все время сидит один человек — программист — требует от двух остальных особои? аккуратности в оформлении решении? задач.

Существует два возможных подхода: либо программист самостоятельно доводит данныи? ему алгоритм до программного кода; либо составитель алгоритма (математик или практик) помогает ему в этом. С точки зрения максимального распараллеливания работы первыи? подход эффективнее, но в деи?ствительности, второи? вполне может приводить к лучшему результату, если только реализуемыи? алгоритм не является совершенно тривиальным.

По-видимому, наиболее разумным будет оставить за программистом решение, будет ли он самостоятельно реализовывать данныи? ему алгоритм или воспользуется помощью автора. Возможно, программист решит набрать часть алгоритма самостоятельно и воспользоваться помощью товарища при наборе другои? части программы.

Итак, процесс пошел, осталось его поддерживать. Необходимость поддержания возникает не всегда, а когда решена очередная задача. Назовем такои? момент точкои? выбора, если до конца тура осталось более двух часов, и критическои? точкои?, если менее 70 минут. В диапазоне 80-110 минут такая точка может быть как точкои? выбора, так и критическои? — в зависимости от того, какие задачи остались, сколько решено, и какие находятся в разработке. Решение о том, является точка критическои?, или нет, должен принять капитан.

Если точка — точка выбора, то освободившии?ся оценивает текущую ситуацию, и, в зависимости от числа задач в разработке и степени их завершенности, начинает разрабатывать новую задачу, приготовленную для него математиком, придумывать тесты, если это не очень трудоемко, к задаче, которая вот-вот будет набита и отлажена; наконец, готовить работу практику, если это математик и перечисленные варианты почему-либо не устраивают.

Если точка является критическои?, и освободившии?ся один, то он либо присоединяется к решению задачи, находящеи?ся в разработке, либо берется за прописывание в псевдокоде задачи с ясным алгоритмом — по решению капитана. В этот же момент может быть принято решение об использовании эвристики.

Отметим мимоходом, что наряду с отсеиванием простых задач для решения в первую очередь, жизненно необходимо отсеивать также сложные задачи, которые решать вообще не планируется. Новая задача ни при каких условиях не может быть выбрана из этого «черного списка», если хоть одна из других задач еще находится в разработке. Смысл этого условия — в минимизации времени решения. Выше головы не прыгнешь, а разбазаривание ресурсов на решение трудных задач, как уже отмечалось, увеличивает суммарное время зачета для задач, которые будут в конце концов сданы командои?.

Если точка является критическои? и освободившихся двое, то капитан принимает решение — добивать оставшуюся в разработке задачу, или есть все шансы за успех решения еще однои?.

Неудачнои? можно назвать ситуацию, когда очередная задача готова и сдана, но алгоритма для следующеи? еще не придумано. Такое может случиться как вследствие ошибок планирования или неправильного выбора задач, так и в результате «естественных» причин (например, одна простая задача, а остальные относительно сложные). В этом случае программисту приходится «заниматься не своим делом» — идти на помощь одному (или сразу обоим) из оставшихся членов команды. Решение о том, чем именно программисту заняться, принадлежит капитану команды. Описанная выше ситуация плоха по многим причинам. Во-первых, программист настроен на набивание текста, отладку, работу за компьютером, и внезапное перемещение его на роль составителя алгоритмов не способствует улучшению производительности команды. Во-вторых, программиста придется «вводить в курс дела» — рассказать ему условие и варианты решении?, над которыми ведется работа, а это опять-таки потеря драгоценного времени. И в-третьих, компьютер у команды один, и он является достаточно важным, если не важнеи?шим ресурсом, которым владеет команда, и поэтому простои? компьютера краи?не нежелателен. В общем и целом, вся ориентация даннои? стратегии — на минимизацию простоя, на постоянное решение задач, имеющих реальные шансы быть завершенными до финального свистка.

Стратегия, как и остальные, имеет много плюсов и минусов. Наиболее важныи? плюс: разделение труда не только ролевое, но и функциональное, что позволяет минимизировать простои? без яркого «лидера». Наиболее важныи? минус: нет шансов на победу, если не смогли решить хотя бы одну или две задачи из списка «более сложных». Такая стратегия на решении только простых задач проигрывает по времени всегда.

Начав тренировки по даннои? стратегии, любая команда довольно быстро наи?дет оптимизирующие изменения, которые позволят более эффективно работать именно этои? команде. Поэтому нет смысла далее подробно прописывать «программу» деи?ствии? отдельных игроков. То, что было хорошо для первых команд Уральского ГУ, совсем не обязательно будет приемлемо для всех остальных.

Мой профиль

(Даваи?те передвинемся — мне нужна чистая чашка)

Условное название стратегии выбрано из-за того, что «освободившии?ся» игрок по ступает как типичныи? мартовскии? заяц: ищет относительно чистую чашку.

«Предохранитель»

Еще одна ролевая стратегия, являющаяся разновидностью предыдущеи?. В окружающем нас мире многие любят заниматься одним (и только одним) делом. Поэтому часто существенно сложнее отыскать хорошего «практика», чем математика или программиста. Предлагаемая к рассмотрению техника предлагает один из вариантов решения этои? проблемы. Количество приведенных стратегии? не должно раздражать читателя. Едва ли возможно поверить, что для столь молодого в нашеи? стране дела может сразу быть выписан оптимальныи? для всех алгоритм. Поэтому следует выбрать моменты различных стратегии?, кажущиеся наиболее разумными, и объединить их в свою собственную, «победную».

Рассматриваемая стратегия выделяет в команде одного математика и двух программистов. Кроме того, один из членов команды является капитаном. Сразу после старта каждыи? из программистов получает по простои? задаче (Методы выбора простых задач могут быть различны; например, каждыи? может читать с разных концов до простои?, или один садится набивать шаблон, а двое читают, и т.п. Во всяком случае, эта тема достаточно подробно обсуждалась выше и ничего нового в этот момент стратегия не вносит). Далее одна задача набирается, а другая параллельно готовится. При этом математик служит как бы «центром», хозяи?ственнои? частью команды. Он занимается составлением тестов, помогает каждому из программистов в изобретении алгоритма, при необходимости, проводит оценки времени, прописывает решения, алгоритмы для задач на бумаге. Программисты регулярно обращаются к нему за помощью, тестами и консультациями.

Отличительная особенность поведения такои? команды — смена оператора во время тура. Каждыи? программист ведет «свою» задачу. Такои? подход имеет свои плюсы и свои минусы. Плюсы: облегчение загрузки программиста. Не каждыи? способен выдержать пять-шесть часов напряженнои? работы за терминалом без потери производительности, внимательности, сообразительности. А такая потеря дорого обходится: это и снижение эффективности использования компьютера, и проблемы в конце тура, когда бывает чрезвычаи?но важно сдать еще одну задачу. Здесь же каждыи? программист «предохраняет» другого, позволяет ему немного отдохнуть. Другое преимущество: локализуется ответственность за сдачу конкретнои? задачи. При этом математик в курсе событии?, он способен квалифицированно охарактеризовать ситуацию в критическии? момент, и в то же время за каждую задачу отвечает конкретныи? программист.

Теперь о недостатках. Предполагаемая возможность смены оператора за терминалом означает тщательную проработку условии? этои? смены. Нет худшего варианта, чем сумбурное чередование лиц перед монитором. Если избрать такои? вариант, на тренировках особое внимание следует уделить именно «смене караула»). Приведем один из возможных вариантов организации этои? смены. Программист доводит задачу до посылки жюри, после чего принимается за другую на бумаге, освобождая машину. При получении отрицательного ответа от жюри, программист, когда место за терминалом освободится (никого не выгоняя!) сам (или советуясь с другими) решает, заняться ли ему отладкои? не зачтеннои? задачи, или набирать новую. Если в результате принятого решения очередная посылка жюри происходит достаточно быстро (10-15 минут), то можно сделать оба дела, прежде чем партнер-программист будет в состоянии приступить к своеи? работе за клавиатурои?, а не на бумаге.

Подчеркнем, что каждому всегда есть чем заняться — простоя как такового не происходит. Если программист не занят на машине, он составляет тесты (в том числе, может помочь в составлении тестов партнеру, если необходимо «сменить рубашку»).

(Пусть он в связке в однои? с тобои? — там пои?мешь, кто такои?)

В целом, работа происходит «попарно» — каждыи? программист с помощью математика сдает очередную задачу. Команда как бы состоит из четырех человек, в чем тоже некоторое преимущество.