Вчера в Гран-При ICL на четвёртом часу соревнований выяснилось, что задача F в предложенной автором формулировке и ограничениях не решается и авторское решение является как минимум неполным (а то и неверным).
Жюри Открытого Кубка приняло решение в связи с этим считать этап "условно внезачётным", уменьшив количество зачётных этапов для каждой команды (в зачёт идут 6 лучших этапов из 8 вместо 6 из 7 или 7 из 8). Таким образом, команды, результат которых из-за допущенной ошибки ухудшился, получают шанс компенсировать его на добавленном Гран-При. Команды же, показавшие достойный результат на данном этапе, всё равно получают некий "бонус".
Остаётся вопрос, что же делать с задачей F при подведении официальных итогов этапа.
Вариант первый — оставить "как есть". В пользу этого варианта — решение жюри Олимпиады ICL о награждении "по итоговой таблице", а также соображения относительно того, что принятые задачи не могут быть "сняты" по прошествии определённого времени после сдачи.
Вариант второй — вообще исключить задачу F из проблемсета, считая, что предлагалось 10 задач. В пользу этого варианта — тот факт, что даже если бы успешные попытки были "сняты" немедленно после сдачи, к правильному решению это бы не привело, нерешаемость задачи в данной формулировке, а также "условная внезачётность" этапа — в этом случае бонус получат команды, адекватно оценившие задачу F.
В данной ситуации, как мне кажется, будет осмысленно перед вынесением решения Апелляционным жюри в соответствии с Регламентом Открытого Кубка выслушать мнения участников в свободном обсуждении. Соответственно, дополнительная просьба — стараться по возможности аргументировать свои мнения.
Добавлю еще одно соображение в пользу решения "как есть". Например, команда Moscow SU Trinity сдала эту задачу на отметке 3:50:40. После этого последовали сдачи на отметках 4:25:53 и 4:51:26. Если снимать задачу, то у Trinity остается 10 задач, а лишнее время, потраченное на "Цену вопроса" остается зашитым в двух последующих попытках. Из-за этого Trinity начинает проигрывать другим командам, имеющим 10 задач. Это никоим образом не эмулирует ситуацию, когда задача F была исключена с самого начала контеста (ведь в этом случае Trinity бы просто сдала остальные задачи раньше). Аналогичная ситуация с NRU ITMO #1 и думаю, с еще несколькими командами (специально не проверял).
Соображение "бонус получат команды, адекватно оценившие F" мне кажется спорным. Задача по сложности предполагалась в верхней половине сета. Если некая команда ее не решала, то неясно, из-за чего это произошло: из-за того, что догадались о некорректной постановке, или же просто не брались за нее из-за нехватки времени. Возможен третий вариант: задачу пытались решать, но не нашли "решения" и в то же время не доказали, что решения нет. В этом случае о бонусе говорить бессмысленно.
Мне кажется, что более вероятны последние два варианта. По крайней мере мне известно только о двух clarification'ах на некорректность, один из которых поступил уже после окончания контеста. Вероятно, если у команды возникают сомнения в корректности задачи, то она скорее отправит clarification, чем нет.
Доказать, что решения нет, не так-то и просто. Даже сведение к 3-sat не является доказательством. Найти решение куда проще. Умение доказать, что найденное "решение" не является верным, тоже требует сил на контесте. Каждая команда имеет выбор, как расходовать время. Посылка неверных решений традиционно штрафуется на acm-style соревнованиях. В этом смысле при исключении задачи поддерживается "честность" соревнования.
С другой стороны железное правило ACM соревнований — Accepted is accepted no matter what (ну ок, за исключением случаев взлома системы)
Ещё случай, когда ОК снимается — когда по ошибке чекер всегда выдаёт OK и это сразу заметили (причём в первой половине контеста). Несколько раз такое в Петрозаводске случалось (в основном на "неполигоновских" контестах). Но даже в этом случае если ОК простоял час, то вряд ли снимут.
Команды, которые получили AC по F, ничего не теряют в случае выкидывания её из problemset'а: в случае правильного решения жюри они бы получили бревно, и как минимум продолжили бы тратить на эту задачу время и дальше (разумеется, безуспешно).
Задача по сложности предполагалась в верхней половине сета — ну это проблемы авторов проблемсета, что они неправильно оценили сложность задачи :) Какое это имеет отношение к подведению итогов контеста?
Если некая команда ее не решала, то неясно, из-за чего это произошло: из-за того, что догадались о некорректной постановке, или же просто не брались за нее из-за нехватки времени — что значит "некорректная постановка"? Постановка корректна, просто задачу фиг решишь. Думаю, большинство команд либо не брались за неё (в топе такие вряд ли есть), либо не догадались попробовать свести к ней 3-SAT, и честно пытались её решить (как мы), разумеется понимая, что тупняк (который все сдавали) — неправильное решение.
В любом случае, то, что по этой задаче сдавали, — пишется быстро, при этом если подумать над задачей хотя бы 5 минут, то контрпример очевиден. Учитывая всё это и то, что науке на данный момент решение задачи неизвестно, мне кажется, что убрать F из результатов — самое разумное решение (даже несмотря на accepted is accepted no matter what).
P.S. Вопрос к топовым командам, сдавшим её на контесте (в частности, к Petr Team): в моё мировоззрение не очень укладывается, что вы могли засабмитить недоказанную лажу, да ещё и с очевидным контрпримером. Вы на контесте понимали, что ваше решение неправильное? Если да, то вы сообщили жюри, что у них лажа? Если да, то почему жюри так поздно прореагировало?
На эту задачу не могло быть "правильного" решения жюри, укладывающегося в TL. Выбросить F из таблицы — это означает рассмотреть ситуацию, когда ее не было в сете с самого начала. В этом случае никто никаких бревен не получал бы и время не тратил.
Хм, что значит не могло быть? Вы это доказывать умеете? oO Круто :)
В этом случае никто никаких бревен не получал бы и время не тратил — идеального решения в данной ситуации разумеется нет (поэтому этап и делают условно внеконкурсным). Но у выкидывания из таблицы минусов меньше всего (странно давать каким-то командам дополнительные баллы за то, что они угадали, какая именно очевидная лажа пришла в голову жюри, и зачем-то засабмитили это)
Мы не могли её решить, тупое решение и контрпример к нему придумали в первый час примерно. Когда я писал задачу K (предпоследнюю для нас), Паша и Андрей стали рассматривать более простые её версии, в попытке решить, и, рассмотрев версию с весами 0 и 1, заметили, что это равносильно раскраске в минимальное число цветов, а значит задача NP-трудная. Потом я сдал K, и у нас осталась только F. Мы подумали, можно ли написать какой-то перебор с отсечениями, тоже ничего не придумали.
Тогда мы осознанно стали думать, как именно могли её неправильно решить авторы и ещё несколько команд. Решили, что кроме тупого решения (брать минимальное ребро) ничего здесь тоже придумать не выходит, и решили послать это просто чтобы проверить, нет ли у авторов такой лажи — время за компьютером было не критично, других задач не было все равно. Оказалось, есть такая лажа. Мы сразу же послали клар, в котором написали контртест.
EDIT. Не клар, а сообщение snarknews.
Неверно. В случае правильного решения жюри по задаче не было бы AC на втором часу от команд внизу таблицы, и другие команды сто раз подумали бы, прежде чем придумывать недоказанную лажу или вообще не пытались бы решить эту задачу.
В данном случае сработал reverse-engineering метод "что за тупую жадность могли массово позасылать в этой задаче".
.
Предлагаю рассмотреть следующую ситуацию: хотя у жюри нет правильного решения, у них есть бесконечно сильные тесты (то есть валящие любое неправильно решение). Тогда все команды посылавшие эту задачу просто получили бы WA. Для команд получивших ОК с точки зрения времени ничего не изменилось, так как после этого они времени на задачу не тратили (хотя возможно тратили бы если получили WA, считай повезло). Для команд получивших сколько то WA перед получением OK так же с точки зрения времени хуже не стало, в случае бесконечно сильных тестов они могли потратить только больше времени. Точно так же ничего не изменилось для команд которые продолжали получать WA — их решения заведомо неверные, а значит достойны WA. То есть если рассматривать каждую команду изолировано, то можно просто добавить новые тесты в задачу и перетестировать все решения (что эквивалентно снятию задачи). Единственная проблема которая остается и устранить ее невозможно — команды которые понимали что такое решение неправильное, но продолжали думать в попытках сделать что-нить нормальное, так как видили что другие задачу сдают (но оказались не достаточно умными, чтобы свести к этой задаче NP-полную). Из описанного выше хочу сказать что разумно сделать следующее: добавить в задачу сильные тесты и сделать реджадж, что будет эквивалентно ее снятию. Как было показано выше, командам которые сдали или долбались пытаясь сдать хуже от этого не станет. А для команд которые потратили время пытаясь решить теперь уже этого вернуть нельзя. С другой стороны оставить задачу в туре будет совершенно несправедливо: вы даете AC тем кто не подумал как следует, давая им преимущество перед теми кто думает перед тем как что то писать. Замечательный методический момент.
Резюмируя: задача ОБЯЗАТЕЛЬНО должна быть снята или в нее должны быть добавлены сильные тесты.
P.S. Любители прецедентной судебной системы могут вспомнить задачу про шахматного слона с какого то весеннего прошлогоднего опенкапа. Единственное отличие — тогда у жюри были нормальные тесты и решение и они были добавлены ПОСЛЕ контеста и все решения были перереджаджены. В отличие от текущего случая, тут как раз можно было говорить о несправедливости, поскольку многие участники получившие после реджаджа WA могли бы и придумать полное решение на контесте.
P.P.S. 2Егор правила аксептед есть аксептед все-таки применяется к случаю описанному выше, а не к текущему.
Тогда раунд был просто объявлен внезачетным, поэтому не имело значения, что и как пересудят.
Это магия
На мой взгляд более адекватным будет просто не учитывать это гран-при вообще. Во всяком случае, если не будет существенных проблем на следующих.
В любом случае невозможно точно установить кто сколько времени на что потерял. Еще могут быть команды, которые с примерно такой же лажей, но работающей чуть-чуть не так, как у жюри. В любом случае эта задача устроило что-то очень странное со штрафным временем. Так что даже если ее выкидывать, все равно надо как-то усреднять штраф.
Присоединяюсь. Составители накосячили, и любое решение, кроме этого, будет несправедливым по отношению к кому-либо из участников.
в том числе и его неучет(не говорю при этом, что не нужно не учитывать)
Аргументирую: есть команды конкурирующие между собой, но ближе к низу таблицы и на которые никак не повлияла задача F(кроме того, что они ее прочитали). Несправедливо не давать команде которая выше больше очков (рейтинга).
Разве что с точки зрения потраченного времени.
Мне кажется, пусть лучше участники (в том числе мы) просто потратят время, чем потратят время и случайные команды сдадут на задачу больше, потому что придумали правильную лажу. Я бы не хотел, чтобы это вообще хоть как-то влияло на положение в OpenCup (которое, например, влияет на штраф на онсайте).
(добавил пример, может не очень убедительный, возможно ты еще не успел прочитать)
Я не к тому, что этот вариат плох или хуже какого-то другого.
Просто комментарий на который я отвечал, по-моему, выглядит как "все решения несправедливы, давайте выберем вот это"
Кто-нибудь может объяснить почему нельзя просто объявить раунд полностью внезачетным?
Потому что есть команды, которых не затронула проблема с задачей F и которые хотят, чтобы результат пошел им в зачет. Прецеденты учета этапа при наличии проблем с одной задачей были. Вроде на ГП Харькова с Е были проблемы (сама лично в них не вникала, могу ошибаться).
Лично для меня лучший вариант — "условно внезачетный этап", со снятием всех AC по F. Эту задачу мы почти не решали на контесте, на наш результат она не повлияла (зато повлияла на результат конкурентов, которые получили незаслуженный AC). Сделать этап совсем внезачетным — значит уменьшить общее количество зачетных этапов. Мы были авторами ГП Саратова, у нас и так меньше зачетных этапов, чем у других.
Если честно, не помню, какие там были проблемы, но в любом случае они затронули всех намного меньше. Боюсь, что логика прецедента в таких вопросах работает плохо. Думаю, что найти очередной японский (или какой-то еще) контест для увеличения количества зачетных этапов будет лучшим решением, чем оставить этот.
Не все читал что писали выше, извиняюсь если повторю кого нибудь. ОЧЕВИДНО, что даже после снятия задачи F (а это по моему также ОЧЕВИДНО) команды получившие АС по задаче F на контесте все равно оказываются в положении более выгодном чем те кто не получил, поскольку если были нормальные тесты то они получили WA и потратили еще больше времени. А так им повезло и они больше не тупили над ней.
То есть если оставить задачу F — то огромная выгода тем кто пишет лажу. Если снять задачу F но сделать рейтинговым контест — то некоторая выгода тем кто пишет лажу.
По мне так лучше даже делать зачет из 3 — 4 контестов из 8 (а тут еще и запас есть!) если в оставшихся всплывает такая проблема. По мне так адекватный выход из ситуации один) ну а команды которые не брались за нее остается токо жалеть)
Неправильная логика. На выбор решать или не решать задачу и в особенности писать или не писать лажу влияет ситуация в мониторе.
Были бы нормальные тесты — контест бы прошел по-другому.
ты в целом прав, НО СИТУАЦИЯ В МОНИТОРЕ была у всех одинаковая) так что хз к чему ты про нее написал) и те кто написали лажу очевидно в более выгодных условиях. Были бы тесты нормальные контест и правда бы пошел по другому и был бы рейтинговый, но как видишь он пошел так
Ну у нас совсем не так, как ты пишешь. Мы потратили на F больше часа, хоть и получили в итоге AC. Так что если ее снять, то вообще неясно на что мы потратили время. Остальные задачи мы решили, но не успели закодить. Если бы этой задачи не было, то оставшиеся две могли бы сдать.
Ренат и мы могли сдать оставшуюся задачу если не было F) А вы час потратили и не поняли что решение лажа? или час писали это решение?)
Вначале мы писали что-то другое, потом написали эту лажу. Подробности к Диме.
Да, у всех бывают тяжёлые дни, когда задача на два вложенных цикла пишется целый час на контесте.
Видимо, мозги были уверены в этом решении, а руки при попытке закодить не верили и сопротивлялись.