Дорогие друзья всех с наступающим новым 2014 годом!!!
Проблема собственно такая...
Участвуя в различных контестах, я начал замечать, что кроме задач на реализацию мне проблематично что-либо решить. Были попытки (много попыток) самостоятельно изучать базовые алгоритмы, но на реальных задачах применять их не получалось, даже на не совсем сложных. Однако заметил такую особенность, если человек объясняет мне алгоритм, то мне все понятно и уже через некоторое время, применение этого алгоритма не вызывает у меня проблем.
Поэтому хочу обратится к более опытным людям с вопросом, как вы самостоятельно осваиваете и закрепляете полученные знания? И как вообще можно и нужно проводить самостоятельную подготовку? Какие алгоритмы изучать в первую очередь, а какие чуть позже?
Заранее огромное спасибо за ваш отклик!)
Поначалу можно читать лекции и параллельно решать задачи на сайте http://informatics.mccme.ru/
После этого, как почувствуешь, что уже более-менее хорошо способен оперировать базовыми алгоритмами, можно расширять пространство для изучения другими сайтами, где отдельно изложены алгоритмы более высокого уровня (например, http://e-maxx.ru ). Также имеет смысл прорешивать архивы с задачами (http://acm.timus.ru/, http://e-olimp.com, например). Со временем, после того, как, так сказать, набьёшь руку, при виде задач уже подсознательно будешь перебирать задачи со схожей формулировкой, которые решал раньше и, как следствие, будешь быстрее их решать. Исключением можно выделить различного рода конструктивные задачи. Здесь уж просто знание алгоритмов не поможет, к ним особый подход нужен =)
P.S. Если говорить о закреплении знаний, то, пожалуй, наиболее важное в этом деле — решение задач на свежеизученную тему. Так и тема лучше запомнится, и сразу узнаешь о подводных камнях, которые ожидают при реализации алгоритмов.
Огромное спасибо, думаю, что это наставление принесет большую пользу, как для меня, так и для людей находящихся в похожей ситуации!)
Ага, а ещё как для Вас, так и для людей, находящихся в похожей ситуации, принесет большую пользу поиск по тегам.
Согласен, уже исправил)
Отправлять серого на Тимус — это не слишком жестоко?
А я бы сделал акцент не на алгоритмах, а на задачах. Решать все подряд на том же СF, юзать разборы, в случае необходимости — учить соответствующие алгоритмы.
Мне вообще с ходу приходит в голову очень мало "стандартных" алгоритмов, которые необходимо знать. Давайте попробуем прикинуть.
Теория чисел — проверка на простоту, разложение на простые, Эвклид, быстрое возведение в степень.
Графы — обход, кратчайшие пути. Возможно еще что-то вроде паросочетаний или поиска мостов.
Строки — хеши... Ну еще бор, и то не факт.
Геометрия... Бинарный/тернарный поиск. Какие-нибудь оболочки еще.
Структуры данных — декомпозиция или дерево отрезков.
Ну и все.
Дальше остаются различные вещи вроде комбинаторики — "как понять, что перед нами размещение, а не выборка". И динамика, динамика, динамика. По динамике есть учебники? :) Задача-разбор, задача-разбор — вот и все изучение динамики.
Что забыл из важного? Сортировка... Я, например, вряд ли смогу написать сортировку. А зачем? Есть sort — так зачем оно мне? Имею общее представление о том, как оно работает, ну и ладно. Главное — работает.
Реальность такова, что адекватные авторы составляют проблемсеты с учетом и опасением того, что потом в обсуждении этого соревнования могут написать "фи, гадость, очередная тупая безыдейная задачка на поток, надоело уже, давайте что-то более интересное". Обратное справедливо разве что для тематических контестов на сборах.
Может, и жестоко, хотя, как мне кажется, первые, скажем, 50-70 задач ну точно должны быть по силам даже серому (если задачи отсортировать по сложности). Но увы, как и, пожалуй, все люди, я могу говорить лишь о том, что принесло хоть какую-то пользу лично мне =)
А мне то, что я описывал очень сильно помогло в том, чтобы, наконец, закрыть критические дыры в самых основах, очень сильно мешавшие чего-нибудь добиться. Если бы я просто прорешивал задачи (а примерно этим я и занимался где-то год назад), то далеко не факт, что я бы достаточно быстро узнал всё то, что можно узнать, целенаправленно изучая всякие теор. материалы.
Насчёт задачи-разбор по динамике, кстати, не совсем согласен. Вот, например, динамика по профилю. Часто она встречается где-либо, чтобы ждать, пока такое попадётся на контесте? Очевидно (а может и не очень), что нет. И при этом она из тех приёмов, к которым, ИМХО, ну очень сложно прийти самостоятельно.
С другой стороны, ты красный, а я фиолетовый, так что вполне вероятно и то, что я ошибаюсь =)
О да, уже сутки как красный, что тут сказать... Можно подождать 1-2 раунда, чтобы это изменилось, и тогда мои взгляды опять станут менее правдоподобными:)
По поводу динамики по профилю — я бы применил подобные рассуждения и в обратную сторону. Если она действительно встречается так редко, что на нее нереально попасть — так зачем ее знать? Все равно ведь шанс на то, что она попадется — близкий к нулю. Если же это предположение выглядит абсурдным, то и начальное не такое уж удачное. И на самом деле она попадается достаточно часто.
Я не знаю, где граница между достаточно часто и недостаточно часто. Я за декабрь видел примерно 4 или 5 задач на динамику по профилю. По сравнению с, скажем, сотней задач на различные вариации dfs — это мало. Но ведь для того, чтобы увидеть новую для себе идею в разборе — достаточно и одной.
Ну я за последний год видел только одну динамику по профилю на реальном контесте (хотя стоит признать, что я отслеживаю намного меньше контестов, чем следовало бы для адекватного разговора о том, насколько часто она встречается). И незнание этой техники стоило весьма многого =)
Ответ на то, зачем её знать — вероятно, затем, что попасть на неё как раз реально, при чём в самый неожиданный момент на каком-нибудь серьёзном ИРЛ контесте, например, а не на раунде в КФ, который является лишь тренировкой (что кстати, опять-таки, ИМХО, более вероятно). И в любом случае, как мне кажется, одного разбора и краткого знакомства с таким типом задач недостаточно — нужно отдельно изучить тонкости, чтоб в следующий раз, если что, быть во всеоружии, не?
P.S. Вот представил я, что было бы, если б ДП только по разборам изучал и отдельно на нём не останавливался. Вот не покидает ощущение, что это вылилось бы в регулярное наступание на одни и те же грабли и фейлы в попытках угадать динамику в задаче. У тебя таких проблем не было? Оо
У меня они, вероятно, и сейчас есть, такие проблемы)
А как изучать не по разборам? Динамика — это ведь, если я правильно понимаю — "вот вам ациклический граф, пройдитесь по его топсорту и что-то посчитайте". Только сведение к графу от задачи к задаче отличается. И то, что нужно посчитать и как его считать.
Ну и спасает то, что авторы редко подходят к процессу творчески. Едва ли не прямо указывают асимптотику решения в разделе "ограничения")
Есть какие-то учебники на эту тему? В моем представлении — бывает только "смотри, чувак, вот еще бывают задачи вроде такой (далее следует описание задачи), ты вряд ли умеешь их решать, так вот общая идея там такая (далее следует разбор этой задачи)". Чем это сильно отличается от прорешивания с разборами? Разве что тем, что шанс изучить конкретную идею зависит не от частоты этой идеи в задачах, а от выбора тренера/учителя. Какие есть другие способы обучения?
Ну мне более-менее разобраться с динамикой сильно помог вот этот раздел на информатиксе, например. Дальнейшие уже познания в ней — таки да, уже упомянутое "задача-разбор" =)
Про какие-то книжные учебники и не знаю...
Надо будет, что ли, и мне почитать про динамику по профилю) А то даже не представляю, что это такое =)
Окей, я понял. Незнание динамики по профилю — необходимое условие для становления красным Оо
Загуглил "определение". Как я понял, это динамика, в которой состояние задаётся битовой маской. Ну собственно такое я встречал, кодил и знаю. Но то, как оно называется, не знал =) Да и теорию по этой теме специально не изучал.
А вообще, в тему о "красном", вся теория, что я на данный момент знаю, это по сути всё то, что расписал LeBron. Ну и плюс теория игр и СНМ.