За праздники развлекался решением всяких интересных задач по программированию. Основные ресурсы с подборкой задач и роботами-грейдерами -
http://acm.timus.ru и
http://www.spoj.pl. Также с интересом прорешал несколько задач с прошлых Google CodeJam -
http://code.google.com/codejam/contests.html и Facebook Hacker Cup -
http://www.facebook.com/hackercup.
Вообще, как раз Facebook несколько разочаровал. Во-первых, робот на их
страничке с задачками (еще один интересный ресурс) лежит, судя по всему, с начала декабря. Мне это было немного обидно, ибо на днях во время отдыха как раз дорешал давно лежавшую на полке задачу
Small World (заодно узнал про KD trees - игровики-то про них все, наверное, знают, а мне в новинку). Во-вторых, решать их задачи с прошлого Hacker Cup не особо интересно, ибо на посылке решения крутится какой-то бесконечный прогресс бар и ничего не проверяется. Решать без робота, конечно, можно, но зачем, если есть Тимус и Сподж.
Зато скоро будет Facebook Hacker Cup - квалификация 20 января. Не сходить ли? Скорости решения, думаю, не хватит - студенты нынче шустрые, но адреналин-то он и в Африке адреналин. Поглядим.
В целом, в очередной раз убедился, что решение небольших концентрированных задач - замечательных способ вспомнить, то, что знал, но забыл. Или узнать что-то новое, что может и в обычной "продуктовой" деятельности понадобиться однажды. Когда бы я еще почитал про
квадратичные вычеты, как не при решении
этого :-). Или про
KD trees. Или про
Pigeonhole Principle. Или про
DPLL algorithm для решения N-SAT. И не только почитать, а и реализовать и проверить роботом, что усвоил правильно! Идеальный способ для изучения. Чего вот не хватает, так это разумного способа выбрать задачи по данной тематике. Например, я лично страдаю от непонимания основ теории вероятности - где-то упустил основы в процессе обучения в универе, и теперь туплю категорически. Прорешать вязанку задач на эту тему было бы самое оно. Но, увы, выбрать подходящие задачи не так-то просто.
Последнее. Кто-то из френдов как-то писал интересные рассуждения на тему "Если вам кажется, что в задаче не хватает данных, то в этом и заключаются отсутствующие данные". Именно так. Если на первый взгляд
задача кажется NP-полной, то надо внимательнее читать условие...