Friday, July 29, 2011

Topcoder. String compression.

В прошлый раз, я писал о своем желании провести детальный разбор решений лучших участников топкодера с целью постичь их тайное дао и примкнуть к их рядам. Итак отчитываюсь.
Первым делом я решил разобрать решение победителя последнего онлайн тура Topcoder Open 2011, участника из Китая, с ником ACRush. Его решение было написано на C++ и состояло из более чем 1800 строк кода. Для того чтобы это переварить, я решил переписать его решение на Java.

Для тех кто не в курсе, расскажу условия задачи. На вход вам давалась некая строка, длинной до 100000 символов. Вам нужно было её сжать, представив в виде нескольких строк вида:

1: abc2a3sd4
2: qwelwesdfdf
3: erwe2rew4dfds
4: qweqwe2dferw

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

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

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

Более точно условие задачи можно прочитать тут.

Wednesday, July 13, 2011

Немного вечерней философии...

Сегодня для меня завершился очередной Topcoder Open, не буду скрывать, в глубине души я все-таки надеялся попасть в финал. Но, надежды надеждами, а результаты так себе. И вроде бы с одной стороны можно успокаивать себя прогрессом, два года назад я вообще не прошел в третий тур, год назад я был на 66-ом месте, а в этом году предварительно на 52-ом, но уж больно медленный этот прогресс. И особенно обидно осознавать, читая описания решений лидеров, что идея то решения была правильной. Как всегда, не хватило каких-то деталей реализации, каких-то мелочей, из которых, конечно же, в нашем деле состоит всё.

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

Я постараюсь, да да, знаю, я уже много чего наобещал за последнее время, но все же, я постараюсь разбирать решения и публиковать тут детали реализации. Зачем? Прежде всего чтобы убедиться, что я сам всё понял, ведь лучший способ разобраться в проблеме это рассказать её другим людям, правда?

Надеюсь, что среди читателей этого блога найдутся еще желающие улучшить свои навыки спортивного программирования, если да, то пишите в комментарии или в почту, пообщаемся. Учиться вместе намного веселей ;)

Tuesday, July 12, 2011

Метод опорных векторов с примерами на R


Друзья, после продолжительного затишься, я продолжаю тему "data mining с примерами на R". И эта статья посвящается методу опорных векторов (в английской литературе support vector machines или, сокращенно, svm). В интернете масса информации по этому методу и, как всегда, она изобилует сложными математическими формулами, за которыми теряется общая идея. Поэтому я решил написать эту статью без единой формулы, в конце концов, если кому-то нужны формулы, он всегда может обратиться в википедию, скриншот из которой вы можете увидеть слева.


Итак, в чем же состоит идея метода опорных векторов? Давайте, сначала рассмотрим очень простой случай. Предположим, что у нас есть множество точек на плоскости, часть которых относится к классу A, а другая часть к классу B и есть точки класс которых нужно определить. Задачу такого рода, по-научному можно определить как задачу классификации, причем, для её решения, нужен алгоритм обучения "с учителем". Метод опорных векторов как раз подходит именно для таких задач.