То, что под катом, будет интересно в основном тем, кто интересуется спортивным программированием и не боится моего приступа графоманства.
Так случилось, что за сегодняшний день, в перерывах между приготовлением brownies и очередным застольем с гостями, надо было написать два контеста. Что вообще очень большая редкость, потому что участвую я только в топкодере и очень редко в чем-то еще. Но вчера вечером
pawa рассказал мне, что сейчас идут Snark News Winter Series и первый тур заканчивается сегодня в 13.
Небольшое лирическое отступление на тему спортивного программирования. Я вообще не олимпиадник и никогда специально не занималась спортивным программированием. Хотя в школе об этом мечтала - информатика была любимым предметом, ну и олимпиады по математике (хоть и школьного, максимум городского уровня) - безусловно, наше все. А в университете все как-то было странно (только сейчас пройдя этот квест, понимаю, какие скиллы надо было качать ;) ), ну и вообще кто ж берет девушек в серьезные команды :). Но жизнь так сложилась, что олимпиадников среди друзей просто-таки большинство. Где-то до 4-5 курса я лишь тихо им завидовала, что у них все так интересно, но самой что-то делать времени не хватало. Ну и просто было лень :). В какой-то момент возник интерес участвовать в отборочных турах TCO и TCCC, поскольку там был материальный стимул :). Сейчас не упускаю случай как бы невзначай прийти в общество Тех, Кто Понимает в футболочке TCO'07 или там TCCC'06(вы уж простите мне эту слабость). К сожалению, в связи с этими новыми принципами раздачи призов и отменой TCCC, в 2008 году новых футболочек у меня не появилось :(. Я сейчас как-то уже и не помню, что меня все-таки подтолкнуло, но в середине 2007 года я начала регулярно участвовать в Топкодере. Кажется совсем недавно, а между прочим, сегодня был уже мой 52-й матч (и срм и отборочные), что мне кажется очень большой цифрой (лично для меня).
Сначала я долго и упорно сидела в див 2. Решала по 1-2 задачи и думала, что в див 1 будет очень сложно. Один раз даже умудрилась ничего не решить (ну или упала задача, не помню точно) в див 2 и посерела. Потом, правда, разозлилась и через несколько матчей уже была в див 1. Произошло это вместе с осознанием того, что див 2 - 500, это очень часто див 1 - 250 и что она не может быть уж очень сложной :). В общем за 2008-й год топкодер стал регулярным мероприятием, проходящим раз в неделю-две и доставляющий просто фан. Причем я вроде как специально не тренируюсь, прорешивание практис румов так и осталось несбыточной мечтой.
Но уж если я начала во что-то втягиваться, то уже меня обратно не вернешь. Летом все-таки зарегистрировалась у
Олега (не знаю как это по-научному называется), стала участвовать в кубке Мира ПК. Во-первых, потому что там заведомо были задачи, которые я могла бы решить, ну а во-вторых, уже для разнообразия - разные правила, разные стратегии. У меня, как у человека, привыкшего к топкодеру, все эти "хитрые" форматы ввода-вывода первое время вызывали некоторые проблемы. Но может быть я все-таки с ними подружусь. По крайней мере не забывать при печати строк c_str() я уже научилась. (Серьезные олимпиадники, вы только не смейтесь над этими проблемами, я же просто любитель ;) ).
Возвращаясь к сегодняшнему дню. Утром надо было успеть до 13 начать писать SNWS. В первой же задаче, естественно, набажила с форматом вывода: забыла двоеточие после "Data Set i". Во второй задаче сама себя перехитрила и почему-то начала вероятности считать через формулу включения-исключения, когда надо было всего лишь их сложить. Не успела буквально минуту. Решила, что надо меньше мудрить.
А через полтора часа уже был СРМ. Первая задача сначала повергла в ступор. У меня уже почти всегда получается решать первую задачу за 15 минут и дальше начинать решать вторую (которую пока не очень часто удается решить). Но тут я как-то с самого начала крепко задумалась, вспомнив только один общий факт про задачи такого типа. Потом все же придумала начало решения и начала писать, рассчитывая, что решение додумается по ходу. Так оно, в принципе и вышло: заготовленный для большого извращения map < int, vector < int > > превратился просто в map < int, int > и код в целом получился не такой страшный как обычно. Додуманная на ходу программа успешно проходила все тесты, кроме первого (что для меня вообще очень оригинально, обычно все наоборот), обнаружила мелкий баг, решила сабмитить, пока уже не совсем неприлично мало очком стало. Хотя уже было что-то типа 160-эпсилон очков, так что было в меру неприлично. Увидев, что тем временем народ в комнате уже компилит вторую, решила, что есть смысл ее написать. Но, как потом выяснилось, не до конца правильно поняла условие, придумала не совсем верное решение ну и до кучи даже неверное не успела написать. И еще так увлеклась его написанием, что чуть не прозевала челлендж-фазу.
С челлендж-фазами у меня обычно не складывается. Последний удачный челлендж был чуть ли не во втором дивизионе. В первом же я обычно первые 5 минут пытаюсь смотреть в чей-нибудь код, долго его гипнотизирую, ничего не понимаю и потом еще 10 минут жду, пока освободится
pawa, чтобы закидать его вопросами по поводу того, как же решалась вторая задача. И сегодня я на челлендж-фазу как обычно шла в надежде на просветление. И оно наступило! Еще в процессе решения я заметила одно условие, которое можно забыть проверить. И очень удачно выбрала первую жертву для просмотра кода. Он ошибся ровно в этом месте. Причем я в это не сразу поверила (уж сколько было ошибочных челленджей, когда я не замечала какой-нибудь одной строчки) и даже (первый раз в жизни!) использовала команду find в арене (бывалые олимпиадники, повторяю, не смейтесь слишком сильно ;) ), убедилась в том, что глаза меня не обманывают и кодер действительно забыл проверить это условие. Пример придумался легко. Челленджу. Challenge unsuccessful. И в этот же момент кто-то челленджит эту задачу. Эээх... Еще раз читаю сообщение арены. Challenge successful! Это я просто давно не видела этого радостного сообщения и часто не успевала. Но тут до меня доходит, что ведь и в моем коде это условие даже проверено, но не учтено! Становится обидно. Решаю челленджить дальше. Аккуратно вчитываюсь в решения, внимательно ищу в коде нужные строчки и успеваю почелленджить еще двух кодеров. Ну что ж, 150 очков, против 158 набранных за кодинг-фазу. Прикидываю положение в итоговой таблице - если повезет, то рейтинг все равно немного может вырасти.
Систест. Обидно, конечно, что задача не пройдет, но 3 не слепых и удачных челленджа надо явно записывать в актив. Систест окончен. Начинают поступать результаты по комнатам. Прикидываю свое положение в итоговой таблице - падения рейтинга быть не должно, это неплохо. Вот и доходят результаты до моей комнаты. Ищу себя в конце списка - нету. У меня 2-е место в комнате!!! Тихо офигеваю (но ведь должна была упасть!). Смотрю свой код. Меня спасло то, что переменную curmax я инициализировала не -1, а 0. Смотрю итоговую таблицу - я в топ 100! Пусть не так высоко, как в мое предыдущее попадание в топ 100, но все равно это очень здорово! Топ 100 - это ведь что-то такое запредельное, для Настоящих Олимпиадников.
В общем я теперь опять желтая. Надолго ли - не знаю, но сегодня я собой очень довольна!
Да и мои браунис вроде всей семье понравились ;).
Прошу прощения, если в тексте баги - если я начну его проверять, то половину сотру. И извиняюсь за английские слова, написанные русскими буквами.