Архив форума

Подскажите, пожалуйста, идею как решить задачу 1447 (Сеть портшлюзов) с тимуса? Какой-то хитрый поиск минимального покрывающего дерева?

Беспардонно содрали идею задачи с чемпионата Питера прошлого (или позапрошлого?) года. Его (с тестами и решениями) можно скачать и посмотреть, как решается подобная задача...

А не подскажешь, где можно все это скачать...

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

Я думаю, могу поручиться за весь оргкомитет олимпиад по программированию УрГУ, что мы никогда не сдираем идеи чужих задач. Тем не менее, коллизии возможны, поскольку помнить условия всех задач, доступных в олимпиадных кругах по всему миру на всех доступных онлайн серверах, IMHO, просто нереально.

К слову, на моей памяти уже трижды возникала ситуация, когда на тех или иных олимпиадах (NEERC и даже финал ACM ICPC) использовались задачи по формулировке дословно совпадающие с идеями, которые на тот момент лежали у нас в копилке. А в одной из новосибирской олимпиад подобная ситуация была на двух(!) задачах из комплекта. Тогда даже проверяли собственную систему хранения задач на утечки.

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

Да ладно :) В чём, собственно, идея? Формирование критерия и дихотомия? Да таких задач миллион.

Даже нас (Timus Top Coders) обвиняли в неоригинальности задач. При нынешнем суммарном объёме всех онлайн-архивов... Вот устроишь контест международного масштаба на собственном проблемсете - и узнаешь, сколько задач, казавших тебе оригинальными, ты "спёр".

А вообще нет ничего удивительного в том, что одна и та же идея может прийти в головы разным людям.

"Даже нас" .... :)
Вот проведёте Timus TopCoders Contest 24, тогда и посмотрим ;)

Почему обязательно "спёр"! В родственной игре "Что? Где? Когда?" автора за боян бьют канделябром не потому, что он якобы "спёр" вопрос, а потому, что играть такой вопрос ну очень неинтересно и морально неприятно. АСМ выросло настолько, что здесь начинается то же самое. Решать известную задачу просто скучно. Поэтому в ЧГК авторы перед тем, как включить вопрос в пакет усиленно проверяют его на "свеченность", запуская Гуглы и пробегаясь по онлайн-архивам. И в АСМ, видимо, надо делать то же самое (желательно, опрашивая при этом ветеранов, не боян ли задача). А то обид потом не оберёшься. Замечу также, что ИМХО не стоит писать про "новизну и оригинальность идей всех задач контеста", поскольку этого уже никто (даже Вы :)) обеспечить не в состоянии.

К тому же, как вы помните, я похвалил вас за интересные гробы.

И как предлагается проверять идею задачи на засвеченность? Сказку-то ведь можно натянуть любую. Тут никакой гугл не поможет.

Хотя бы поспрашивать народ. Например, увидев http://acm.timus.ru/problem.aspx?space=1&num=1515 любой из людей, бывших в Петрозаводске сказал бы, что это ну сильная и новая свечка. Хотя задача неплоха. Если делать олимпиаду для школьников, так стоит поспрашивать новоиспечённых первокурскников, не видели ли они такие задачи.

Хотя, конечно, задача не из лёгких. Я же так, теоретизирую.

А почему столь высокомерное "даже"? Хоть последний чемп разобрать:
1. Налоговые операции - ну можно с натяжкой назвать авторской
2. Зиниум - это, товарищи, классика жанра, и на новую задачу никак не тянет. Метод решения: зайти на википедию, наброть в поиске "n queens puzzle" и наслаждаться жизнью!
3. Басня о лимоне - вообще бородатая задача
4. Национальный парк - тоже классика геометрии, особенно для читавших Препарату и Шаймоса
5. Финансовая реформа - свеча, да еще какая
6. Ностальгия - авторская, но легкая
7. Свобода выбора - можно назвать авторской, но новизной не блещет
8. Джедайский ребус - хорошая задача, и тянет на авторскую
9. Формула 1 - тоже борода, свой урожай неакцептов берет только гробовыми ограничениями на инпут
10. Империя наносит ответный удар - то же что и 9.
11. С натяжкой можно назвать авторской.

Итого задач, который можно было бы назвать авторскими со светлыми идеями 1, 2, ..., я насчитал 5 штук, т.е. меньше половины. И причем здесь "даже" в цитате :?: :?: :?:

2 Александр Клепинин:
Если "беспардонно содрали" Вас задело, приношу свои извинения. Просто действительно плохо, когда одна из самых сложных задач тура оказывается со свеченой идеей. Если свечки - легкие задачи (как про домино в последнем чемпе Урала) - это еще ничего, если одна сильная команда их видела, а другая нет, то обе ее решат, и никому хуже не будет. А вот если "засвечена" одна из самых сложных задач проблемсета (что и было с задачей про портшлюзы) - это уже очень плохо. Команды, которые ее видели, быстренько решат, а другие, может быть, не менее сильные - нет. Как понимаете, на объективность результатов сей факт влияет очень сильно. Поэтому я, собсно, и возмутился. У меня есть и другие примеры, когда задача с той же идеей появлялась на чемпионате Урала через год после ее появления на NEERCе или чемпионате мира (возьмите хотя бы задачу Pass Licenses с последнего чемпионата Урала). Да примеры, я думаю, Вы и сами подберете, мне писать лень. Стесно, такая практика не оставляет меня равнодушным к происходящему.

К сожалению, Vedernikoff Sergey демонстрирует полное непонимание процесса составления проблемсета.

Спорить я не буду, поскольку каждый имеет право на личное мнение. А моё личное мнение - всякие (довольно высокомерные, да? ;)) "ну можно с натяжкой", "новизной не блещет" и т.д. - просто LOL :lol:

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

Все задачи полностью оригинальны. Мы их ниоткуда не спёрли. Ни одной из этих задач не было в архивах Timus Online Judge - это основной критерий. Проверять содержимое других архивов у нас нет ни времени, ни желания. А всякие сборы в Петрозаводске и прочие локальные контесты, в которых участвует 1% от общего числа участников тем более.

Мы поощряем тех, кто читает книжки по программированию и знаком с классическими задачами, структурами и алгоритмами, будь то N-queens problem, суффиксные деревья, венгерский алгоритм или что-то другое.

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

Такова политика команды Timus Top Coders, и очень сомнительно, что она изменится к следующему контесту. Если кого-то что-то не устраивает - проводите свои контесты ;)

К сожалению, Dmitry Kovalioff демонстрирует полное непонимание сути предъявляемых к нему претензий :)

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

Позволю себе вставить свое мнение.
Dmitry Kovalioff, я в принципе поддерживаю вашу политику проведения контестов и рад возможности попрактиковаться в решении задач на суффиксные деревья, например. У Вас интересные задачи и сбалансированные проблемсеты.
Но при этом совсем непонятен Ваш пафос, с которым Вы и рекламируете контесты Timus Top Coders, и расхваливаете их потом. Думается, что хороший контест и так похвалят. Да и не в похвале суть: достаточно просто смотреть на количество участников и молча делать свое доброе дело. Будьте скромнее, и люди к Вам потянутся :)