Category: здоровье

Category was added automatically. Read all entries about "здоровье".

[topcoder] SRM 252 & 253

Быстро пролетели topcoder SRM 252 и SRM 253. Кратко опишу происходящие события.

На SRS 253 я конкретно отстоялся. На второй задачке я завалился выйдя за предел времени выполнения. Когда прикидывал в голове количество операций, то забыл один нолик. В итоге получилась программа на 10M неочевидных операций, а в 2 секунды это уже не укладывается. Обидно еще и то, что последний тест из примера задачи был как раз на время исполнения, и я пользовался ExampleBuilder-ом, то есть прогонял свое решение на всех тестах. Однако в спешке я не заметил, что последний тест у меня не завершается. А задачка ведь была стандартная и я массу таких прорешал за свою жизнь... А последнюю задачу я просто не смог решать за оставшееся время – не догадался во время соревнования до грамотного подхода (считать отдельно количество путей и мат. ожидание количества очков). Результаты SRM 252 были отменены из-за технических накладок и это мне оказалось на руку.

На SRM 253 я начал очень хорошо – быстро решил все задачи и к окончанию кодирования был на первом месте в своей комнате и на седьмом месте в общем зачете. Однако во время challenge phase меня вывели на чистую воду. В третьей задачке (которую я решал аналитически найдя седловую точку) я не учел граничные случаи когда седловая точка имеет допустимое значение (от 0 до 1) для одного значения вероятности и недопустимое значение (меньше 0 или больше 1) для другого. Было очень поучительно и интересно, так как задачку такого типа мне еще никогда до этого не приходилось решать. В итоге 4-ое место в комнате и 24-ое в общем зачете. Но рейтинг у меня все равно вырос (хоть и чуть-чуть).

P.S. Написал свой собственный plug-in для тестирования Java задач на основе ExampleBuilder. Его легко приспособить для C#, но не для C++, так как используется Reflection по аналогии с JUnit. Он мерит время работы каждого теста и позволяет легко переключатся с запуска всех тестов, к запуску только одного (без необходимости комментировать лишние тесты), что удобно для отладки. Доведу до ума (попробую на очередном SRM) и выложу. Кому-нибудь нужно?

[topcoder SRM 250] В меру сложно и разнообразно

В общем и целом, topcoder SRM 250 оказался интересным и в меру сложным ;) А сдал решение последней задачки буквально за 5 минут до окончания. Чудом решив все задачи правильно я оказался на 6-м месте в общей таблице результатов, что сильно подняло мой рейтинг (до 2215).

Первая задачка была простой, но с подковыркой. Я был уверен, что решение в double-ах пройдет, но, признаюсь, не сильно напрягал голову когда выбирал 1e-9 в качестве эпсилона. К счастью, этого было достаточно.

Над второй задачкой пришлось подумать. Быстро отбросив идеи про жадный алгоритм (не зря я перечитывал теорию матроидов) я придуман динамический алгоритм и приступил к написанию кода. Однако трудность меня подстерегала при вводе данных. Я стал дико тупить и минут 5 не мог сообразить что означает AM/PM нотация для времени. Пытался тщетно сообразить что же именно значит 12:35PM и 12:35AM. Эти потуги происходили когда я уже набил код для разбора строчек вида hh:mmaa самостоятельно. У меня уже было целое число от 1 до 12 обозначающее час, целое число от 0 до 59 обозначающее минуты и флаг AM/PM. Уверенность что я что-то понял у меня так и не появилась, и я удалил написанный код парсинга, поручив всю работу стандартным классам в Java: calendar.setDate(new SimpleDateFormat(“hh:mmaa”).parse(s)). А дальше – calendar.get(Calendar.HOUR_OF_DAY) и calendar.get(Calendar.MINUTE).

Третья задачка была чистой геометрией. Здесь всё было в технике и аккуратности кодирования. На первом этапе надо было найти все точки результирующего многоугольника. Написав этот код, мне пришлось его отлаживать (было несколько опечаток в математике пересечений). Когда отладка была закончена, и у меня был правильный список точек, я просто скопировал свое решение задачки из предыдущего соревнования, которое находит площадь выпуклой оболочки. В первой части решения (ввод данных и нахождение пересечений) я слишком активно пользовался cut-and-paste-ом. Если бы я программировал более структурно (завел бы класс Polygon с методами чтения и проверки точки на принадлежность), то это бы сильно упростило и ускорило бы процесс отладки.