Wednesday, July 13, 2011

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

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

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

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

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

7 comments:

  1. А что вы можете посоветовать помимо наработки задач с того же TopCoder (я имею ввиду practice rooms)? Может быть книжечки какие-то хорошие. Язык - c++

    ReplyDelete
  2. Мне нравится Кормен http://www.rsdn.ru/res/book/prog/basic_algorithms.xml, еще хвалят Скиену http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1849967202/ но у меня с этой книжкой как-то не сложилось :)
    А вообще, лучше практики может быть только практика. Так что, решене задач вряд ли можно чем-то заменить.

    ReplyDelete
  3. Есть волшебный сайт http://e-maxx.ru/ для фанатов спортивного программирования.

    Я как-то увлекся темой около года назад, и не могу сказать, что ощущаю сильный прогресс. Я в основном люблю задачки на ДП и графы. Но все равно, даже после освоения базовых тем ДР типа скобочные последовательности, строки и т.д. любая новая задача обычно вводит в ступор. Я сижу на acmp.ru, и често говоря, из раздела ДП задачи со сложность выше 60% могу у меня занимают по несколько дней на решение. И как-то прогресса не ощущается. На TC в Div2 я обычно решаю 250 и иногда 500, что, конечно, крайне слабо. В общем, также интересуюсь с кем можно обсудить задачку другую, более менее вменяемой сложности, не 500 или 1000 Div1 ;-).

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

    Я как-то в блоге (http://easy-coding.blogspot.com) пишу про алгоритмы, но обычно людей это не шибко интересуют.

    Удачи.

    ReplyDelete
  4. Александр, спасибо за ссылку, отличный сайт.

    DP это мое слабое место, и вроде всё понятно, и теория изучена, а чуть задача посложней и всё, приехали.

    Если снова возникнет желание обсудить какую-нибудь задачку - пишите, обсудим :)

    ReplyDelete
  5. Отличное начинание!
    И Вам полезно разобраться, и нам полезно прочитать :)

    ReplyDelete
  6. Привет!
    Я прогнал твою программу через свой тестер и сравнил со своими результатами. Кроме тех случаев, в которых твоя программа находила оптимальное решение, могу выделить три области:
    - длина исходной строки равна 100000. Нужно было увидеть, что несмотря на то, что программа рапортовала "Exact solution", результат был очень низким. Проблема в обработке "отрезанного хвоста" (вернее в ее отсутствии). Поскольку такие тесты составляли примерно 13%, можно сказать, что очков 10 в предварительном тестировании ты на этом потерял.
    - err > 0.3 Я не разбирался, как ты восстанавливал исходную строку (боролся с шумом), но, очевидно, здесь твой алгоритм сильно уступал лидерам. Это следующий уровень, и мне самому здесь еще учиться и учиться.
    - err > 1.0 Я не уверен в точной границе, но я заметил, что при больших значениях err, твое решение было стабильно лучше моего. К сожалению, разница была не столь существенна, чтобы компенсировать потери от предыдущих пунктов.

    Мой первый совет, наверное, очевиден: тщательнее тестировать. Нужно постоянно отдавать себе отчет в том, как ведет себя решение в разных областях параметров: делать специальные прогоны с фиксированными параметрами (например, err=1.0 или len=100000), вводить дополнительные метрики (я, например, сравнивал свой результат не только с данной строкой, но и с исходной), делать специальные submits, которые будут давать результаты только для ограниченной области параметров. Я больше чем уверен, что скажи тебе кто-нибудь, что у тебя провал на случаях len=100000, ты бы понял, в чем проблема, и исправил бы ее.

    Успехов,

    -- olg2002

    ReplyDelete
  7. Большое спасибо за советы и столь детальный ответ! Буду работать.

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

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

    Сейчас разбираюсь с решением ACRush, можно сказать, восхищен его подходом. Как только разберу по частям всё его решение, а там 1800 строк убористого кода, напишу.

    ReplyDelete