До полуфинала NEERC 2012 осталось совсем чуть-чуть, а до финального этапа ВКОШП 2012 — пара дней. Желаю не тупить и не бажить, поменьше дебага и побольше Accepted-ов!
Перед столь важными соревнованиями всегда полезно вспомнить свои удачные выступления, а порой даже просто чудесные случаи. Верьте в чудеса!
Предлагаю тему — давайте вспомним чудеса на контестах, которые случались с вами. Лично я всегда упоминаю такой случай.
Посмотрите на этот ранклист (Петрозаводск, зима 2003):
Final Contest, Saturday, February 08, 2003 RESULTS
ID Team A B C D E F G H = Time R
-------------------------------------------------------------------------------
05 Saratov SU#3 . +9 +12 . . . . + 3 1045 1
09 Outsiders . +2 + . . . . . 2 253 2
19 Trinity . + . . -5 . . + 2 282 3
07 SPb IFMO 2 . +2 -3 . -4 . . + 2 378 4
01 SPb IFMO 1 . +1 . . -3 -2 . . 1 104 5
16 DNK . -4 . . . . . + 1 241 6
18 Noname . -7 . . . . . + 1 268 7
06 SPb SU#3 . -8 . +2 . . . . 1 318 8
20 SPb ETU 1 . -3 . . . . . +3 1 327 9
02 SPb SU 24 . -2 . . . . . . 0 0 10
03 New . -1 -7 . . . . . 0 0 10
04 YaRiK . -7 . . . . . . 0 0 10
08 MSU SA . . . . . . . . 0 0 10
10 ME4TA . . . -3 . . . . 0 0 10
11 Antivirus . . . . . . . . 0 0 10
12 Jupiter . . . . . . . -22 0 0 10
13 HACMOPK . . . . . . . . 0 0 10
14 BM . . -11 . . . . . 0 0 10
15 AI . . . . . . . . 0 0 10
17 Wx4 . . -4 . . . . . 0 0 10
Команда Saratov SU 3 — это мы: Эльтерман, Лазарев, Мирзаянов. Последняя попытка в этом контесте — наша. За 16 секунд до окончания мы получили ACCEPTED по задаче С. Особый смак добавляет факт, что решали ее в основном Андрей Лазарев и я. Мы написали по тем временам сложное решение со случаями и КМП, оно падало с WA на каких-то тестах, и под конец соревнования у нас совсем опустились руки. Волевым решением на последних минутах капитан команды Илья Эльтерман попросил нас от клавиатуры и (почти не зная задачу!) стал делать попытку за попыткой делая случайные изменения кода. В ход пошли замены < на <= (и наоборот), всякие +1 и -1 в формулах и прочие сомнительные изменения.
Он сделал несколько попыток, приходили разные вердикты WA, PE и так далее. Контест закончился, мы расстроенные пошли на обед. Я же решил успеть написать письмо до обеда и минуты через две после окончания контеста, закрыв MessageBox, понял, что там было написано <<ACCEPTED!>>.
Да-да, именно так мы победили на тех сборах :-) Верьте в чудеса!
А о каких чудесах можете рассказать вы?
Почти такой же случай произошёл с нашей командой в прошлом году на каком-то тренировочном контесте. Два моих сокомандника долго мучали какую-то то ли геометрию, то ли физику, а я всё, что мог решить, уже решил. Тогда я присоединился к ним и начал пытаться дебажить софт по задаче, которую особо и не знал. Мне объяснили, что написано уже две программы и не понятно, чем плоха любая из них. В общем, каким-то магическим способом совмещая код этих двух программ в третью, я в последние минуты получил-таки AC. К победе это не привело, но всё равно было очень забавно.
Ещё у нас тут есть известная история о временах, когда сабмит на USACO производился по почте. Из-за недоступности интернета простым смертным, USACO писали в помещении курсов, в котором интернет был на машине преподавателя. И вот контест закончился и контестанты несут свои решения преподавателю. Когда очередь дошла до решений героя этой истории, запыхавшийся препод случайно послал решение, но неправильно указал задачу. Делать нечего, мэйл обратно уже не вернёшь — пришлось перезаслать решение. А на эту задачу у контестанта всё равно решений не было. Через какое-то время приходят результаты — на "правильной" задаче-то он получи 100%, а на другой ещё — около 30%-40%. Это было весьма неожиданным приятным сюрпризом.
Ну например могу вспомнить про ВКОШП-2010.
Очень бодро начав через 1,5 (или 2) часа у нас было 5 задач, у гены через минуту тоже 5 с куда лучшим штрафом, у остальных 4 и меньше. Впереди есть решенный геом, какой-то жадник с бинпоиском и какое-то декартово дерево. Садимся писать жадность. Написали, протестировали на примере. Не сходится. Понимаем, что жадность неправильная забиваем садимся за геом.
К тому времени, как дописали геом у нескольких команд уже по 6, кто-то сдавал "жадность", кто-то геом. Заходило все давольло легко у команд. Посылаем. WA4. Что-то поправили. WA18. Оставшаяся часть контеста прошла в получении этого WA18, периодически превращавшегося в что-то еще более маленькое. Минут за 15 до конца решаем поделать всякую чушь. Правим какие-то несущественные места. Внезапно WA61. Правим eps. Получаем букет из разных WA и внезапно OK. До конца контеста 7 минут. Делать нечего беремся за жадность. Вписываем все подряд компараторы. Какой-то вдруг проходит тест из примера. Посылаем. OK.
Не сказать, чтобы были довольны результатом, но за 5 минут до конца он казался куда более приятным, чем за 15.
Чудеса, конечно, бывают, но все-таки у вас 5-я была сдана на 107-й минуте, а у Гены на 49-й. Судя по таблице. UPD. Может, правда, какое-то перетестировние было, не помню.
Значит я криво что-то заметил. Возможно. На контесте нет времени внимательно следить за монитором. Воспоминание осталось, что мы сдали чуть раньше но с плохим штрафом.
Предпоследний абзац.
Не могу не вспомнить, как наша команда попала на финал в этом году. Где-то за полчаса до конца у нас было 4 задачи. Тогда eduardische послал простой жадник на одну задачу, мы получили ОК, обрадовались нереально. Писались ещё две задачи, обе получали WA, первая — динамика, вторая про строки. И за пять минут до конца nvilcins исправил баг и на динамику мы получили плюсик... У нас даже стул полетел на пол, когда мы вскочили от радости.
А на закрытии называли команды на финал, и оказалось, что мы первые за чертой, потому что только 13 проходят. Мы ещё не успели порядком расстроиться, когда объявили, что регион получает ещё 4 дополнительных места. :D
У меня конечно на памяти осталась студенческая олимпиада СГУ 2011 года. Контест начался хорошо я быстро (за 36 минут) нашел 3 простенькие задачи и с плюса сдал их. Оказался в одной из первых строк ранклиста. Что происходило потом мне трудно объяснить потому, что к моменту заморозки у меня по прежнему было сдано 3 задачи и -15 по другой задаче. В ранклисте меня обгоняли все в том числе студенты младших курсов которые только начали заниматься, а также случайные прохожие :-) Монитор заморозили и я подумал черт с задачей F надо че-нить решать. Открыл быстро сдал динамику (в которой все сдавали жадность). Потом открыл задачку на графы быстро с +2 сдал. Открыл геометрию написал, поискал баги, попосылал, поподгонял EPS и наконец сдал с +5. До конца контест оставалось 7 минут я подумал ну норм короче спасся. Трудно объяснить о чем я думал но я решил еще раз послать свой последний код по задаче по которой у меня было -15 послал и начал думать в чем у меня баг. И с ужасом увидел что она прошла. Ну вот собственно чем все закончилось:
Петя Калинин недавно писал про "10 лет назад"
Очень даже чудо :-)
Спасибо за пожелания! От себя также пожелаю удачи всем командам Питера на ВКОШПе и на полуфинале. Ребята, тащим, Питер зе бест ;)
И небольшая скромная история. В этом году был я в ЛКШ, ну, и по канону, в конце смены зачет. Зачет достаточно простой, ведь, все-таки, он по задачам, схожим с задачами на прошедших контестах, по известным темам. Ну, я быстро сдал все простые задачи, набрав "5-". До конца зачета оставалось примерно 2.5 часа, что очень даже прилично. На глаза попалась несложная задача, я ее быстро решил, написал, заслал — WA. Думаю, блин, опять какая-то дурацкая бага, все-таки само решение вполне очевидное и правильное. Дебагаю-дебагаю, наконец понимаю, что код полностью верен. В задаче присутствовал тернарник по вещественным числам, так что, подумал я, проблема в точности. Стал я подбирать константы всякие разные, какие я только не выдумывал. Но противный WA все никак не давал мне получить мою "5". Так я сидел ДВА ЧАСА на простейшей задаче, валялся в траве, орал, бесился. Так сидел я сидел, сидел-сидел, до того дошло, что до конца зачета осталось 3 минуты. Ну, думаю я, облажался. Приплыли. Суши весла. Думаю, зашлю-ка я еще раз этот несчастный говнокод, получу свой WA и пойду в корпус пить позорный чай. Отсылаю — пишет, что посылаю дубликат кода. С этим никак смириться не мог я — выбрал рандомное место в программе, да изменил там один символ. Снова заслал. Обновляю сабмиты в ожидании очевидного WA. Вы только представьте себе, каким было мое удивление, когда вердиктом по задаче стал ЗЕЛЕНЕНЬКИЙ AC. Тут я заорал бешеным криком. Я танцевал, ругался, никак не мог успокоиться. В этот момент в комповник зашел Андрей Станкевич, думаю, мое поведение его очень даже повеселило :) А решение.. Заменил я константу в тернарнике, причем похожее ее значение до этого уже было опробовано и не зашло, а тут оп и зашло. История достаточно позорная по сравнению с остальными, здесь выложенными, но для меня она очень поучительна, часто ее вспоминаю и смеюсь :)
Московский четвертьфинал 2010, команда MSU.T@pirenock — еще совсем зеленые первокурсники, только-только съездившие на свои межнары. Для меня тот год был первым годом написания контестов на C++, поэтому я чувствовал себя еще довольно неуверенно. В тот год от МГУ на полуфинал выходили еще только 4 команды, 3 из которых были всем ясны (unpredictable, ST, pushkin), а за 4-ую путевку в солнечный питерский край развернулась ожесточенная борьба. Мы, как обычно, крайне неудачно начали контест, "сев" на нескольких довольно простых задачах. В итоге лишь к последнему часу мы догнали группу команд МГУ с 8-ю задачами (в которой насчитывалось уже около 3-4 команд, при это 3 команды МГУ уже имели >= 9 задач), проигрываю им всем по пенальти. Честно говоря, в тот момент выход на полуфинал казался фантастикой.
9-ой задачей мы писали какую-то динамику, причем со слегка неверной сложностью. За полторы минуты до конца получили заслуженный ТЛ, но (сам удивляюсь как), рук не опустили. Посмотрели в код, Миша Пядеркин показал один из циклов и сказал что он и есть самое узкое место. Я предложил ему вставить частичные суммы и ограничить ими пределы цикла, быстрым альт-табом он посмотрел на секундомер — оставалось около 50 секунд. Дальше он сделал то, на что я сомневаюсь что у меня когда-либо хватило нервов: недрогнувшей рукой, он объявил два массива, добавил два цикла считающие частичные суммы, изменил пределы в цикле, и за все это время не сделал ни одной опечатки! Я только стоял разинув рот и смотрел как он посылает задачу за 13 секунд до конца. Поскольку решение по-прежнему оставалось неверным по сложности, нас ожидали томительные 3-4 минуты созерцания строчки running, что впрочем только приумножило нашу радость когда строчка все-таки стала зеленой. Дежурные уже пытались попросить нас удалиться, но поняв в чем дело, смотрели вместе с нами =)
Несмотря на это, мы все равно не сомневались что хотя бы одна из команд-конкурентов сдала 9-ую задачу и несомненно обошла нас по времени. Большую часть из них мы опросили сразу же после контеста, и каждый новый ответ "сдали 8" увеличивал нашу надежду. Потом было еще много нервного ожидания, и радость в конце, так как помимо поездки на полуфинал, этот accepted дал нам поездку в новосибирск (МГУ оплачивал не все прошедшие команды, а только полуфиналистов), сборы МФТИ и весьма ценный слот на петрозаводских сборах. Довольно не плохой куш мы сорвали за 13 секунд, не правда ли?
Помнится Виталик Гольдштейн нам сказал после контеста "Задачи вы решать еще не умеете, но характер у вас есть".
да, хорошая история)
Ахах =)
Да, читая историю, я понимал, что это тот четвертьфинал, на котором у вас забрали полуфинал на последней минуте :)
Я помню-помню! Ты тогда еще встал и на всю аудиторию прокричал: "Кто тут папка оптимизации?" =)
Для нас эта история, действительно, скорее хорошая. Потому что команде Родиона мы проиграли 5 минут.
Московская четверть 2006 года — оказалась невероятно чудесной для нашей команды (Я, Яков Длугач, Андрей Локоть). На момент конца контеста мы не выходили из-за вузовой квоты (были бы четвертыми, даже если за заморозку никто ничего не решил), но из-за того, что несколько последних минут сервер сбоил контест продлили на 15 минут. За эти 15 минут мы каким-то образом успели решить две задачи и вышли первыми от МФТИ.
Есть одна история из ЛКШ. Параллель А', домик вечером перед практическим зачетом. Сосед по комнате рассказывает мне о задаче king(наверное, все ее знают), которая в прошлом году была у него на зачете в параллели В. Решение, конечно, рассказывает не до мельчайших подробностей, но становится понятным, что писать там надо не паросочетания, а разбиение на компоненты сильной связности. Просыпаемся, идем на зачет, садимся за ноутбуки напротив друг друга. Открываем задачи(был сразу весь набор задач) и видим задачу king на 5+. Обменялись взглядами, улыбнулись, начали решать. Сразу скажу, что этот контест был не очень удачным :) К обеду я имел всего лишь 3-(воистину лох), при этом у меня была не написана самая тупая из задач на 3. Решил, что раз я знаю решение по King, написать его не так уж и сложно(тем более можно было использовать написанный за смену код). Копипастю разбиение на компоненты сильной связности, редактирую задачу, чтобы что-то, похожее на правильное, выводило, отсылаю, WA 4. Смотрю на препов, они вслух смеются над тем, что троечник отсылает решение задачи на 5+. Думаю о том, что будет, когда я ее сдам, но WA 4 от этого, правда, никуда не делся. Вбиваю рандомный тест, смотрю — неправильный ответ выдает. Добавляю одну проверку — OK. В итоге эту задачу сдали только двое — я и мой сосед по комнате. Вот такая вот история. Разговорчивый сосед и никакого мошенничества :)
Ну так расскажи, что стало с преподавателями после того, как троечник сдал задачу на 5+
Примерно ничего, по крайней мере со мной.
Расскажите вообще кто нибудь об ЛКШ, что это такое, как туда попасть, как там все проходит. Интересно же.
http://olympiads.ru/sis/index.shtml Мог бы и сам поискать
А оценка ставится по одной наиболее сложной задаче?
Нет, в этом случае задача на 5+ шла как задача на 3. x1te получил бы 5+, если бы еще решил нужное количество задач на 4 и 5, но он почему-то не справился с этим.
В прошлом году на четвертьфинале ACM ICPC в Минске мы за 15 секунд отправили решение, над которым колупались 2 часа. Последний час сидели и тупили, где тут RE 15. В итоге за 5 минут до конца контеста я резво прошёлся по всему коду, понаставил всевозможных затычек где ни попадя и где они вроде как и не нужны (и в это время меня уже жутко колотило, т.к. по нашим расчётам мы были чуть ниже строчки попадания в полуфинал). Когда отправил, состояние было у меня уже жутковатое (всё-таки очень хотелось в Питер же, последний раз учавствовал). Все уже расходиться начали, а я сидел и судорожно обновлял страницу с вердиктами тестирующей системы.
И да, именно благодаря этой задаче мы в полуфинал и попали.
В далеком 2009 году в шестой день на сборах в Петрозаводске был забавный случай. Мы написали многобуквенное решение в задаче С, получили ВА, что-то поправили, снова получили ВА и долго медитировали над нашим решением. В итоге мы начали решать другую задачу, не успели ее как следует отладить и, понимая, что контест слит, пошли обедать. К ужину ближе меня осенило, что я как-то очень плохо оценил максимальную длину числа в длинке, выставил размер массива в 10 раз больше, получил Accepted и совсем расстроенный ушел рубиться не помню во что.
По приезду в Самару нам говорят — а вы здорово выступили, особенно в шестой день! Я не верю своим ушам и открываю монитор. Что? Задача С?! Да у нас же был WA! Я долго пытался понять, что же произошло, и у меня есть единственное объяснение этому факту.
Видимо, после контеста по какой-то причине был rejudge. В случае ответа "YES" в программе никакого вылезания за границу массива и в помине не было. В случае ответа "NO" программа за массив убегала намертво, но последней операцией программы была проверка ответа. Если повезет и проверка не сошлась, мы правильно решаем тест! Похоже, что при повторном запуске звезды были на стороне нашей программы.
Вот как-то так получаются лучшие за все время выступления в Петрозаводске.
Я вспоминаю чудеса на одной из наших тренировок. Ребята решали очень хорошо, я приободрился. "Могут, когда хотят!" Примерно так я думал :-)
На третьем часу контеста я заметил, что совсем неправильный код одного из участников получает ACCEPTED. Немного игры в детектива и выяснилось, что подлый вирус пожрал тестирующий компьютер — как результат, все процессы стали завершаться с exitCode=0. И чекеры тоже.
Мы в этом году в ЛКШ.Август в инновационной параллели C.py при подготовке задач использовали экспериментальную систему Please, разработанную годом ранее в ЛКШ же. Посередине смены обнаружилось, что наша система в качестве стандартного чекера ставила
Если забыть сделать чекер, то возникал схожий эффект. AC каждому, даром, и пусть никто не уйдёт обиженный!
Например, валидация задач в Codeforces::Тренировках включает как один из этапов проверку, что на случайной строке чекер возвращает WA или PE. Такой фокус там не пройдет :-)
А если задача вот такая, только со строками, как быть?
Редчайшая экзотика. Кроме того, полагаю, что в задаче все-равно будет ограничение на выводимые символы и длину, а при валидации в чекер отдается очень широкий диапазон и довольна длинная строка.
Очередная иллюстрация того, что возвращать вердикт через exit code — костылеобразное извращение. А ведь до сих пор существуют тестирующие системы, считающие, что так и надо :(
А как предлагается делать иначе? Выводить в stdout вердикт?
Например в stdout. Или в report-файл, как все современные чекеры умеют делать.
Exit codes — стандартный и переносимый способ возвращать статусы из приложений. Они и придуманы для подобных вещей. Очень приятно, что используются они — например, даже чекеры из других стран почти всегда следуют соглашениям. А использовать общий спец. формат вывода в файл/stdout/stderr — утопия, да и смысла в этом мало.
Это стандартный способ только в рамках sh-way. Но тестирующие системы — это давно уже не набор bash-скриптов, поэтому и вердикт хорошо бы возвращать в более приятном и расширяемом формате (через exit-code никакой дополнительной информации не передашь; что если логика задачи предполагает >1 байта информации от чекера?). Общий формат вывода в файл давно уже есть у всех testlib'ов; ну а для чекеров из другой исторической эпохи/других стран можно писать стандартные wrapper'ы.
Это стандартный способ в рамках POSIX, Windows API и языков C, C++ и Java.
? Не понял. С каких это пор POSIX, Windows API, C, C++ и Java регламентируют, как возвращать вердикты чекеров? oO
Никаких стандартов про чекеры не существует, и конечно было бы хорошо их создать. С архитектурной точки зрения передача информации через коды возврата программы используется только при написании shell-скриптов, что ИМХО в данном случае не подходит (не говоря уж о том, что это не покрывает всех существующих use-case'ов, например, строки-комментария от чекера).
С архитектурной точки зрения коды возврата используются везде, где есть процесс-родитель и процесс-потомок, для этого они и придуманы.
Конечно, результат работы программы можно возвращать и через файл с навороченной XML-разметкой, который каждый раз парсится и валидируется, и даже через более сложные схемы. Но… зачем?
Удивлён таким количеством сторонников exit-кодов, применяемых не в тему...
Они используются не для передачи информации между родителем и потомком, а (в первую очередь) для сигнала о том, что в процессе работы потомка произошло что-то нехорошее. Реже (в шелл-скриптах) они используются для передачи данных из ограниченного диапазона, например булевых. А для передачи информации между родителем и потомком нормальных программах используются пайпы, сокеты, много чего ещё.
На вопрос "зачем" ответ очевиден — из-за расширяемости. Предположим, есть задача, в которой тест не "OK/WA/PE", а даёт какое-то количество баллов, например, от 0 до 100000. Как вы это предлагаете в извращённой модели с exit-кодами делать? Писать 3 чекера, каждый из которых возвращает по одному байту от score? ИМХО, за такое надо руки отрубать :) Таких примеров можно привести множество, а модель с нормальной xml'кой в качестве результата — отлично расширяемая, и проблем с ней я не вижу.
Я, я не за exit-коды! Я поддерживаю всё что ты отписал выше :)
Exit-коды, имхо, идейно должны возвращать не результат работы другой программы, а успешный/ошибочный результат работы самой себя, а вся остальная инфа (в том числе результат работы тестируемой программы и дополнительные комментарии к результатам работы) должны быть обозначены другими способами. То есть основные две проблемы: exit-коды в принципе не для того и проблема расширяемости.
UPD. Да, и ещё я не понимаю, почему твои посты так яро минусуют. Всё вроде разумно и дискуссируемо.
Нет никакой проблемы в самом exit code. Проблема здесь в том, что exit code 0 поведение по умолчанию и "все хорошо" одновременно. Говоря простым и понятным языком:
Замечательное самонаведение в ногу. Например,
то, что явно необходимо функции, принимающей Checker как параметр.
Где это поведение по умолчанию? А еще exit code удобен для писания всяких скриптов во время подготовки задачи. И тут exit code 0, как "все хорошо" очень даже важен.
ЗЫ. Я не понял к чему код приведенный выше, но это лечится деланьем функции hasErrors чисто абстрактной (или как там это называется). По моему приписать =0 в конец или что-то такое.
Если поставлю ping как checker, работать будет?
Например, первый попавшийся исходник вполне подошел на роль чекера на полигоне.
Upd. Лечится {return true;}, хотя в данном примере правильно, конечно, = 0 {return false;}
Ну поведение по умолчанию — это тоже вполне себе shellscript-way, так что с кодом возврата согласуется :) Обычно когда надо сделать что-то по-человечески и надолго, а не сваять на скорую руку, — shellscript-way плохо подходит.
Кажется Moscow SU 1, Belarusian SU 1 и SPb SU 4 (у последней вообще 4 задачи за последний час) после сегодняшнего NEERC есть что рассказать :)