В последнее время для меня все актуальнее становится вопрос о том, какими же все-таки должны быть условия задач? Что должно содержаться в этих условиях и как это правильно сформулировать? Как избежать хотя бы малейшей двусмысленности?
При создании контеста я всегда считал составление условия самой сложной задачей. Всегда старался избегать написания условий задач, в которых нельзя обойтись коротким и понятным условием. Если при разработке контеста я читаю чужое условие, то я стараюсь максимально придраться к нему, чтобы ни у кого из участников не возникло ни малейшей двусмысленности. Я иногда рефлекторно защищаю свои (порой изначально двусмысленные) формулировки. Но, как только немного остываю, сажусь и стараюсь исправить все замечания до последнего. А после того, как исправляю, спрашиваю стало ли понятно теперь.
Часто бывает так, что ужасно хочется приплести к условию задачи какую-то жутко забавную легеду или, как зачастую кажется авторам, подходящую как нельзя кстати именно к этой задаче. При написании условия задачи надо всегда помнить, что легенда может увести участника от самой сути задачи настолько далеко, что лучше бы ему просто увидеть примитивное условие на языке математических обозначений. Часто легенды плохо согласуются с оригинальным пониманием условия, что сбивает с толку и заставляет участника непроизвольно додумывать какие-то дополнительные ограничения.
Если участнику непонятно какое-то обозначение из условия или как в примере получается именно такой ответ, то всегда можно написать примечание, которое снимет все вопросы. Тем не менее, примечание должно быть лишь вспомогательной составляющей условия. Условие без примечания не должно быть неполным и должно содержать все необходимые ограничения.
Очень важно заранее увидеть страницу, которую будет видеть участник. Некоторые важные элементы условия могут оказаться незаметны в конечном итоге из-за своего геометрического положения на листе бумаги или на экране монитора.
Важных пунктов при составлении условия - великое множество. Сложно перечислить все важные пункты, да я и не буду пытаться перечислить их все. Более того, всех пунктов я, наверное, и не знаю.
Всю эту тему я решил поднять из-за недавнего спора с одним программистом (если захочет, сам назовет себя) на тему того почему же я изначально неправильно понял условие задачи, которую мне недавно довелось порешать. Я погорячился и даже написал автору задачи (в индивидуальном порядке), что это условие написано некачественно. Лишняя агрессивность была вызвана тем, что я позорно слил этот раунд, и во мне бурлил негатив. Эту задачу я все-таки сдал во время раунда, но потратил на нее намного больше времени, чем потребовалось бы, если бы я изначально правильно понял формулировку. Спасибо тем, кто отвечал на вопросы, за то, что пояснили тест из примера. Это дало мне все-таки понять ту самую формулировку, которую подразумевал автор.
Для начала я полностью поясню ситуацию... Когда я прочитал условие, то сразу же обратил внимание на следующее предложение: "...Ктулху назовем такой неориентированный граф, который может быть представлен как набор из трех или более корневых деревьев, корни которых соединены простым циклом...". Я подумал, что конечно-же имеется в виду цикл, состоящий из трех и более вершин. Но зачем вот это "трех или более". "А! Наверное подразумеваются только деревья, состоящие из более, чем одной вершины" - подумал я. "Ну да, все логично! У Ктулху такая морда с висящими из нее штуками. Менее трех таких болтающихся из морды штук у Ктулху - не православно, вот отсюда и такое ограничение!" - вот, что я подумал следом и принялся набивать код решения именно такой задачи. Написав, я заметил, что на тесте из примера мое решение выдает не такой ответ. И действительно, если удалить цикл из него, то остается только два дерева. И тут в голове начинаю перебирать как же надо понимать условие: Может быть можно считать поддеревья отдельными деревьями? Может быть можно считать одинокую вершину тоже деревом? Я задаю вопрос жюри и свет проливается. Причем ответ был очень подробным пояснением, откуда же берется три дерева в тесте из примера. Да, теперь задача действительно решается одним дфс-ом, подумал я. В моем решении я просто убрал if на то, чтобы деревьев с количеством вершин больше 1 было не менее трех и отправил. Больше я к этой задаче не возвращался.
Позже, все кому я говорил о том, как много времени я потерял на этой задаче (таких было не так уж и много) тыкали меня носом в различные вещи. Кто-то в то, что я не додумал условие из теста из примера. А между делом, он и сам обратился к тесту из примера, чтобы разобраться. Кто-то винил меня в том, что я не прочитал примечание, а, соответственно, прочитал не все условие.
Лично я считаю, что условие должно быть таким, чтобы не требовалось разбираться в тесте из примера, чтобы понять, что же от меня требуется. А о существовании примечания я и знать не знал. Видимо, авторы не заметили того, что оно находится под двумя огромными тестами. А по скроллбару сложно ориентироваться, ведь в условии находится еще огромная (но не самая полезная) картинка. Как выяснилось, пояснение того, что дерево из одной вершины все же надо учитывать, находилось именно в примечании. А условие про "трех и более" означало тривиальный для меня факт того, что циклы не могут содержать менее трех вершин.
Человек, с которым я спорил, утверждает, что и без примечания все понятно и однозначно. Этот человек решил эту задачу, не задавая вопросов жюри, то есть понял с первого раза условие правильно. Именно он сказал, что я [начало цитаты] не полностью прочитал условие [конец цитаты].
Как мне показалось, ответ, который дали мне, был использован и ранее. Я могу ошибаться, но по-моему я не единственный из тех, кто задал такой вопрос.
И тут, собственно, остается много вопросов, по которым я бы хотел услышать мнение общества:
1) Было ли условие (без учета примечания) однозначным для понимания для Вас?
2) Можно ли выносить то самое ограничение на количество вершин в корневом дереве в примечание или же это часть условия? (опять же относительно Вашего мнения)
3) Достаточно ли заметны для Вас примечания под "примерами тестов" при больших высоте страницы и размерах этих самых примеров?
По остальным пунктам согласна.
По-моему, нормальное условие.
Я, правда, поняла задачу только тогда, когда пошла взламывать чужие решения.
Была удивлена :) Но не считаю свое неумение читать багом автора.
Если задача чем и плоха, то тестами - мое неверное решение (на два экрана) прошло, хотя тест, который его ломает, вполне очевидный.
2. Да, можно. Это стандартное определение дерева. Формально в этом месте условия нет оснований додумать, что в дереве должно быть строго больше одной вершины. Проблема, как мне кажется, не в этом, а в том, что можно это предложение прочитать по-другому: вместо “из >= 3 деревьев, все корни которых соединены в цикл” прочитать “из >= 3 деревьев, корни которых соединены циклом, возможно, с добавлением вершин степени 2”. А из-за этого уже приходится что-то додумывать.
3. Да. При чтении условия я сначала смотрю, что в нём есть (собственно условие, формат ввода, формат вывода, картинка, два теста с ответами, примечания). Это (а также беглый взгляд на примеры, а потом на формат I/O) заодно помогает понять, стоит ли вообще читать именно сейчас именно эту задачу. А потом при чтении стараюсь не пропустить ни один из этих элементов. Хотя бывает, что читаю не с начала (например, когда кажется, что в первых нескольких абзацах только легенда) или заканчиваю читать раньше, считая, что уже всё понял (например, в TopCoder Easy).
На мой взгляд, в этом раунде в целом условия были интересные (что есть плюс), но в данном месте действительно возникла неточность (хотя бы судя по тому, что уже несколько человек высказались за это).
1) Нет, запнулся на том же месте
2) Нет, наверно лучше писать в условии
3) Скорее да, все-таки примечания идут сразу после условий.
А я вот думаю. Может вместо зелёного Ктулху в условии стоило привести чертёж графа из примера... Тогда бы сразу было над чем задуматься...
Видимо и тут страсть к прекрасному в виде этого симпатичного создания Ктулху возымела своё.
По большому счёту ничего страшного не произошло.
Есть даже положительный момент - многие авторы задач (и я в том числе) для себе определённые выводы сделали.
Так что автора этой задачи хотелось бы поблагодарить и за корректирование моего авторского взгляда на формулировку условий задач.
Ну учитывая что ниже в условии написано "граф не содержит петель и кратных рёбер" это довод в пользу "логичности" довольно шаткий :D
> в примечаниях этой задачи содержались исключительно тривиальные утверждения
Не знаю, может продублирую какое-то сообщение ниже, но если из условия убрать "трех или более", то получается, что граф из одной вершины является сомнительным Ктулху, а граф К2 - Ктулху (определение простого цикла из примечания допускает формализацию, в которой "одна вершина - простой цикл", а также ему строго соответствует граф из двух связанных вершин)
Тут ещё картинка наверное повлияла на восприятие. Читаем условие про "цикл с 3 корневыми деревьями" и сразу понимаем "ага, Ктулху он значит такой, кругленький и у него 3 или больше конечностей".
Поэтому даже после того как я заметил что первый тест представляет Ктулху с 2 конечностями и минут 15 потратив на перечитывание условия, я так и не вник в суть примечания и сказал себе "а ну его в качель, время только тратить - не корову ведь разыгрывают!"
Думаю, если цель автора была нарочно тренировать внимательность участников, то эта цель достигнута. А если "эффект Ктулху" получился случайно, то лучше такого не допускать. К тому же, учитывая что условие можно было сократить до пары строчек, и учитывая что часть соревнующихся читают условие на языке не родном ни для них, ни для автора, ни для переводчика.
второй большущий жирный минус (который я бы с радостью поставил, если бы смог) за изменение текста комментария на 100%, тут даже никакое "UPD" не спасает
Я так понимаю что если уж писал "длинно, со вкусом и слегка полуприподзапутанно", то был к этому в душе готов. ;-)
Задачи неплохие - в этом смысле респект. А формулировка (имхо) подкачала.
да, мои условия требуют навыка "фильтрования бреда"
однако, надо быть, извините за выражение, идиотом, чтобы пытаться понять условие из собственного разыгравшегося воображения и картинки, на которой изображён зелёный человечек, вместо того, чтобы разобраться с единственным формальным предложением в условии задачи, которое даже начинается со слова "формально"
Но неужели, как автору, приятно чтобы ещё до соревнований появлялись шутки вроде:
о подготовке по книге рассказов Лескова
А после того начинались рассуждения о том идиоты ли те, кто читали задачу или те кто её писали?
Мне кажется что вы сами предпочли бы обойтись без таких моментов. Или я не прав и в этом самый цимес?
Напоминает анекдот: А команда США в этот раз на соревнования по фигурному катанию не поедет, вместо них будет участвовать сильная команда американских юристов.
если мне запретят писать длинные условия так, как мне нравится (введут соответствующую цензуру, правила, требования), то я не стану получать удовольствие от подготовки контеста и, как следствие, перестану их делать
конечно, находятся люди, которые сливают контест, а потом обвиняют авторов во всех смертных грехах (иногда, впрочем, по делу), но находятся и другие, которые пишут в личку или говорят при встрече, какие интересные и классные условия задач
и знаешь - людей второй категории много больше, чем первой ;) просто они не участвуют в этих холиварах - незачем
не вижу ничего обидного в шутке Паши Хаустова, я даже плюсанул :)
в любом случае, если мой никнейм присутствует в списке авторов задач - жди беды :D благо, авторы известны до начала раунда, поэтому особо вредным ненавистникам длинных условий могу предложить посдавать задачи в режиме дорешивания, а не мучать себя и других ;)
Просто тема оказалась для многих интересной во многих и разных аспектах и каждый хоть немного, но, как мне кажется, всё-таки изменил (подкорректировал), свои взгляды на это.
Это нормальный процесс расширения рамок взаимопонимания, по моему разумению.
Задача действительно сводится к тому что "Ктулху это связный граф с единственным циклом, причём длина цикла > 2" и никаких корневых деревьев (и даже петли / кратные рёбра уже не нужно оговаривать).
Если же была цель "малость запутать" то да, условие из 2 строчек не годится.
Вопрос как обычно крутится вокруг непонятной "золотой середины" в вопросе сколько времени участник должен потратить на программирование, а сколько на поиск конкретики в условии.
Я смотрю на это с точки зрения промышленного программирования, где заказчик или системный архитектор сам заинтересован в том чтобы программист его понял. С точки зрения спортивного программирования конечно всё может выглядеть иначе.
1) Да.
2) Можно.
3) Достаточно.
А если возникают проблемы из-за непонятностей в условии - это участнику повод совершенствоваться, а не пинать автора. Автора можно пинать, разве что если участник задал вопрос, а ему ответили неправильно.
Аргумент у меня за такую позицию стандартный: на финале ACM у тебя будет условие на страницу, где в первых двух абзацах будет, возможно, только одно значимое для решения слово, причём это будет слово thousand. И если кто-то опять скажет, что "не одним ACM мир живёт", я не стану с ним спорить, только укажу, что Павел в статье, кажется, реквестирует личное мнение.
До сих пор помню, как на нашем финале в какой-то задаче надо было распарсить строчку. Мы ее распарсили, но сэмпл не проходил. В середине двух страниц текста обнаружилась фраза: строчка в файле может быть записана как в прямом, так и в обратном порядке. (!!!)
Я тоже понял условие неправильно и тоже написал решение, проверяющее невырожденные деревья.
Затем не прошел первый тест, посмотрел в примечание...
И да, задачу я так и не сдал, т.к. забыл проверить связность графа. Интересно, 46 тест, на котором у меня упало, был добавлен из взломов? (всего их 47)
1. Понимание про то, что в корневом дереве должно быть больше одной вершины я считаю на совести тех участников кто так понял. Никаких объективных предпосылок к этому не было. А тот факт, что такое понимание отсекалось на довольно ранней стадии (сэмплы из условия) говорит о том, что условие составлено довольно хорошо. Хотя возможно это так случайно получилось :)
2. Примечания после сэмплов, которые не относятся собственно к сэмплам мне не нравятся. Их действительно надо делать идущими после условия, до сэмплов. Как это делается например на топкодере. А после сэмплов пояснять сами сэмплы, если нужно. К сожалению, полигон не позволяет штатными средствами все это реализовать, поэтому пока так и происходит. Возможно в таких случаях надо прямо в условии писать что-то типа (см. примечание) там где встречается термин объясненный далее.
3. Вопрос про то должны быть условия короткими или длинными да с легендой обсуждался уже много раз, и я понял так, что однозначного мнения по этому поводу нет. А значит нет объективных причин раз за разом после матча (а в этот раз все началось еще и до матча) жаловаться на длинные условия.
А почему кстати вырожденное дерево с одной вершиной - это дерево, а вырожденный цикл из единственной вершины - это не цикл?
UPD: это не наезд, это просто попытка понять, почему TopCoder (как мне кажется) старается избегать специальных терминов в формулировках (даже таких простых как "натуральное число").
Это "определения из теории графов от jte" или "определения из теории графов которые знает каждый идиот а тот кто не знает, тот точно идиот"?
В ваших определениях сквозит что "простой путь" тоже может состоять из одной вершины. И цикл (петля) может состоять из одной вершины. Ну почему же такое неравноправие и цикл в отличие от пути или дерева должен ещё и ребро содержать?
Теорема. Для графа G = (V, E) (|V| = n, E = m) следующие утверждения эквивалентны:
Не, тут дело в другом. Не в определениях а в сути. Некоторые алгоритмы на графах критичны именно к тому, является ли он ациклическим. Причём конечно в смысле циклов с 1 или больше ребром. Здесь "правильное определение" подсказывает сама практика.
Словосочетания "вырожденный цикл" и "вырожденное дерево" я вообще вроде впервые вижу. Я понятия не имею почему одно дерево а другое не цикл, если хотите называйте одно не деревом. а другое циклом, никто не запрещает. И к чему этот вопрос я тоже не понял. На топкодере, да и здесь действительно стараются избегать специальных теминов. Опять же не понятно зачем вы упомянули эту прописную истину :)
Простым циклом назовем множество из v вершин, которые можно пронумеровать так, что будут существовать ребра только между вершинами с номерами 1 и 2, 2 и 3, ..., v - 1 и v, v и 1
И что, из него следует что цикл невырожденный? При усилии воображения по этой фразе можно даже подумать что наличиее рёбер для цикла не является необходимым условием. ;-)
У большинства участников вопроса о том, что такое цикл, не возникло, я надеюсь.
Конечно не возникло. И про корневое дерево тоже вопросов не возникло, как видим - все были достаточно уверены в своей точке зрения. :D
Неумение читать и понимать условие - личная проблема олимпиадника.
В нашем же случае, скажем, KhaustovPavel, Alex_KPR и it4.kp находятся довольно близко друг к другу в общей таблице, а потому лучше таких случаев было бы избегать (имхо).
Честно говоря то что задачу не понял я - это мягко говоря не проблема - я не олимпиадник и даже не сочувствующий (я тупо для передышки мозга на часок от своего проекта захотел отвлечься).
А то что с задачей возникло определённое непонимание у тех участников для которых соревнования действительно важны, например у Павла (это небось его со 100-какого-то на 200-какое-то место откинуло, нет?) - это жаль, конечно.
И согласитесь - любой уважающий себя спортсмен предпочитает выигрывать не за счёт того что кто-то другой срезался неправильно поняв задачу... Ну мне так кажется...
С корневым деревом тоже все было понятно: в примечании было определение (общепринятое), на примере можно было убедиться, что используется именно это определение (а не то, что, вероятно, только что придумано участником по прочтении легенды).
Хотя тут надо заметить что путь соединяет N вершин с помощью N-1 ребер, а у цикла количество ребер и вершин совпадает.
1)Да
2)Да
3)Да
Илья, вы не учитываете разницу между форматами соренований на олимпиадах по Математике/Физике и соренованиями по Информатике. К условиям здесь применяются совершенно различные требования.
Олимпиады по Математике и Физике, требуют нахождения ответа и строго его доказательства, поэтому задача формируется тоже строго - четко и однозначно. Если бы на олимпиадах по Информатике так же требовалось найти алгоритм решения и строго его доказать, то и условия писались бы соответствующие. Причем, более чем уверен, что с таким форматом популярность бы сильно снизилась. Условия задач окутаваются какой-то историей чтобы создать иллюзию блуждания по коридорам логики и разгадывания головоломок, потому что именно это приносит удовольствие. Если давать сухо, только суть, то соревнования превратятся в
фаршфарс.А популярность олимпиады по Информатике, в случае если условия нужно будет доказывать строго, сильно снизится, потому что очень часто пропихиваются догадки, а не решения, более того, можно опробовать много догадок, и хоть один раз таки угадать. А если доказывать нужно будет строго, аудитория отвалится. Даже не надо ходить далеко, тот раунд который проводил Сергей Ведерников, та задача, где авторское решение оказалось неверно - сколько людей пытались ее сдать, причем уверен, многие пытались потому что какие-то примитивные догадки, были очень похожи на ответ, и проходили много претестов. И как мне кажется Petr эту задачу не пробовал сдавать потому что он пытался ее _решить_ а не угадать, но подходящего решения не нашел, и именно поэтому он единственный сдал E, потому что он ее _решал_ и таки решил, в то время как многие опять же пытались доугадать, то что не получается решить. Разумеется, не он один задачи именно решает, просто он достаточно хороший пример программиста который критично относится к решениям которые пишет. Этот абзац так, к слову, прямого отношения к вашему посту он не имеет
спасибо, о себе я уже узнал достаточно =)
2)Не надо, по-моему НЕЯСНОСТЬ условия делает задачу, простую с технической стороны, интересной. Не писать же прямо в условии, что нужно проверить связен ли граф и равно ли кол-во вершин кол-ву ребер.
3)Ctlr + "-" в помощь)) И нижних подсказок было достаточно для понимания. Вообще задача очень удачная, я лично не догадался просто проверить связность и количество вершин и ребер, а пустил дфс и проверял кол-во циклов и связность.
Да, и, конечно, вы будете правы, минусуя этот комментарий с мыслью: "Да ну и хрен с тобой, подумаешь, невелика потеря". У нас же тут демократия. Тьфу.
Так что очень здорово, что Саша добрый и наверняка продолжит проводить свои контесты несмотря на изливающиеся на него потоки неадеквата. Почему требования сухости условий - неадекват? Понятия не имею. Вы сами так решили, заплюсовав мой коммент. В ваших действиях, ув... кхм, нет... короче, члены сообщества... так вот, в ваших действиях посему наблюдается явное противоречие. Но с ним вы уже сами разбирайтесь.
автор одной из них точно OBepkJIokEP, авторства других не помню, но они точно есть
Саша добрый, пфф =) дело в том, что я заинтересован сделать контест такой, про который 90% скажут, что это "офигеть как круто", а 10% скажут, что это "долбаный отстой и параша", чем 100% скажут "вроде норм"
у контеста есть показатель — число в левом нижнем углу поста, и его величина перебивает все существующие топики ненависти и гнева ;)
(Хотя, впрочем, если в данном случае "мне всегда нравилась" - это не сарказм, то мой вопрос, конечно, неуместен.)