?

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

( 60 comments — Leave a comment )
Page 1 of 2
<<[1] [2] >>
dimrub
Dec. 26th, 2011 09:07 am (UTC)
Нет, все совсем не так запущено. Мне кажется, умение решать подобные задачки за секунды не слишком коррелирует с умением делать программистскую работу. Ну это как сравнивать мастера-биатлониста и солдата коммандо. Стрелять и там и там надо, причем биатлонист, наверное, даже стреляет точнее, но коммандос из него (в общем случае) никакой.
schegloff
Dec. 26th, 2011 09:12 am (UTC)
Это как спорт высших достижений
Спортсмен из олимпийского чемпиона хороший. А вот работник...
potan
Dec. 26th, 2011 09:13 am (UTC)
Ни когда не умел быстро въезжать в задачу и выдавать нагора результат. Да и не помню, что бы в индустрии это тредовалось (кроме собеседований :-)).
fat_crocodile
Dec. 26th, 2011 09:14 am (UTC)
плюсую к коллегам.
как говорил мой дедушка, спешка уместна при ловле блох.

да и вообще какие-то алгоритмы программировать приходится довольно редко, обычно задача так не стоит
pivovaroffs
Dec. 26th, 2011 09:18 am (UTC)
Не знаю, может где и востребовано - но как бывший программист и нынешний их руководитель, считаю куда более полезным другое "экстремальное" умение:
за несколько десятков минут разобрать, где в системе размером в миллион строк кода находится нужный кусок, почему он падает, и исправить его, не сломав ничего вокруг.
Опять же, такие задачи при нормально поставленных процессах скорее исключение - но они встречаются, в отличие от описанной в посте.
optimist_09
Dec. 26th, 2011 09:22 am (UTC)
Вот такого руководителя не хотел бы:)
Господин Пиваваров, извините,
а где написанные к этому коду инструкции и схемы?
Зачем мучать программеров и заставлять за несколько десятков минут врубаться в забытые программы?
Хороший руководитель имеет необходимую документацию.
Всего доброго, читайте мат.часть и с Новым Годом!
optimist_09
Dec. 26th, 2011 09:19 am (UTC)
Они же олимпийцы!
КАк программист (экс)и преподаватель скажу:
- их же тренируют и, скорее всего, они уже
хотя бы частично этот алгоритм делали,
- возможно у них были заготовки.
Вот так вот :)
Не огорчайтесь ::))
alex_bykov
Dec. 26th, 2011 09:23 am (UTC)
Именно. Поддерживаю оратора. Есть стандартные наработки + умение распознать в произвольной формулировке стандарт.
(no subject) - maxim_mil - Dec. 26th, 2011 03:10 pm (UTC) - Expand
stoshagownozad
Dec. 26th, 2011 09:19 am (UTC)
я тоже читала такое про переводческие программы. дескать, кто мышкой кликает, тот лох и тормоз.

ну, я не знаю, у меня скорость работы примерно 666 (шутка и не шутка, но в среднем от 600 до 670) слов перевода в час с мышкой. Скорость, вообще говоря, неплохая, если судить по итоговым результатам. "Норма" примерно вдвое ниже. Уж я не знаю, сколько слов в час можно выгадать, не пользуясь мышью, тем более, что надо ещё потратить часть ценного мозга на запоминание комбинаций клавиш. Я клавиатурой только в Дежа Вю пользуюсь и в Мемо (потому что там не предусмотрено почти никакх мышьих вариантов), а вот как продуктивно работать в традосе, регулярно нажимая по две-три клавиши служебных - ума не приложу.
aghartha
Dec. 26th, 2011 02:56 pm (UTC)
Прошу прощения у хозяина журнала за оффтоп; а также у Вас, если окажется, что этот комментарий Вам покажется лишним. Но команда "Set/Close Next Open/Get" работает по нажатию ALT и "серый плюсик", а команда "Copy Source" по - ALT и Insert. И они действительно очень удобные и экономят время при работе на "большом" компьютере. На ноутбуке первой комбинации очень не хватает :-/ особенно в "полевых" условиях, без мышки.
(no subject) - stoshagownozad - Dec. 26th, 2011 04:05 pm (UTC) - Expand
(no subject) - aghartha - Dec. 26th, 2011 04:31 pm (UTC) - Expand
(no subject) - fregimus - Dec. 26th, 2011 06:14 pm (UTC) - Expand
(no subject) - sqld - Dec. 28th, 2011 06:03 pm (UTC) - Expand
(no subject) - aghartha - Dec. 29th, 2011 11:47 am (UTC) - Expand
_winnie
Dec. 26th, 2011 09:33 am (UTC)
А лобовое решение тут прокатывает? Перебрать все подмножества, благо для n < 80 их не больше четырёх штук. А перебирвать подмножества это то что топ-кодеры действительно делали 1000 раз на тренировках.

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

А сложность алгоритмов - сильно меньше, чем их подгонка под реальные человеческие требования, и чаще всего эти алгоритмы уже сидят готовые внутри баз данных или стека TCP/IP.
fregimus
Dec. 26th, 2011 09:37 am (UTC)
Нет, их число растет экспоненциально от количества знаков в заданном числе, как 2k. Для числа 123 их уже 8. Перебор не прокатывает. Все три решения были основаны на признаках делимости, как и мое.
(no subject) - _winnie - Dec. 26th, 2011 09:44 am (UTC) - Expand
(no subject) - fregimus - Dec. 26th, 2011 09:45 am (UTC) - Expand
(no subject) - aamonster - Dec. 26th, 2011 10:04 am (UTC) - Expand
(no subject) - _winnie - Dec. 26th, 2011 10:18 am (UTC) - Expand
aamonster
Dec. 26th, 2011 10:02 am (UTC)
Что-то сдается мне, что несколько абзацев текста с примерами понять легче, чем вашу формулировку. Что такое "булеана множество" - я не вполне понимаю... К примеру, сколько элементов в этом множестве для числа 33?
А так - вроде данная задачка решается очень быстро, если сразу вспомнить признак делимости на 9 и сообразить, сколько раз каждая цифра войдет в сумму. Ответ n*trunc(log10(n)+1) mod 9 - верный? Хотя за полторы минуты я бы его наверняка не выдал, даже если бы сразу понял условие.

Но для реальной жизни это и правда не требуется. Т.е. решение алгоритмических задачек встречается - но всегда можно позволить себе посидеть немножко с листком бумаги. И всегда желательно потом еще подумать - а не решается ли она одной-двумя стандартными библиотечными функциями =).

Ну и для меня подобные задачки всегда были легче и приятнее, чем периодически встречающаяся задачка "локализовать баг в миллионе строк кода" - их обычно интереснее решать.
dskrvk
Dec. 26th, 2011 10:23 am (UTC)
И всегда желательно потом еще подумать - а не решается ли она одной-двумя стандартными библиотечными функциями =).
А вот об этом желательно подумать как раз сначала :)
(no subject) - fregimus - Dec. 26th, 2011 09:27 pm (UTC) - Expand
(no subject) - aamonster - Dec. 27th, 2011 05:54 am (UTC) - Expand
jakobz
Dec. 26th, 2011 10:19 am (UTC)
Я работал приличное время в допечатной подготовке. В фотошопе, в частности. Там - да, там заучиваешь все нужные шоткаты, врубаешь fullscreen, и давай какие-нибудь фотки чистить и вытравливать. Чтобы это кормило, надо делать все весьма шустро.

Теперь я работаю программистом. Конкретно мне все эти шоткаты и мега-скорость не так важны.

Возможно если клепать сайты на потоке и этим жить - там надо.

Короче если работа достаточно однообразна - там наверное важна скорость, чтобы конкурировать. Если задачи сложные - там другое важнее.

Мне кажется что топкодер - именно про однообразные задачи. Я его считаю задротством и не люблю.
calcin
Dec. 26th, 2011 10:19 am (UTC)
Я бы предложил отследить корреляцию между классом задач и отдельными успешными программистами.
Например, для этой задачи быстро ответит тот, кто просто "умеет" решать данный класс задач.

Для данной задачи:
mod 9 взято для того, чтобы найти не сумму по модулю всех чисел, а сумму по модулю всех цифр этих чисел (10^n всегда даёт в остатке 1 при делении на 9).

Т.е. фактически из неупорядоченного множества цифр, образующего данное число, составить все неидентичные подмножества и просуммировать все цифры этих подмножеств, поделив после этого на 9. Причём нули и девятки можно сразу выкинуть.

Кстати, я не очень понял. А что, ограничения на числа нет? Допустим, в вашем примере число 3333333 даёт множество S(3333333) = {'3'}, соответственно, оно также изоморфно подмножеству S(123).
fregimus
Dec. 26th, 2011 10:47 am (UTC)
Множество цифр числа, { 3, 3, 3, 3, 3, 3, 3 } в данном случае. Это разные тройки. Наверное, я не очень хорошо переформулировал задачу.
rwalk
Dec. 26th, 2011 10:29 am (UTC)
Этот пример все-таки не столько программистский, сколько математический. Терпеть не могу олимпиадные задачи, но тут думать действительно долго не надо. У меня другой вопрос к программистам - будет ли для них существенно отличаться время написания соответствующего кода от времени написания математиком формулы (a1+...+ak)2n-1 (mod 9)=n2n-1 (mod 6) (mod 9)? И при чем тут 1080?
janatem
Dec. 26th, 2011 11:13 am (UTC)
Согласен, что это чисто математическая задача. У меня получился такой же ответ за несколько минут (только у вас опечатка — справа от знака равенства n используется как длина числа и как само число).

Даже если забыть про теорему Ферма или про функцию Эйлера, всё равно записанное в лоб выражение N*2^(n-1) (mod 9) вычисляется мгновенно для чисел, занимающих единицы байтов в разумном представлении.
(no subject) - rwalk - Dec. 26th, 2011 12:30 pm (UTC) - Expand
_aristeo
Dec. 26th, 2011 10:29 am (UTC)
Да ладно, при чём здесь программистская неспособность? Задачки подобного уровня - это не столько программирование, сколько спорт. И решают их быстро спортсмены, т.е. люди, которые почти каждый день тренируются решать такие задачи на скорость. Именно отсюда и берутся все эти чемпионы мира по программированию в acm-icpc. Труд же программистов, которые создают и поддерживают различные проекты и получают за это деньги - это нечто иное.
rombell
Dec. 26th, 2011 11:13 am (UTC)
Водитель такси и гонщик формулы-1.
Гонщик может проехать гораздо быстрее, но только в строго отведённых местах. Таксист же знает в своём городе закоулки, срезы, объезды, умеет договариваться с гайцами, усмирять клиентов, может отремонтировать машину (хотя бы знает куда ехать) и т.п.
Совсем другие навыки и другие знания.
gadyuka
Dec. 26th, 2011 11:59 am (UTC)
На практике приходится решать совершенно другие задачи: задачи архитектуры, задачи нагрузки, задачи безопасности, задачи совместимости, задачи оптимизации и т.д. И все это за секунды никак не решается. А чаще всего абстрактно не решается вообще никак - а только через тестирование. Ну и, да, как многие отметили - задачи поиска и исправления ошибок в чужом коде.
Page 1 of 2
<<[1] [2] >>
( 60 comments — Leave a comment )