*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

понедельник, 17 мая 2010 г.

Судоку для программистов или олимпиадные задачи

Последнее время радикально подсел на алгоритмические задачки по программированию.

Каким-то чудом и к великому сожалению сейчас вся эта тема олимпиадного программирования сильно меня не зацепила в школе и институте. Хотя там для этого было бы больше времени.

И самое что в этом всем отрезвляющие, что порой ступор наступает на казалось бы «очевидных» и типа «уже когда-то давно изученных» тобой задачах. Например, практически над каждой из серии «задач для обучения и закрепления материала» по динамическому программированию я изрядно чесал репу, хотя выглядят конкретно они весьма академично. И практически каждую я засабмитил далеко не с первого раза. Думается, что на том же ТопКодере каждая из них была бы первой задачей (то есть самой простой).

Вообще появляется некоторая зависимость. Зависимость от количества решенных задач. После нескольких успешных сабмитов хочется еще, еще и еще, а задачи становятся сложнее и сложнее. Своеобразное программистское судоку.

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

И все это – абсолютное знание. Твой единственный судья – это программа проверки результата и тестовые наборы данных, которые одинаковы для всех. Говорят, что на том же ТопКодере есть пути нечестного поднятия рейтинга, но очень несильно. Если посмотреть на топ-листы независимых онлайновых контестов, то можно увидеть там одни и те же имена. Неужели все эти люди знают как «читить» на всех сайтах? Конечно нет.

Притягивает тут абсолютность знания. Все что нужно, чтобы выиграть – это просто решить задачи быстрее всех. Казалось бы, что может быть проще. Как сказал мне тут один товарищ, что нейроны необходимо постоянно задр***вать, а иначе они теряют эластичность.

Сайтов для онлайнового решения задач много. Я пока остановился на Школа программиста, Timus Online Judge, UVa Online Judge (классика жанра), Codeforces и, конечно, TopCoder (пока только в practice room’ах).

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

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

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

Если вместо сотни красивых слов в резюме про где и как человек учился и над чем замечательным работал, будет просто указана ссылка на профайл того же ТопКодера, то это будет в сотни раз полезнее. Там тебе и примеры кода, и тематика решенных задач, время из решения (после этого можно не спрашивать, как «человек работает под стрессом»), и, что очень важно с моей точки зрения – страсть к программированию, увлеченность (а как иначе можно объяснить многолетнее постоянное участие в «пустой трате времени», как спортивное программирование).

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

Например, другой товарищ рассказывал, когда его стандартно попросили у нас на интервью нарисовать функцию для вычисления чисел Фибоначчи разными способами – рекурсивно, рекурсивно с хвостовой рекурсией, а затем просто циклом, он написал матричный вариант через производящую функцию, который работает за логарифмическое время, вместо линейного. У товарища, кстати, неплохой рейтинг на ТопКодере.

Думается мне, что в принципе люди с относительно высоким рейтингом на ТопКодере проблем с трудоустройством не испытывают.

В общем, решайте задачи, тренируйтесь, держите себя в форме.

6 комментариев:

  1. Когда-то был очень популярен конкурс "Programmer of the month". Есть нетривиальные. Список тут:
    http://potm.tripod.com/problems.html
    К сожалению, после 2000 заглох

    ОтветитьУдалить
  2. Есть еще такой проект, как Al Zimmermann's Programming Contests. Он, конечно, менее соревновательный, но посмотрите на призы ^-^

    ОтветитьУдалить
  3. Ещё очень сильно нравится spoj.pl

    ОтветитьУдалить
  4. Я придерживаюсь противоположного мнения - умение решать олимпиадные задачки еще не значит что программист хороший. Тут как с упомянутым судоку или разгадыванием кроссвордов - практических знаний это не принесет. Это скорее вариант времяпровождения/хобби, которое приносит фан. Алгоритмику подтянешь и "трюки" выучишь эт да, но в промышленном коде, имхо, это не решает. Алгоритм всегда можно посмотреть, главное знать где. А держать их все в голове - это уж чересчур.

    Я сам когда-то занимася олимпиадным программированием. Далеко не уходил, но на на туре сибирь+урал побывал. Курсу ко второму университета я забросил это дело. Лучше это время тратить на освоение каких-либо полезных практически применимых технологий.

    Кстати, а вы случайно в Го не играете? :)

    ОтветитьУдалить
  5. Удивлен что нет в списке: projecteuler.net
    Конечно, он без отправки сорцов, но требует сильного штурма мозгов для того чтобы получить ответ хотя бы в пределах двух минут.

    ОтветитьУдалить
  6. Евгений Коростелев: Если говорить о "играю-играю", то я неплохо играю в русские шашки (не в чапаева ;-). В Го я играю на уровне "знаю правила".

    Решение задач позволяет хотя бы знать какие алгоритмы есть в природе. Например, задача Фермер 2 - вряд-ли я бы сам додумкал до алгоритма со сложностью N*M. Но это задача считается классической - "поиска прямоугольника максимальной площади" - это тут надо просто знать ;-)

    ОтветитьУдалить