Top Coder SRM 259
Полоса везения продолжается. Я - таргет! Об этом можно было только мечтать. Что ж, теперь надо продержаться как можно больше. Можно было бы, конечно, не писать месяцок-другой, полюбоваться на себя, только вот завтра TCO. Ну, может это и к лучшему.
Решил начать голосовать за задачи, а то стыдно обижаться, что люди не голосуют на TTB, а самому не делать это на TC. В скобках буду указывать (Clarity / Difficulty / Originality).
250 (10/10/7) - после первого прочтения удивился. Потом сляпал какое-то рекуррентное за N^3, все равно не понимая, почему это 250. Как оказалось впоследствии, есть красивый и простой жадный алгоритм. Хорошая задача.
600 (10/10/8) - все было бы очевидно, если бы не надо было возвращать минимальную из искомых подстрок. А 2500^2 сравнений подстрок длины 2500, очевидно, не успели бы. Сперва хотел построить бор, или суффиксный массив реализовать для просмотра подстрок в алфавитном порядке. Потом подумал, что для 600 это все-таки сложновато. Придумал как сделать за 26*2500 сравнений подстрок (причем, реально гораздо меньше). После того, как отослал, долго пытался сломать - не получилось, зато сделал тест для челленджа. Придумал как сделать за 2500 сравнений строк, но решил не перепосылать. Все-таки решение было довольно стремное, но прошло. Задачу действительно можно назвать оригинальной.
900 (10/10/6) - на задаче большими буквами написано ДП. Может сходу не совсем очевидно какое, но минут через пять становится понятным. Решил задачку быстрее всех :)
На челендже двух почеленджили быстрее меня, потом я почеленджил еще двух, а затем, окрыленный успехом, еще двух неудачно - лучше бы я этого не делал... На последней минуте ploh сделал очередной удачный челендж и вырвал первое место, оставив меня со вторым. Впрочем, этого хватило для рейтинга 3005, который больше 3000, а больше мне ничего и не надо было.
Результаты белорусов:
2. ivan_metelsky - 1539.31
107. Hus - 198.13
114. HeaDacHe - 181.05
132. NotImplemented - 101.55
136. Shamaniac - 0.00
У нас никто из сильных не участвовал, поэтому результаты прогнозируемо низкие. Да и вообще, состав участников у СРМа был слабый - многие, наверно, решили поспать подольше перед GCJ Quals, или отдохнуть перед завтрашним TCO.
Сборная по-прежнему на 13 месте. Отдохну пару часиков, и на GCJ!
Решил начать голосовать за задачи, а то стыдно обижаться, что люди не голосуют на TTB, а самому не делать это на TC. В скобках буду указывать (Clarity / Difficulty / Originality).
250 (10/10/7) - после первого прочтения удивился. Потом сляпал какое-то рекуррентное за N^3, все равно не понимая, почему это 250. Как оказалось впоследствии, есть красивый и простой жадный алгоритм. Хорошая задача.
600 (10/10/8) - все было бы очевидно, если бы не надо было возвращать минимальную из искомых подстрок. А 2500^2 сравнений подстрок длины 2500, очевидно, не успели бы. Сперва хотел построить бор, или суффиксный массив реализовать для просмотра подстрок в алфавитном порядке. Потом подумал, что для 600 это все-таки сложновато. Придумал как сделать за 26*2500 сравнений подстрок (причем, реально гораздо меньше). После того, как отослал, долго пытался сломать - не получилось, зато сделал тест для челленджа. Придумал как сделать за 2500 сравнений строк, но решил не перепосылать. Все-таки решение было довольно стремное, но прошло. Задачу действительно можно назвать оригинальной.
900 (10/10/6) - на задаче большими буквами написано ДП. Может сходу не совсем очевидно какое, но минут через пять становится понятным. Решил задачку быстрее всех :)
На челендже двух почеленджили быстрее меня, потом я почеленджил еще двух, а затем, окрыленный успехом, еще двух неудачно - лучше бы я этого не делал... На последней минуте ploh сделал очередной удачный челендж и вырвал первое место, оставив меня со вторым. Впрочем, этого хватило для рейтинга 3005, который больше 3000, а больше мне ничего и не надо было.
Результаты белорусов:
2. ivan_metelsky - 1539.31
107. Hus - 198.13
114. HeaDacHe - 181.05
132. NotImplemented - 101.55
136. Shamaniac - 0.00
У нас никто из сильных не участвовал, поэтому результаты прогнозируемо низкие. Да и вообще, состав участников у СРМа был слабый - многие, наверно, решили поспать подольше перед GCJ Quals, или отдохнуть перед завтрашним TCO.
Сборная по-прежнему на 13 месте. Отдохну пару часиков, и на GCJ!