?

Log in

No account? Create an account

Previous Entry | Next Entry

Приключилось мне в интернетах искать не самые сложные задачи по программированию, чтобы задать ими обучаемых, и набрело в связи с этим на сайт под названием TopCoder, где программисты устраивают меж собою соревнования, кто быстрее разрешит разной сложности задачи. Собственно задач интересных там много, но что меня удивило — это то, с какой скоростью соревновавшиеся решали эти задачи.

Вот, например, задача, которую я могу переформулировать для простоты так. Каждое целое число n изоморфно упорядоченному множеству цифр в своей десятичной записи S(n). Найти сумму по модулю 9 всех чисел, изоморфных элементам булеана множества цифр S(n) данного числа n. Например, для числа 123 это (0+1+2+3+12+23+13+123) mod 9. Алгоритм должен работать по крайней мере для n ≤ 1080.

Задача в принципе не сложная. Мне хватило минут 15 на то, чтобы допереть до алгоритма решения. Что меня потрясло, так это то, что трое лучших олимпийцев решили эту задачу за, соответственно, 86, 90 и 96 секунд. В это время вошло чтение задачи — а там несколько абзацев текста с несколькими примерами чисел, придумывание алгоритма и написание собственно кода. Если до того, как я это увидел, у меня еще были некоторые сомнения насчет своих программистских неспособностей, теперь они развеялись окончательно.

Однажды я прочел книгу по пользованию «Фотошопом», где говорилось, что тот, кто не учится работать с этим редактором клавишами, а тыцает в команды мышкой, не имеет никаких шансов на выживание в скоротечном бизнесе редактирования изображений. Сэкономленные доли секунды в пересчете на каждое действие проводят границу между успехом и неудачей.

В связи с этим у меня вопрос к работающим инженерам-программистам. Скажите, а вы действительно решаете такие задачи за секунды? Насколько вообще напряженна жизнь в вашей сфере? То есть, например, если потратил 5 минут на эту задачу — даже и не думай о том, что напрограммируешь на кусок хлеба, или же все не так запущено? Расскажите о своих впечатлениях от работы.

Tags:

Comments

_winnie
Dec. 26th, 2011 09:33 am (UTC)
А лобовое решение тут прокатывает? Перебрать все подмножества, благо для n < 80 их не больше четырёх штук. А перебирвать подмножества это то что топ-кодеры действительно делали 1000 раз на тренировках.

В реальном программирование такого не надо, там действительно адекватней пример выше - в системе из миллиона строк найти место и починить.

А сложность алгоритмов - сильно меньше, чем их подгонка под реальные человеческие требования, и чаще всего эти алгоритмы уже сидят готовые внутри баз данных или стека TCP/IP.
fregimus
Dec. 26th, 2011 09:37 am (UTC)
Нет, их число растет экспоненциально от количества знаков в заданном числе, как 2k. Для числа 123 их уже 8. Перебор не прокатывает. Все три решения были основаны на признаках делимости, как и мое.
_winnie
Dec. 26th, 2011 09:44 am (UTC)
А, тогда наверно имелось ввиду n ≤ 10^80.
fregimus
Dec. 26th, 2011 09:45 am (UTC)
Ах, да! сейчас поправлю!
aamonster
Dec. 26th, 2011 10:04 am (UTC)
Если я правильно понял задачку, то быстрее написать одну строчку ответа, чем скопипастить и подправить перебор.
_winnie
Dec. 26th, 2011 10:18 am (UTC)
Я недоумевал по поводу ограничения 80, при котором можно в лоб решать без признаков делимости.