Блог пользователя pkhaustov

Автор pkhaustov, 13 лет назад, По-русски
В последнее время для меня все актуальнее становится вопрос о том, какими же все-таки должны быть условия задач? Что должно содержаться в этих условиях и как это правильно сформулировать? Как избежать хотя бы малейшей двусмысленности?
При создании контеста я всегда считал составление условия самой сложной задачей. Всегда старался избегать написания условий задач, в которых нельзя обойтись коротким и понятным условием. Если при разработке контеста я читаю чужое условие, то я стараюсь максимально придраться к нему, чтобы ни у кого из участников не возникло ни малейшей двусмысленности. Я иногда рефлекторно защищаю свои (порой изначально двусмысленные) формулировки. Но, как только немного остываю, сажусь и стараюсь исправить все замечания до последнего. А после того, как исправляю, спрашиваю стало ли понятно теперь.
Часто бывает так, что ужасно хочется приплести к условию задачи какую-то жутко забавную легеду или, как зачастую кажется авторам, подходящую как нельзя кстати именно к этой задаче. При написании условия задачи надо всегда помнить, что легенда может увести участника от самой сути задачи настолько далеко, что лучше бы ему просто увидеть примитивное условие на языке математических обозначений. Часто легенды плохо согласуются с оригинальным пониманием условия, что сбивает с толку и заставляет участника непроизвольно додумывать какие-то дополнительные ограничения.
Если участнику непонятно какое-то обозначение из условия или как в примере получается именно такой ответ, то всегда можно написать примечание, которое снимет все вопросы. Тем не менее, примечание должно быть лишь вспомогательной составляющей условия. Условие без примечания не должно быть неполным и должно содержать все необходимые ограничения.
Очень важно заранее увидеть страницу, которую будет видеть участник. Некоторые важные элементы условия могут оказаться незаметны в конечном итоге из-за своего геометрического положения на листе бумаги или на экране монитора.
Важных пунктов при составлении условия - великое множество. Сложно перечислить все важные пункты, да я и не буду пытаться перечислить их все. Более того, всех пунктов я, наверное, и не знаю.
Всю эту тему я решил поднять из-за недавнего спора с одним программистом (если захочет, сам назовет себя) на тему того почему же я изначально неправильно понял условие задачи, которую мне недавно довелось порешать. Я погорячился и даже написал автору задачи (в индивидуальном порядке), что это условие написано некачественно. Лишняя агрессивность была вызвана тем, что я позорно слил этот раунд, и во мне бурлил негатив. Эту задачу я все-таки сдал во время раунда, но потратил на нее намного больше времени, чем потребовалось бы, если бы я изначально правильно понял формулировку. Спасибо тем, кто отвечал на вопросы, за то, что пояснили тест из примера. Это дало мне все-таки понять ту самую формулировку, которую подразумевал автор.
Для начала я полностью поясню ситуацию... Когда я прочитал условие, то сразу же обратил внимание на следующее предложение: "...Ктулху назовем такой неориентированный граф, который может быть представлен как набор из трех или более корневых деревьев, корни которых соединены простым циклом...". Я подумал, что конечно-же имеется в виду цикл, состоящий из трех и более вершин. Но зачем вот это "трех или более". "А! Наверное подразумеваются только деревья, состоящие из более, чем одной вершины" - подумал я. "Ну да, все логично! У Ктулху такая морда с висящими из нее штуками. Менее трех таких болтающихся из морды штук у Ктулху - не православно, вот отсюда и такое ограничение!" - вот, что я подумал следом и принялся набивать код решения именно такой задачи. Написав, я заметил, что на тесте из примера мое решение выдает не такой ответ. И действительно, если удалить цикл из него, то остается только два дерева. И тут в голове начинаю перебирать как же надо понимать условие: Может быть можно считать поддеревья отдельными деревьями? Может быть можно считать одинокую вершину тоже деревом? Я задаю вопрос жюри и свет проливается. Причем ответ был очень подробным пояснением, откуда же берется три дерева в тесте из примера. Да, теперь задача действительно решается одним дфс-ом, подумал я. В моем решении я просто убрал if на то, чтобы деревьев с количеством вершин больше 1 было не менее трех и отправил. Больше я к этой задаче не возвращался.
Позже, все кому я говорил о том, как много времени я потерял на этой задаче (таких было не так уж и много) тыкали меня носом в различные вещи. Кто-то в то, что я не додумал условие из теста из примера. А между делом, он и сам обратился к тесту из примера, чтобы разобраться. Кто-то винил меня в том, что я не прочитал примечание, а, соответственно, прочитал не все условие.
Лично я считаю, что условие должно быть таким, чтобы не требовалось разбираться в тесте из примера, чтобы понять, что же от меня требуется. А о существовании примечания я и знать не знал. Видимо, авторы не заметили того, что оно находится под двумя огромными тестами. А по скроллбару сложно ориентироваться, ведь в условии находится еще огромная (но не самая полезная) картинка. Как выяснилось, пояснение того, что дерево из одной вершины все же надо учитывать, находилось именно в примечании. А условие про "трех и более" означало тривиальный для меня факт того, что циклы не могут содержать менее трех вершин.
Человек, с которым я спорил, утверждает, что и без примечания все понятно и однозначно. Этот человек решил эту задачу, не задавая вопросов жюри, то есть понял с первого раза условие правильно. Именно он сказал, что я [начало цитаты] не полностью прочитал условие [конец цитаты].
Как мне показалось, ответ, который дали мне, был использован и ранее. Я могу ошибаться, но по-моему я не единственный из тех, кто задал такой вопрос.
И тут, собственно, остается много вопросов, по которым я бы хотел услышать мнение общества:
1) Было ли условие (без учета примечания) однозначным для понимания для Вас?
2) Можно ли выносить то самое ограничение на количество вершин в корневом дереве в примечание или же это часть условия? (опять же относительно Вашего мнения)
3) Достаточно ли заметны для Вас примечания под "примерами тестов" при больших высоте страницы и размерах этих самых примеров?
  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
1) Из-за легенды я сделал некорректное предположение о том, что граф по условию является связным, из-за этого словил WA. Ответ на вопрос: нет, однозначным не было.
2) В-принципе, примечания могло бы вообще не быть, и задача тем не менее была бы полной. Ответ на вопрос: выносить можно.
3) Я не считаю эти примеры слишком большими. Ответ на вопрос: да, достаточно заметны.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тут, конечно, зависит от характеристик монитора. Я участвую с ноутбука диагональю 15`. Разрешение 1280 на 800. Меньше, чем большинство современных мониторов. Условие и без картинки бы заняло у меня весь экран.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится
    1) Вроде из легенды никакой связности не следует, везде написано "дан граф"
    По остальным пунктам согласна.

    По-моему, нормальное условие.
    Я, правда, поняла задачу только тогда, когда пошла взламывать чужие решения.
    Была удивлена :) Но не считаю свое неумение читать багом автора.

    Если задача чем и плоха, то тестами - мое неверное решение (на два экрана) прошло, хотя тест, который его ломает, вполне очевидный.
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Я изначально понял условие так же как и ты, потом нарисовал тест из примера и тоже не понял откуда там 3 дерева и потом только дошло когда прочитал примечание к задаче.
1) Нет
2) Выносить можно, но где-нибудь в начале условия отметить факт того, что определения терминов употребляемых в условии можно найти в примечании.
3) Примечания заметны в том случае, если начинаешь рисовать и изучать тесты. В случае если бы это была сложная задача, то наверняка все без исключения изучали бы тесты и без труда бы заметили и примечание. А в случае простой - не факт. Есть вариант также расположить примечание до тестовых примеров, или вообще до описания формата входных данных - так будет трудно не заметить.

13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
1. Да. Даже если бы я вычитывал это условие, скорее всего, проскочил бы это предложение безо всяких альтернативных пониманий. Хотя и кажется, что можно сказать как-нибудь лучше (у меня, например, до самого конца условия висел вопрос “зачем в этом предложении деревья корневые?”).

2. Да, можно. Это стандартное определение дерева. Формально в этом месте условия нет оснований додумать, что в дереве должно быть строго больше одной вершины. Проблема, как мне кажется, не в этом, а в том, что можно это предложение прочитать по-другому: вместо “из >= 3 деревьев, все корни которых соединены в цикл” прочитать “из >= 3 деревьев, корни которых соединены циклом, возможно, с добавлением вершин степени 2”. А из-за этого уже приходится что-то додумывать.

3. Да. При чтении условия я сначала смотрю, что в нём есть (собственно условие, формат ввода, формат вывода, картинка, два теста с ответами, примечания). Это (а также беглый взгляд на примеры, а потом на формат I/O) заодно помогает понять, стоит ли вообще читать именно сейчас именно эту задачу. А потом при чтении стараюсь не пропустить ни один из этих элементов. Хотя бывает, что читаю не с начала (например, когда кажется, что в первых нескольких абзацах только легенда) или заканчиваю читать раньше, считая, что уже всё понял (например, в TopCoder Easy).
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Я сразу чётко и правильно понял условие, так что можно сказать, что оно для меня было однозначно.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

1) Нет, запнулся на том же месте

2) Нет, наверно лучше писать в условии

3) Скорее да, все-таки примечания идут сразу после условий.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
1) Yes
2) I think, it's a part of statement.
3) No, moreover, if you didn't write about them, I'll even notice it D:
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
1). Этот момент остался непонятным после прочтения текста, но когда я посмотрел просто в тесты, стало ясно.
2). Это примечание. Другое дело, что примечания, по-хорошему, должны, как и в топкодере, находиться перед тестами. А то, что тут называется примечанием - это пояснения к тестам на самом деле.
3). Ну да, иногда приходится промотать вниз, тоже пишу с ноута. Но не вижу в этом ничего очень ужастного.

А правило, по-моему, должно быть следующее: Условие = Легенда + Формат данных + Тесты + Примечания + Аннотации. И вот Условие должно давать четкий ответ на то, какой должен быть ответ на любые входные данные. А если не включать Тесты в условие, то они только для успокоения нервов участников - ценно для участников, но бесполезно для условия:)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    но когда я посмотрел просто в тесты

    А я вот думаю. Может вместо зелёного Ктулху в условии стоило привести чертёж графа из примера... Тогда бы сразу было над чем задуматься...
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        Я как бы увидел в определённые моменты себя со стороны. Я тоже "страдаю" любовью к картинкам в условиях задач. Иногда желание привязать легенду к картинке преобладало над здравым смыслом и возникали моменты в необходимости неоднократного толкования авторского понимания условия задачи.
         Видимо и тут страсть к прекрасному в виде этого симпатичного создания Ктулху возымела своё.
         По большому счёту ничего страшного не произошло.
         Есть даже положительный момент - многие авторы задач (и я в том числе) для себе определённые выводы сделали.
         Так что автора этой задачи хотелось бы поблагодарить и за корректирование моего авторского взгляда на формулировку условий задач.
13 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится
во-первых, спасибо за статью :) очевидно, что мне как автору есть куда совершенствоваться =)

я хотел бы прояснить несколько моментов

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

в условии есть фраза, уже описанная в статье: "Ктулху назовем такой неориентированный граф, который может быть представлен как набор из трех или более корневых деревьев, корни которых соединены простым циклом"

из этой фразы прямо следует, что Ктулху — это три или более дерева с выделенными корнями, корни этих деревьев соединены простым циклом-кольцом — верно? а поскольку деревьев три и более, корни которых завязаны в кольцо, то это кагбэ намекает, что кольцо никогда не выродится в какое-нибудь дерево из двух вершин или одинокую вершину — снова всё логично получилось?

объясни, пожалуйста, более подробно логический переход в твоих рассуждениях от "трёх и более деревьев" к "речь идёт о деревьях, в которых более одной вершины"

по поводу примечаний

в примечаниях этой задачи содержались исключительно тривиальные утверждения, с которыми может быть не знаком только новичок СП (например, что дерево может из одной вершины состоять)
  • 13 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится
    Саш, для меня было очевидно, что цикл имеется в виду только из трех и более вершин. Отсюда возникала непонятка о вот этих "трех или более". Если в цикле не менее трех вершин, то менее трех деревьев вообще не возможно. Значит, такое ограничение при деревьях из одной вершины не имеет смысла. Отсюда возникали дальнейшие предположения, а легенда о Ктулху только помогала уйти в ту сторону.
    Этого всего могло бы не быть, если бы ты написал "цикл должен содержать не менее трех вершин". Такая формулировка лишена малейшей двусмысленности и даже не требует избавиться от легенды. Но это скорее просьба исправлять такие предложения тем, кто вычитывает и исправляет условия. Автору очень сложно заметить изъяны именно в своем условии. Если он написал условие именно так, то это значит, что ему это предложение кажется однозначным и недвусмысленным.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    что кольцо никогда не выродится в какое-нибудь дерево из двух вершин или одинокую вершину — снова всё логично получилось?

    Ну учитывая что ниже в условии написано "граф не содержит петель и кратных рёбер" это довод в пользу "логичности" довольно шаткий :D
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    > в примечаниях этой задачи содержались исключительно тривиальные утверждения

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Оффтоп по третьему пункту: вчера писал snss и задачу F увидел только на 40ой минуте контеста.  
13 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

UPD: пока ехал в метро решил сократить мысль. ;-)

Тут ещё картинка наверное повлияла на восприятие. Читаем условие про "цикл с 3 корневыми деревьями" и сразу понимаем "ага, Ктулху он значит такой, кругленький и у него 3 или больше конечностей".

Поэтому даже после того как я заметил что первый тест представляет Ктулху с 2 конечностями и минут 15 потратив на перечитывание условия, я так и не вник в суть примечания и сказал себе "а ну его в качель, время только тратить - не корову ведь разыгрывают!"

Думаю, если цель автора была нарочно тренировать внимательность участников, то эта цель достигнута. А если "эффект Ктулху" получился случайно, то лучше такого не допускать. К тому же, учитывая что условие можно было сократить до пары строчек, и учитывая что часть соревнующихся читают условие на языке не родном ни для них, ни для автора, ни для переводчика.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится
    большущий жирный минус за последнее предложение по поводу условия в пары строчек

    второй большущий жирный минус (который я бы с радостью поставил, если бы смог) за изменение текста комментария на 100%, тут даже никакое "UPD" не спасает
    • 13 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится
      а чем тебе не нравятся условия в пару строчек? мы тут переводами рассказов занимаемся или где?
      • 13 лет назад, # ^ |
          Проголосовать: нравится -16 Проголосовать: не нравится
        мне кажется, что это тема отдельного холивара ;)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +30 Проголосовать: не нравится
      Я очень люблю когда задача легко формулируется. Задачи с небольшим условием могут быть и простыми и сложными, для решения такой задачи может "не хватить места на полях книги" :). Приятно сразу понять задачу и заниматься её решением, а не чтением 4 страниц текста сгенерированного больной фантазией автора.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ну всё, снова обосрали с ног до головы =)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А что, хотелось чтоб хвалили и носили на руках, и дали много денег и памятную доску?

          Я так понимаю что если уж писал "длинно, со вкусом и слегка полуприподзапутанно", то был к этому в душе готов. ;-)

          Задачи неплохие - в этом смысле респект. А формулировка (имхо) подкачала.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +24 Проголосовать: не нравится
            не надо доводить до абсурда)

            да, мои условия требуют навыка "фильтрования бреда"

            однако, надо быть, извините за выражение, идиотом, чтобы пытаться понять условие из собственного разыгравшегося воображения и картинки, на которой изображён зелёный человечек, вместо того, чтобы разобраться с единственным формальным предложением в условии задачи, которое даже начинается со слова "формально"
            • 13 лет назад, # ^ |
                Проголосовать: нравится +2 Проголосовать: не нравится
              Ладно-ладно, я идиот, согласен...

              Но неужели, как автору, приятно чтобы ещё до соревнований появлялись шутки вроде:
              о подготовке по книге рассказов Лескова

              А после того начинались рассуждения о том идиоты ли те, кто читали задачу или те кто её писали?

              Мне кажется что вы сами предпочли бы обойтись без таких моментов. Или я не прав и в этом самый цимес?

              Напоминает анекдот: А команда США в этот раз на соревнования по фигурному катанию не поедет, вместо них будет участвовать сильная команда американских юристов.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +24 Проголосовать: не нравится
                скажу за себя

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

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

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

                не вижу ничего обидного в шутке Паши Хаустова, я даже плюсанул :)

                в любом случае, если мой никнейм присутствует в списке авторов задач - жди беды :D благо, авторы известны до начала раунда, поэтому особо вредным ненавистникам длинных условий могу предложить посдавать задачи в режиме дорешивания, а не мучать себя и других ;)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +11 Проголосовать: не нравится
                  Не обращайте внимание на мелочи и продолжайте писать такие условия, как Вам хочется.
                  Просто тема оказалась для многих интересной во многих и разных аспектах и каждый хоть немного, но, как мне кажется, всё-таки изменил (подкорректировал),   свои взгляды на это.
                  Это нормальный процесс расширения рамок взаимопонимания, по моему разумению.
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  ====================================================================
                  просто они не участвуют в этих холиварах - незачем
                  ага, точняк =) это я как человек из второй категории говорю ;)

                  однако, надо быть, извините за выражение, идиотом, чтобы пытаться понять условие из собственного разыгравшегося воображения и картинки, на которой изображён зелёный человечек, вместо того, чтобы разобраться с единственным формальным предложением в условии задачи, которое даже начинается со слова "формально"
                  абсолютно в точку, браво, Алекс! всё по местам расставил, ни дать ни взять =)
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +8 Проголосовать: не нравится
                не сочти за оскорбление, пожалуйста :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится -15 Проголосовать: не нравится
        "Поля книги слишком узки" - да, это классный и классический пример... Особенно если учесть что решение от 1995 года по-моему такое толстое, что на "удивительную простоту" обещанную автором не претендует... ;-)
    • 13 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится
      Да мне в общем наплевать на минусы "большущие и жирные"... На здоровье... :D

      Задача действительно сводится к тому что "Ктулху это связный граф с единственным циклом, причём длина цикла > 2" и никаких корневых деревьев (и даже петли / кратные рёбра уже не нужно оговаривать).

      Если же была цель "малость запутать" то да, условие из 2 строчек не годится.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вот это очень правильное замечание, все поняли что деревья это конечности, а я, как и многие другие высказавшиеся, не мог понять считать ли конечностью(деревом) вырожденное корневое дерево из одной вершины. Мое решение выделяло цикл, и затем уже пускало дфсы, которые считали количество деревьев и прочую фигню проверяли. Я считаю что условие непонятное, и бесполезно с этим спорить. Очень многие участники не могли понять его правильно без ответов жюри на вопросы - это факт.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится
    Ага, а еще задачи можно формулировать сразу в духе: реализовать динамику по трем параметрам с такими-то переходами - или поток на таком-то графе. А то, что в условии про это ничего обычно не говорят - козни авторов^-^. (Это на тему правки 1).
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Конечно, это тоже крайность. ;-)

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

      Я смотрю на это с точки зрения промышленного программирования, где заказчик или системный архитектор сам заинтересован в том чтобы программист его понял. С точки зрения спортивного программирования конечно всё может выглядеть иначе.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

1) Да.
2) Можно.
3) Достаточно.

А если возникают проблемы из-за непонятностей в условии - это участнику повод совершенствоваться, а не пинать автора. Автора можно пинать, разве что если участник задал вопрос, а ему ответили неправильно.
Аргумент у меня за такую позицию стандартный: на финале ACM у тебя будет условие на страницу, где в первых двух абзацах будет, возможно, только одно значимое для решения слово, причём это будет слово thousand. И если кто-то опять скажет, что "не одним ACM мир живёт", я не стану с ним спорить, только укажу, что Павел в статье, кажется, реквестирует личное мнение.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если на финале убрать легенды и сформулировать задачи формально, то в большинстве случаев получится невнятная муть, которая разве что в кошмарном сне приснится.

    До сих пор помню, как на нашем финале в какой-то задаче надо было распарсить строчку. Мы ее распарсили, но сэмпл не проходил. В середине двух страниц текста обнаружилась фраза: строчка в файле может быть записана как в прямом, так и в обратном порядке. (!!!)
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
1. Без примечаний условия было не понятным для меня, но я считаю виноватым только себя так как понятие корневого дерева это общеизвестная теория. 
2. Мне было бы понятнее если  бы оно было над тестами.
3. заметны но в условиях ограниченности времени мне показалось что я правильно понял условие и без них.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
> "ага, Ктулху он значит такой, кругленький и у него 3 или больше конечностей"
Я тоже понял условие неправильно и тоже написал решение, проверяющее невырожденные деревья.
Затем не прошел первый тест, посмотрел в примечание...

И да, задачу я так и не сдал, т.к. забыл проверить связность графа. Интересно, 46 тест, на котором у меня упало, был добавлен из взломов? (всего их 47)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    в 14-м тесте граф тоже несвязен, так что, думаю, дело не только в этом =)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Несвязен, но там два цикла. Мое решение видит один из этих циклов, удаляет из него одно ребро, ищет еще циклы, снова находит и успешно выводит NO.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        У меня решение упало на 46-ом тесте. Оказывается нужно было посчитать количество компонентов связности. И если их было больше одного, то "NO"
13 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится
Имхо, лучше всего, когда то, что требуется в задаче, понятно из (короткого) описания форматов входа/выхода. При этом само условие может быть сколь угодно длинным. При таком подходе и волки сыты (удовлетворён графоманский зуд авторов), и овцы целы (участники, которым не очень интересна легенда, могут её пропустить).
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Выскажу пару тезисов по поводу всего этого дела.

1. Понимание про то, что в корневом дереве должно быть больше одной вершины я считаю на совести тех участников кто так понял. Никаких объективных предпосылок к этому не было. А тот факт, что такое понимание отсекалось на довольно ранней стадии (сэмплы из условия) говорит о том, что условие составлено довольно хорошо. Хотя возможно это так случайно получилось :)

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

3. Вопрос про то должны быть условия короткими или длинными да с легендой обсуждался уже много раз, и я понял так, что однозначного мнения по этому поводу нет. А значит нет объективных причин раз за разом после матча (а в этот раз все началось еще и до матча) жаловаться на длинные условия.
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    Понимание про то, что в корневом дереве должно быть больше одной вершины я считаю на совести тех участников кто так понял

    А почему кстати вырожденное дерево с одной вершиной - это дерево, а вырожденный цикл из единственной вершины - это не цикл?

    UPD: это не наезд, это просто попытка понять, почему TopCoder (как мне кажется) старается избегать специальных терминов в формулировках (даже таких простых как "натуральное число").
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Потому что есть определния этих понятий в теории графов:
      Дерево - связный граф на n >= 1 вершинах с (n - 1) ребром ( дугой).
      Простой цикл - это простой путь, длины не менее 1, у которого начало и конец совпадают. (Простой путь - путь, который содержит лишь попарно различные вершины).
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

        Где ссылка на источник?

        Это "определения из теории графов от jte" или "определения из теории графов которые знает каждый идиот а тот кто не знает, тот точно идиот"?

        В ваших определениях сквозит что "простой путь" тоже может состоять из одной вершины. И цикл (петля) может состоять из одной вершины. Ну почему же такое неравноправие и цикл в отличие от пути или дерева должен ещё и ребро содержать?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          1) "Замкнутый маршрут называется простым циклом, если 
          все его n вершин различны и n ≥ 3  " . - Хараре,"Теория графов", страница 27,  / Пер. с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. 

          2) "Дерево — это связный ациклический граф. "  - оттуда же, страница 48.


      • 13 лет назад, # ^ |
          Проголосовать: нравится -9 Проголосовать: не нравится
        Самое "свежее" определение дерева (С.М.Окулов "Дискретная математика. Теория и практика решения задач по информатике")

         Граф без циклов называют ациклическим. Дерево - это связный ациклический граф.
        Теорема. Для графа G = (V, E) (|V| = n, E = m) следующие утверждения эквивалентны:
        1. G - дерево.
        2. G - связный граф и m=n - 1.
        3. G - ациклический граф и m = n - 1.
        4. Любую пару несмежных вершин соединяет единственная простая цепь.
        5. G - ациклический граф, и если какую-либо пару несмежных вершин соединить ребром x, то граф G + x будет содержать ровно один простой цикл.
        с. 130 выше упомянутого учебного пособия.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Ну... Графы определим по Окулову... А "натуральные числа" по кому определять? С нулём или без?

          Не, тут дело в другом. Не в определениях а в сути. Некоторые алгоритмы на графах критичны именно к тому, является ли он ациклическим. Причём конечно в смысле циклов с 1 или больше ребром. Здесь "правильное определение" подсказывает сама практика.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        К слову о терминах:
        Треугольники бывают вырожденными. Векторы бывают нулевыми. Деревья могут состоять из одной вершины. В некоторых задачах такие частные случаи исключаются, в некоторых они не исключены. В первом случае пишут о том, что такие элементы в расчет брать не надо. А во втором хорошо бы писать что-то вроде "в том числе и деревья состоящие из одной вершины" (например). В этой задаче это было написано, но в примечании. Из-за специфики оформления, я этого примечания не видел вообще.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится
          Сравнивать вырожденные треугольники и нулевые вектора с графом с одной вершины мягко говоря не совсем корректно. В первом случае объекты специально выделяются, т.к. они теряют важные свойства. Во втором же все нормально. Вы можете привести пример книги по графам где граф с одной вершиной специально выделяется? Я таких не припомню. Да и не имеет это смысла. Вырожденный треугольник я бы скорее сравнил с графом с нулем вершин.
    • 13 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится
      Вот вы написали сообщение из нескольких строчек, а я вообще не могу понять о чем вы говорите, представляете как не легко авторам задач? :)

      Словосочетания "вырожденный цикл" и "вырожденное дерево" я вообще вроде впервые вижу. Я понятия не имею почему одно дерево а другое не цикл, если хотите называйте одно не деревом. а другое циклом, никто не запрещает. И к чему этот вопрос я тоже не понял. На топкодере, да и здесь действительно стараются избегать специальных теминов. Опять же не понятно зачем вы упомянули эту прописную истину :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится
        Это я упомянул к тому, что если цикл может содержать 1 вершину и 0 рёбер, то Ктулху может выглядеть состоять из 2 рёбер соединяющих 3 вершины *-*-* (будет цикл без рёбер от которого растут три дерева - в каждую из вершин). А определение цикла в задаче дано не было. :D
        • 13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Определение простого цикла было дано в примечании. И правильно, что в примечании, а не в тексте условия. У большинства участников вопроса о том, что такое цикл, не возникло, я надеюсь.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

            Точно, определение было:

            Простым циклом назовем множество из v вершин, которые можно пронумеровать так, что будут существовать ребра только между вершинами с номерами 1 и 2, 2 и 3, ..., v - 1 и v, v и 1

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

            У большинства участников вопроса о том, что такое цикл, не возникло, я надеюсь.

            Конечно не возникло. И про корневое дерево тоже вопросов не возникло, как видим - все были достаточно уверены в своей точке зрения. :D
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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


              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Это относится к тем случаям, когда автор(ы) задач не участвует в том же рейтинге, что и этот "проблемный" олимпиадник.

                В нашем же случае, скажем, KhaustovPavel, Alex_KPR и it4.kp находятся довольно близко друг к другу в общей таблице, а потому лучше таких случаев было бы избегать (имхо).
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Может потому, что у большинства эта точка зрения была изначально правильная?)
              На самом деле, это неприятный вопрос, потому что в большинстве изданий даже нету определения графа и встречаются фразы а-ля "граф - это граф". Принято считать, что цикл по определению невырожденный, а дерево может состоять из одной вершины.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится
                (ну мы точно не знаем насчёт большинства - сколько процентов поняли так, а сколько иначе)

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

                А то что с задачей возникло определённое непонимание у тех участников для которых соревнования действительно важны, например у Павла (это небось его со 100-какого-то на 200-какое-то место откинуло, нет?) - это жаль, конечно.

                И согласитесь - любой уважающий себя спортсмен предпочитает выигрывать не за счёт того что кто-то другой срезался неправильно поняв задачу... Ну мне так кажется...
            • 13 лет назад, # ^ |
                Проголосовать: нравится +11 Проголосовать: не нравится
              Из условия следовало, что в цикле в данном случае должно быть хотя бы три вершины.

              С корневым деревом тоже все было понятно: в примечании было определение (общепринятое), на примере можно было убедиться, что используется именно это определение (а не то, что, вероятно, только что придумано участником по прочтении легенды).
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Цикл не может содержать 1 вершину и 0 ребёр - Вы, наверное, хотели сказать, что 1 вершину и 1 ребро, т.е петлю?  - см. определение выше, так как цикл - это путь ненулевой длины.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну не... как раз и вопрос был, откуда берётся такое определение. Почему единственная вершина без ребер вообще - это не цикл. Почему путь может быть нулевой длины а цикл нет.

            Хотя тут надо заметить что путь соединяет N вершин с помощью N-1 ребер, а у цикла количество ребер и вершин совпадает.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

1)Да

2)Да

3)Да

13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
ИМХО, вот идеальный пример идеальных по форме условий. А все легенды -- это для графоманов, которые не понимают, как задача может быть прекрасной без страницы унылого текста.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Илья, вы не учитываете разницу между форматами соренований на олимпиадах по Математике/Физике и соренованиями по Информатике. К условиям здесь применяются совершенно различные требования.

    Олимпиады по Математике и Физике, требуют нахождения ответа и строго его доказательства, поэтому задача формируется тоже строго - четко и однозначно. Если бы на олимпиадах по Информатике так же требовалось найти алгоритм решения и строго его доказать, то и условия писались бы соответствующие. Причем, более чем уверен, что с таким форматом популярность бы сильно снизилась. Условия задач окутаваются какой-то историей чтобы создать иллюзию блуждания по коридорам логики и разгадывания головоломок, потому что именно это приносит удовольствие. Если давать сухо, только суть, то соревнования превратятся в фарш фарс.

    А популярность олимпиады по Информатике, в случае если условия нужно будет доказывать строго, сильно снизится, потому что очень часто пропихиваются догадки, а не решения, более того, можно опробовать много догадок, и хоть один раз таки угадать. А если доказывать нужно будет строго, аудитория отвалится. Даже не надо ходить далеко, тот раунд который проводил Сергей Ведерников, та задача, где авторское решение оказалось неверно - сколько людей пытались ее сдать, причем уверен, многие пытались потому что какие-то примитивные догадки, были очень похожи на ответ, и проходили много претестов. И как мне кажется Petr эту задачу не пробовал сдавать потому что он пытался ее _решить_ а не угадать, но подходящего решения не нашел, и именно поэтому он единственный сдал E, потому что он ее _решал_ и таки решил, в то время как многие опять же пытались доугадать, то что не получается решить. Разумеется, не он один задачи именно решает, просто он достаточно хороший пример программиста который критично относится к решениям которые пишет. Этот абзац так, к слову, прямого отношения к вашему посту он не имеет

    • 13 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится
      Петросян, ты почему не в своем амплуа? Шутки где?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    http://www.codeforces.ru/blog/entry/2360#comment-49603

    спасибо, о себе я уже узнал достаточно =)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Хм, а ты считаешь, что весь твой вклад -- это длинные условия задач? :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    1. В четвертой задаче легенда есть.

    2. Ни разу не видел авторов, утверждающих будто длинная легенда делает задачу прекраснее. Всегда, когда говорят о красоте задачи, имеют ввиду именно ее чистую формулировку и решение, а про легенды обычно и не вспоминает никто.

    3. Легенды вставляются (в идеале) для того, чтобы помочь правильно понять условие, которое без легенды выглядит, как безумный набор символов.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Против таких легенд как в четвёртой задаче никто ничего и не имеет. Народу не нравится, что периодически приходится вчитываться в длинную графоманию автора, даже если она весёлая и интересная :) При составлении условий иногда хочется пографоманить, поэтому я и считаю вариант, когда формальный смысл понятен из последнего абзаца условия/форматов ввода-вывода, идеальным.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Люто, бешено плюсую третий пункт: разумная легенда может сделать задачу намного понятнее. Легенда не должна придумываться отдельно от задачи. Часто просто придумывают легенду, наполненную искрометным юмором и тонкой иронией, и абы как приделывают ее к задаче.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
1)Да, и связность тоже сразу была понятна.

2)Не надо, по-моему НЕЯСНОСТЬ условия делает задачу, простую с технической стороны, интересной. Не писать же прямо в условии, что нужно проверить связен ли граф и равно ли кол-во вершин кол-ву ребер.

3)Ctlr + "-" в помощь)) И нижних подсказок было достаточно для понимания. Вообще задача очень удачная, я лично не догадался просто проверить связность и количество вершин и ребер, а пустил дфс и проверял кол-во циклов и связность.
13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Читая комменты, я сделал для себя очень простой вывод. Раунда моего авторства здесь никогда не будет.

Да, и, конечно, вы будете правы, минусуя этот комментарий с мыслью: "Да ну и хрен с тобой, подумаешь, невелика потеря". У нас же тут демократия. Тьфу.

Так что очень здорово, что Саша добрый и наверняка продолжит проводить свои контесты несмотря на изливающиеся на него потоки неадеквата. Почему требования сухости условий - неадекват? Понятия не имею. Вы сами так решили, заплюсовав мой коммент. В ваших действиях, ув... кхм, нет... короче, члены сообщества... так вот, в ваших действиях посему наблюдается явное противоречие. Но с ним вы уже сами разбирайтесь.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    если я не ошибаюсь, то после каждого моего раунда создаётся подобная тема, где изливаются потоки ненависти =)

    автор одной из них точно OBepkJIokEP, авторства других не помню, но они точно есть

    Саша добрый, пфф =) дело в том, что я заинтересован сделать контест такой, про который 90% скажут, что это "офигеть как круто", а 10% скажут, что это "долбаный отстой и параша", чем 100% скажут "вроде норм"

    у контеста есть показатель — число в левом нижнем углу поста, и его величина перебивает все существующие топики ненависти и гнева ;)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Уверен, что большинство ставит плюс за контест до его написания, так что это не показатель.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
    Мне всегда нравилась манера людей выставлять других идиотами, а себя философом, ничего не делая для исправления, чтобы потом и дальше иметь возможность выставлять людей идиотами
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Для исправления чего? Или кого? О ужас, людей?!
      (Хотя, впрочем, если в данном случае "мне всегда нравилась" - это не сарказм, то мой вопрос, конечно, неуместен.)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я лично  вообще не хочу чтобы автор контеста что-то менял. Я люблю когда технически простейшая задача запутывается при помощи условия, это делает ее интересной. Скучно если в условии сказано: дан неориентированный граф, проверьте что в нем ровно 1 простой цикл цикл и что граф связен.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Одно дело когда легенда используется для усложнения задачи, другое - когда она используется для того, чтобы сделать условие менее понятным. Во первом случае сложнее решить задачу, во втором - понять.
13 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится
Вот к этой же теме относится и сегодняшний контест №81. Меня очень Напрягали такие большие условия, с кучей дополнительных объяснений. Может это по тому что я не играю в компьютерные игры. Мне было очень тяжело вникать в то что от меня хотят. Заранее прошу прощения у авторов. Я уважаю ваш труд и стремление и хочу сделать результаты ваших трудов ещё лучше.