10 лет назад
...Мы как-то не замечали, как идет время. То, что монитор заморозили, мы поняли, только услышав краем уха фразу про это от соседней команды.
...Контест начался для нас с PE1 на первом же сабмите, и мы - мы с Серегой второй раз участвовали в серьезных командных соревнованиях, Антон - первый - мы стали сразу же думать на тему "надо ли в конце выходного файла выводить перевод строки". Что-то исправили, пересабмитили, получили Accepted, и только когда нам принесли распечатку, подтверждающую успешный сабмит, я заподозрил - и только после контеста проверил - что в первом сабмите я умудрился решение задачи F послать по задаче E.
Дальше, на протяжении всего контеста, мы колебались на грани прохождения в финал. Сдав очередную задачу, мы поднимались место на десятое, а в промежутках между сдачами задач откатывались место на 20-е. За первые места в контесте боролась группа фаворитов, в первую очередь MSU 1 - настоящая dream-team от МГУ - и Saratov SU 3, чемпионы Европы прошлого года.
...Итак, до конца контеста оставалось меньше часа. МГУ1 за несколько минут до заморозки монитора сдали последнюю, девятую, задачу, обеспечив себе практически безоговорочное первое место. У нас Серега писал I, а мы с Антоном сидели над несколькостраничной распечаткой моего решения A и искали в нем баги. Находя очередной баг, мы выгоняли Серегу из-за компа, исправляли его, сабмитили заново - и уходили дальше читать код. Через пару минут Серега подтверждал нам, что у нас очередной WA. В какой-то момент мы даже перераспечатали решение - столько там было исправлений.
...До конца контеста оставалось 25 минут, когда на очередной итерации этого процесса нам пришел Accepted. (Я до сих пор удивлен, что у нас в таблице по A стоит всего лишь +2; я думал, что штрафных попыток у нас было намного больше.) Но, получив Accepted по A, мы сели по обе стороны от Сереги и стали смотреть, как он пишет I. Он ее дописал, проверил на тесте из условия - сабмит! - и мы возвращаемся в IDE тестить задачу дальше. Пару простых наших тестов решение проходит, но дальше тестить не приходится: нам приходит Accepted. До конца контеста остается чуть больше 15 минут.
Из 9 задач контеста у нас решены 7. Остались две: G - страшная стереометрия, по которой у нас ни строчки кода и ни строчки формул, - и E. По ней, если не считать того ошибочного первого сабмита, у нас были еще две попытки в середине контеста. Они получились так. Антон сказал: о, а наверное, задачу можно решить так. Мы написали, засабмитили, получили WA и забили - наверное, идея неправильная. Через некоторое время Антон сказал: о, прошлое решение не учитывает такой-то случай. Мы дописали в решение разбор этого случая, засабмитили, опять получили WA и опять забили.
...И вот теперь было ясно, что за оставшиеся 15 минут мы не напишем ничего по G, да и вряд ли придумаем что-то серьезно новое по E. Разве что можно надеяться на то, что у нас бага в реализации. Поэтому мы открыли решение E и стали смотреть в код. Кода там было всего строчек на 20 - Флойд плюс какая-то простая проверка. Багов вроде и сажать-то негде.
Но тут я понимаю, что на самом деле код, обрабатывающий наш второй случай, должен прекрасно работать и в первом случае. Если исходить из предположения о том, что в программе где-то бага в реализации, то с вероятностью примерно 50% она в коде для первого случая, с вероятностью 50% - в коде для второго. Поэтому комментируем код для первого случая и сабмитим. И уже не в силах дальше думать о коде, тупо пялимся в экран PCMS2.
...На наш крик "Йес" обернулась, наверное, половина аудитории, где мы сидели. Accepted! До конца контеста пара минут, у нас решено 8 из 9 задач, причем три задачи за последние полчаса - можно спокойно откинуться на спинку кресла и ждать.
...Как только объявили, что контест окончен, мы - захватив бумажки-распечатки с информацией о наших сабмитах - побежали на другой конце Аничкового дворца, где сидела команда NNSU1 во главе с Миханом - абсолютным победителем межнара двухлетней давности. И мы бежали туда с единственным вопросом: у Михана девять или надо будет штрафное время считать? Известие, что у Михана шесть, нас очень сильно удивило. Только после этого мы вспомнили, что надо бы переписать свои решения и прочие свои материалы на дискеты, раздаваемые оргкомитетом, и вернулись в нашу аудиторию - уже довольно сильно опустевшую.
...Потом до нас стали доходить слухи, что девять никто кроме МГУ не решил, да и восемь вроде "решила только одна команда". И действительно, мы - внезапно для самих себя - оказались на втором месте, решив на одну задачу меньше победителей, но при этом имея в полтора раза больше штрафного времени. Ну и надпись last success: Nizhny Novgorod SU 2, E, 4:56:45 тоже весьма радует.
...Потом мы сидели в холле Аничкова дворца, и я излагал Михану придумываемое на ходу доказательство нашего решения E. Несколько лет спустя, уже совсем по другому поводу, я писал разбор E, - и только не так давно стал подозревать, что на самом деле то, что мы там придумали, на самом деле называется "дан некоторый максимальный поток, проверьте, что он еще и mincost". Надо бы все-таки будет вспомнить условие задачи и понять, правда ли, что наше решение полностью соответствует современной терии mincost-maxflow.
...Это все было почти точно 10 лет назад.
...А когда через год мы опять займем второе место на полуфинале, это будет восприниматься не как успех, а как полный провал. Ибо сдать три задачи за последние полчаса - это очень круто, но не сдать ни одной задачи за последние два часа 20 минут (почти полконтеста) - это весьма не круто.
...А финалы мы оба слили.
...Контест начался для нас с PE1 на первом же сабмите, и мы - мы с Серегой второй раз участвовали в серьезных командных соревнованиях, Антон - первый - мы стали сразу же думать на тему "надо ли в конце выходного файла выводить перевод строки". Что-то исправили, пересабмитили, получили Accepted, и только когда нам принесли распечатку, подтверждающую успешный сабмит, я заподозрил - и только после контеста проверил - что в первом сабмите я умудрился решение задачи F послать по задаче E.
Дальше, на протяжении всего контеста, мы колебались на грани прохождения в финал. Сдав очередную задачу, мы поднимались место на десятое, а в промежутках между сдачами задач откатывались место на 20-е. За первые места в контесте боролась группа фаворитов, в первую очередь MSU 1 - настоящая dream-team от МГУ - и Saratov SU 3, чемпионы Европы прошлого года.
...Итак, до конца контеста оставалось меньше часа. МГУ1 за несколько минут до заморозки монитора сдали последнюю, девятую, задачу, обеспечив себе практически безоговорочное первое место. У нас Серега писал I, а мы с Антоном сидели над несколькостраничной распечаткой моего решения A и искали в нем баги. Находя очередной баг, мы выгоняли Серегу из-за компа, исправляли его, сабмитили заново - и уходили дальше читать код. Через пару минут Серега подтверждал нам, что у нас очередной WA. В какой-то момент мы даже перераспечатали решение - столько там было исправлений.
...До конца контеста оставалось 25 минут, когда на очередной итерации этого процесса нам пришел Accepted. (Я до сих пор удивлен, что у нас в таблице по A стоит всего лишь +2; я думал, что штрафных попыток у нас было намного больше.) Но, получив Accepted по A, мы сели по обе стороны от Сереги и стали смотреть, как он пишет I. Он ее дописал, проверил на тесте из условия - сабмит! - и мы возвращаемся в IDE тестить задачу дальше. Пару простых наших тестов решение проходит, но дальше тестить не приходится: нам приходит Accepted. До конца контеста остается чуть больше 15 минут.
Из 9 задач контеста у нас решены 7. Остались две: G - страшная стереометрия, по которой у нас ни строчки кода и ни строчки формул, - и E. По ней, если не считать того ошибочного первого сабмита, у нас были еще две попытки в середине контеста. Они получились так. Антон сказал: о, а наверное, задачу можно решить так. Мы написали, засабмитили, получили WA и забили - наверное, идея неправильная. Через некоторое время Антон сказал: о, прошлое решение не учитывает такой-то случай. Мы дописали в решение разбор этого случая, засабмитили, опять получили WA и опять забили.
...И вот теперь было ясно, что за оставшиеся 15 минут мы не напишем ничего по G, да и вряд ли придумаем что-то серьезно новое по E. Разве что можно надеяться на то, что у нас бага в реализации. Поэтому мы открыли решение E и стали смотреть в код. Кода там было всего строчек на 20 - Флойд плюс какая-то простая проверка. Багов вроде и сажать-то негде.
Но тут я понимаю, что на самом деле код, обрабатывающий наш второй случай, должен прекрасно работать и в первом случае. Если исходить из предположения о том, что в программе где-то бага в реализации, то с вероятностью примерно 50% она в коде для первого случая, с вероятностью 50% - в коде для второго. Поэтому комментируем код для первого случая и сабмитим. И уже не в силах дальше думать о коде, тупо пялимся в экран PCMS2.
...На наш крик "Йес" обернулась, наверное, половина аудитории, где мы сидели. Accepted! До конца контеста пара минут, у нас решено 8 из 9 задач, причем три задачи за последние полчаса - можно спокойно откинуться на спинку кресла и ждать.
...Как только объявили, что контест окончен, мы - захватив бумажки-распечатки с информацией о наших сабмитах - побежали на другой конце Аничкового дворца, где сидела команда NNSU1 во главе с Миханом - абсолютным победителем межнара двухлетней давности. И мы бежали туда с единственным вопросом: у Михана девять или надо будет штрафное время считать? Известие, что у Михана шесть, нас очень сильно удивило. Только после этого мы вспомнили, что надо бы переписать свои решения и прочие свои материалы на дискеты, раздаваемые оргкомитетом, и вернулись в нашу аудиторию - уже довольно сильно опустевшую.
...Потом до нас стали доходить слухи, что девять никто кроме МГУ не решил, да и восемь вроде "решила только одна команда". И действительно, мы - внезапно для самих себя - оказались на втором месте, решив на одну задачу меньше победителей, но при этом имея в полтора раза больше штрафного времени. Ну и надпись last success: Nizhny Novgorod SU 2, E, 4:56:45 тоже весьма радует.
...Потом мы сидели в холле Аничкова дворца, и я излагал Михану придумываемое на ходу доказательство нашего решения E. Несколько лет спустя, уже совсем по другому поводу, я писал разбор E, - и только не так давно стал подозревать, что на самом деле то, что мы там придумали, на самом деле называется "дан некоторый максимальный поток, проверьте, что он еще и mincost". Надо бы все-таки будет вспомнить условие задачи и понять, правда ли, что наше решение полностью соответствует современной терии mincost-maxflow.
...Это все было почти точно 10 лет назад.
...А когда через год мы опять займем второе место на полуфинале, это будет восприниматься не как успех, а как полный провал. Ибо сдать три задачи за последние полчаса - это очень круто, но не сдать ни одной задачи за последние два часа 20 минут (почти полконтеста) - это весьма не круто.
...А финалы мы оба слили.