?

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

( 59 comments — Leave a comment )
Page 2 of 2
<<[1] [2] >>
kvakosavrus_q
Dec. 26th, 2011 12:24 pm (UTC)
Спешка хороша на соревнованиях и при ловле блох
В реальной работе требуются совершенно другие навыки
Исенбаев Владислав
Dec. 26th, 2011 12:29 pm (UTC)
На topcoder'е есть три градации сложности: на 250, 500 и 1000 баллов.

Приведенный пример, насколько я знаю, был задачей на 250, они всегда тривиальные и если немного тренироваться то можно научиться решать любую из них за 3-5 минут.

Задачи на 500 уже сложнее, на них может уйти 10-30 минут и далеко не все участники умеют их решать. Среди них попадаются интересные идейные задачи, но ~70% все еще достаточно стандартны.

Задачи на 1000 обычно занимают 30-60 минут, среди них почти не бывает стандартных и они по духу близки к олимпиадным задачам по математике, с уклоном в CS. Очень малая доля участников умеет стабильно решать задачи этого уровня и это умение очень трудно "натренировать", в отличие от 250 и 500


Вообще, задачи на topcoder нечасто бывают задачи со сложной реализационной частью и почти не бывают чисто реализационными или на стандартные алгоритмы, в отличие от задач ACM. Есть еще некоторые форматы соревнований, со своей спецификой задач. Если
Исенбаев Владислав
Dec. 26th, 2011 12:31 pm (UTC)
У упомянутой задачи кстати есть простое решение, работающее для любого модуля p, не только для 9
fregimus
Dec. 26th, 2011 09:21 pm (UTC)
Вот это зубодробительно! Не подсказывайте, буду думать!
(no subject) - fregimus - Jan. 3rd, 2012 10:36 pm (UTC) - Expand
(no subject) - Исенбаев Владислав - Jan. 13th, 2012 10:08 am (UTC) - Expand
erofeich
Dec. 26th, 2011 12:45 pm (UTC)
Совершенно лишний навык для программиста, скажем так, работающего на моем месте и в окрестностях.
Я могу себе представить, точнее даже знаю место где сложные задачи могут возникать если не каждый день, то хотя бы регулярно. Если сделать громадное допущение и представить что завтра все такие места раздулись до размеров, ну не знаю там, майкрософта и посадили себе в штат по олимпиаднику, то даже в этом случае, я боюсь, они не смогут обеспечить его подобными задачами на 8 часов в день и 5 дней в неделю.
Лично в моей практике таких случаев не случалось вообще. То есть я сталкиваюсь со сложными задачами, но они скорее о технологическом, или человеческом факторе.
fdo_eq
Dec. 26th, 2011 02:22 pm (UTC)
Для задачи, обозначенной в первой фразе, рекомендую познакомиться с ресурсом "проект Эйлер": http://projecteuler.net/
fregimus
Dec. 27th, 2011 04:47 am (UTC)
Спасибо! Я знаю его, и тоже о нем думал. И, пожалуй, оттуда задачи и возьму.
(no subject) - _navi_ - Dec. 27th, 2011 08:30 am (UTC) - Expand
(no subject) - fregimus - Dec. 27th, 2011 08:56 am (UTC) - Expand
sharpc
Dec. 26th, 2011 02:44 pm (UTC)
250 это способность быстро комбинировать несложные абстракции (скажем, штуки 3: арифметика остатков, свойства булеана, разбиение на цифры) и безбажно переносить их в код — ни о каких классах задач не может быть и речи. 500 и 1000 действительно требуют понимания довольно сложных вещей, которые встречаются на практике не часто, однако и стабильно решает их совсем немного человек: в отношении их в индустрии ценнее, скорее, стремление к совершенству и изрядно прокачанный общеаналитический скилл, чем конкретный опыт.

Локализация бага в обычном промышленном коде, как правило, работа скорее механическая, а вот локализация бага в чужом решении задачи на TopCoder (challenge phase) — действительно нетривиальная задача, тренировка в решении которой заметно улучшает и чтение (подсознательную интерпретацию) обычного кода, и качество его написания (т.к. приучает делать предсказания относительно возможных ошибок на этапе продумывания/написания).

Читая комментарий Исенбаева о тривиальных и стандартных задачах, учитывайте, что разница между средним читателем и ним примерно как между средним читателем и Теренсом Тао :)

Да, полезно. Нет, не обязательно.
pphantom
Dec. 26th, 2011 02:46 pm (UTC)
Сразу оговорюсь, что я не совсем инженер-программист, но писать приходится часто и много...

Нет, подобные навыки практически не востребованы. Более того, как показывает опыт, в некотором смысле они даже вредны (многие слишком увлекаются тренировками к этому виду спорта, полагая, что тем самым научатся программированию).
fregimus
Dec. 26th, 2011 09:23 pm (UTC)
Так и я тоже код-то пишу ежедневно, и думал, что нормально. А вот…
captainl
Dec. 27th, 2011 01:17 am (UTC)
Задачи, о которых Вы пишете, к собственно программерской работе отношения почти не имеют. Теперь вообще математики в программировании стало намного меньше. Правильнее будет, наверное, сказать, что профессиональное программирование очень разнородно. Кто-то специализируется на пользовательских интерфейсах, другие - на обработке изображений, третьи бухгалтерию автоматизируют, четвертые управляют устройствами и т.д. Деньги платят не за решение математических задач на скорость, а за достаточно быстро написанный код, который максимально соответствует требованиям и содержит минимальное количество дефектов. Кроме того, действительно высоко ценятся те люди, которые способны быстро разобраться в чужом коде и найти причину ошибки.

Кстати, Этюды для программистов Уэзерелла не пробовали?
fregimus
Dec. 27th, 2011 04:45 am (UTC)
Мне уже начинает казаться из ответов, что программисты программ почти не пишут (во всяком случае, алгоритмов не реализуют — это явно говорилось), а только ищут в них ошибки. Пока не совсем понимаю, откуда берутся эти программы с ошибками.

На книге Уэзерела я, можно сказать, вырос. Именно с нее я оценил невычислительную сторону компьютеров. До того, как она появилась, ничем, кроме числовых моделей физики, я не занимался и не представлял, что другое бывает!
(no subject) - captainl - Dec. 28th, 2011 01:38 am (UTC) - Expand
racoonbear
Dec. 28th, 2011 07:47 am (UTC)
таких задач в год даже в математическом проекте штук 5 максимум будет.
Так что совершенно некритично. Время уйдёт на другое.
familom
Jan. 3rd, 2012 06:33 pm (UTC)
Это спортивное программирование (:
Забавная с ним ситуация: никто не возмущается, что Шумахер водит не только болиды Ф1, но и обычные, "гражданские" автомобили. Зато в постах про спортивное программирование неизменно появляется пара-тройка человек, кого наличие "олимпиадников" среди программистов доводит до состояния "кюшать не могу". Мне навскидку сложно вспомнить, чтобы кто-то из друзей-олимпиадников требовал на работе исключительно "алгоритмических" задач или считал себя гуру-программистом лишь из-за своего олимпиадного хобби.

На TopCoder'е, кстати, есть соревнования и по промышленному программированию, и по проектированию, и по тестированию.
ald1976
Jan. 6th, 2012 01:04 pm (UTC)
Такие "соревнования" дают одностороннюю информацию - также, как и тесты на IQ.

В случае с IQ тестом:

набрал мало - значит точно дебил;
набрал средне - никакой информации, разве что исключение, с большой вероятностью, случая клинической дебильности;
набрал много - тоже никакой информации, слишком много вариантов: действительно умный, хорошо тренированный, аутист с гиперразвитыми узкими способностями и.т.д.

Что IQ тест, что соревнования по спортивному программированию на гиперскорость показывают только умение быстро решать несложные задачки. А, на практике, надо решать что-то существенно более сложное либо "тупо-трудоемкое", при этом время некритично - лишь бы производственный план выполнялся.


При этом среди супер-скоростных спорт-программеров больше тренированных обезьянок, чем действительно дельных людей. Нет никакой ценности в том, что человек сделал сегодня то, на что его натаскали вчера - в реальных условиях достаточно времени, чтобы решить задачу самостоятельно либо найти готовое решение в справочниках-интернетах.
Page 2 of 2
<<[1] [2] >>
( 59 comments — Leave a comment )