?

Log in

No account? Create an account
TopCoder - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

TopCoder [12 May 2010|17:02]
Oleg Eterevsky
[Tags|]

Решил тряхнуть стариной и поучаствовать в этом году в TopCoder Open. Я в эти игры уже года три не играл. Точнее, в один из последних лет я банально забыл пройти квалификацию, в другой -- забыл о первом туре, в третий -- забыл о третьем. Интересно, на каком туре я сломаюсь в этом году? Квалификацию только что прошёл неплохо.
LinkReply

Comments:
[User Picture]From: marinka239
2010-05-12 01:13 pm (UTC)
ни пуха!
(Reply) (Thread)
[User Picture]From: eterevsky
2010-05-12 01:15 pm (UTC)
Спасибо. Надо будет напоминалку себе поставить.
(Reply) (Parent) (Thread)
[User Picture]From: bik_top
2010-05-12 02:03 pm (UTC)
Там по-прежнему нельзя использовать C# 3.0?
Я б в SRM'ах поучаствовал...
(Reply) (Thread)
[User Picture]From: eterevsky
2010-05-12 02:07 pm (UTC)
Я C# не использую, так что не знаю. Python на сегодняшней квалификации использовать было нельзя. :(
(Reply) (Parent) (Thread)
[User Picture]From: bik_top
2010-05-12 02:19 pm (UTC)
>Python на сегодняшней квалификации использовать было нельзя.

Печально. Имхо, если бы кроме императивных языков там были представлены функциональные (Haskell, F#, C#/LINQ хотя бы), они постепенно вытеснили бы C++ и Java — слишком явно их преимущество на SRM-задачах.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2010-05-12 02:29 pm (UTC)
Сомневаюсь. Достаточно посмотреть статистику по языкам на spoj.pl, где эти языки доступны.

В условиях ограниченного времени я бы не советовал писать на хаскелле, код может получиться короче, но он накладывает дополнительный уровень сложности.

В функциональных языка многие конструкции можно выразить очень просто, но там есть тонкости, от которых зависит скорость работы. В C/Java/Python видишь три встроенных цикла и понимаешь тут же, что сложность O(n^3). В функциональном языке так просто не получится. Банальная замена направления fold может сильно изменить производительность.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2010-05-12 02:31 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: bik_top
2010-05-12 03:14 pm (UTC)
Я сужу по своему опыту. Решал «в песочнице» задачи старых SRM'ов на C# 2.0, C++, C# 3.0 (LINQ) и F#.

Решение подавляющего большинства тамошних задач, на мой взгляд, ограничивается лишь манипулированием функциями высших порядков map—filter—fold. Чтобы оно откомпилировалось в Арене, мне приходилось декларативный код переводить в эти ваши вложенные циклы. Что приводило к увеличению кода, времени и числа ошибок.

Вместо манипулирования коллекциями приходится манипулировать элементами этих коллекций.
Вместо комбинирования собственно функций приходится возиться с их аргументами.
Приходится придумывать ненужные имена связанным переменным (pointful programming).
Приходится вводить изменяемые состояния по техническим причинам, объективно не обусловленным. Всё это мешает, отнимает время, внимание, рассредотачивает.

Все эти for, ++j, a[i] — их нет у меня в голове в момент решения, это навязанные языком артефакты.

Есть разные причины, почему в промышленном коде считаются предпочтительными привычные императивные ОО-языки, а не функциональные. Но ведь в блиц-задачах типа SRM — ФЯПы только в путь!
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2010-05-12 03:34 pm (UTC)
И фолды, и циклы обладают своими потенциальными багами. Но вообще, по большому счёту, всё это -- небольшая надстройка. Если рука набита, то нужный код пишется очень быстро. В олимпиадных задачах очень редко упираешься собственно в скорость написания кода. Вот в сегодняшней квалификации, например, было три задачи на 75 минут. Решение каждой занимало не больше экрана. Так что основная сложность именно в том, чтобы придумать что и как, а не написать сам код.
(Reply) (Parent) (Thread)
[User Picture]From: mkevac
2010-05-12 08:33 pm (UTC)
А ты что использовал?
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2010-05-12 11:35 pm (UTC)
C++. VB я никогда не знал и не собираюсь, C# пока не представилось случая выучить, а между Java и C++ с точки зрения олимпиадных задачек разница невелика.
(Reply) (Parent) (Thread)
From: rayevg
2010-05-12 03:02 pm (UTC)
Удачи!
ps
Интересно, в Event Sponsors Яндекс прописался.
(Reply) (Thread)
[User Picture]From: eterevsky
2010-05-12 03:36 pm (UTC)
Спасибо!

С учётом того, сколько народу из России участвует в Топкодере, это вполне логичный шаг для Яндекса.
(Reply) (Parent) (Thread)
[User Picture]From: darnley
2010-05-12 05:35 pm (UTC)
> в другой — забыл о первом туре, в третий — забыл о третьем

topcoder-calendar.appspot.com
(Reply) (Thread)
[User Picture]From: darlam
2010-05-12 05:40 pm (UTC)
Ага. Я тоже уже кучу турниров запорол, банально забыв об очередном раунде. Особенно обидно было, когда один раз я вспомнил о раунде за три минуты до начала, но зарегистрироваться на него уже было нельзя. Кстати сегодня мы в списке результатов оказались на соседних строчках и наблюдать за обновлением результатов после системного теста было немного интереснее.
(Reply) (Thread)
[User Picture]From: eterevsky
2010-05-13 11:57 am (UTC)
Я себе поставил 5 напоминалок про следующий тур. :)
(Reply) (Parent) (Thread)