Привет, CodeForces.
Давно знаю, что многие успешные кодеры(e.g. AlexSkidanov) добивались выдающихся результатов в итоге интенсивного тренировочного процесса, как альтернативы Х годам регулярных тренировок раз в неделю.
Теперь у меня появилось много относительно свободного времени, которое можно потратить на ACM, и я решил посвятить себя тренировкам. Поэтому хочется узнать об опыте людей, испытавших это дело на себе.
На данный момент, я умею более-менее быстро писать халявки уровня Див2 ABCD(иногда Е) и понимаю большинство тем с e-maxx. Однако, довольно много стандартного не умею.
Примерные цели -- попасть на какой-нибудь онсайт вроде RCC(если не в 2013, то хоть в 2014) и постараться до сезона 2015/16 включительно вытащить свой провинциальный ВУЗ, никогда ещё не участвовавший даже в четвертьфинале ICPC, в финал. Так что, пока имеет смысл использовать преимущества prewritten code.
А как тренировались вы (результаты тренировок приветствуются) и что можете мне посоветовать?
В одно лето так получилось что я не работал и все мои родственники уехали на юг, так что я остался один в квартире и решал контесты сутками на пролет с перерывами на поспать. Я решал по три 5-ти часовых виртуальных контеста в день на acm.tju.edu.cn. Затем мои сутки растянулись на 36 часов.
Думаю стоит порешать какие-нибудь простые контесты, например старые американские полуфиналы, там еще про коров куча задач. Причем я решал именно контестами, и писал задачу даже если она оказывалась для меня бояном, или представляла собой скучную и тупую реализацию. На реальном контесте у тебя не будет возможности забить на эту тупую задачу. После этих двух недель я прямо заметил что стал лучше решать и быстрее реализовывать. Правда уровень на тот момент у меня был повыше. Ну и задач на стандартные темы там полно. Я уже писал что важным моментом являются сборы, в частности общение с более крутыми ребятами. Советую ездить на сборы в Ижевск.
Для меня, задачи, в основном, делятся на 2 типа: которые доводимы до конца и к которым не ясно как подступиться. Бывают ещё математики, но это совсем другая история.
Простые реализации я решаю довольно быстро, сложные — нужно подтянуть и вполне очевидно, как это делается. Но что делать с задачами, которые решает куча народу(например, 1000+ на тимусе), но у меня никаких идей по этому поводу?
... и постараться до сезона 2015/16 включительно вытащить свой провинциальный ВУЗ, никогда ещё не участвовавший даже в четвертьфинале ICPC, в финал. Так что, пока имеет смысл использовать преимущества prewritten code.
Как вам в этом prewritten code то поможет? :) Скорее, наоборот, слишком частое использование prewritten code помешает в самый ненужный момент. Это я говорю не потому, что ярый противник, а потому что правилами запрещено.
Насчет подготовки могу сказать, что вряд ли вам сильно поможет решение задач на сложные структуры данных и алгоритмы(типа контестов с Петрозаводских сборов не очень старых), на мой взгляд, чтобы решить нужное вам количество задач в четвертьфиналах и полуфиналах достаточно уметь решать задачки с объемом кода < 50 строк(на не очень простые идеи), хотя это, конечно, не правило.
Попробуйте прорешать много не очень сложных контестов(если не ошибаюсь в Яндекс-тренировках таких много). Можете прямо открыть табличку результатов, убедиться, что много команд решило много задач и в таком случае решать. В отличие от AlexSkidanov, я считаю, что дорешивание задач с контеста всё-же очень помогает (в случае Яндекс-тренировок можно видеоразборы смотреть перед дорешиванием), не вижу другого способа научиться решать задачи, которые раньше решать не умел. А решение огромного числа контестов, на мой взгляд, помогает именно в том, чтобы на решение этих сложных задач время в конце оставалось.
Сколько слышу о "Яндекс.тренировках", но никак не могу понять, где же их найти?
http://contest.yandex.ru/ Нужно войти под любым аккаунтом яндекс — и можно выбирать соревнования в соответствующей вкладке сверху, участвовать виртуально и т.п.
На яндекс-контесте выложена лишь очень малая часть яндекс-тренировок.
Откуда такие сведения? Тренировки проходят на платформе, на которую дали ссылку вверху. Контесты открытые, и никто их потом оттуда не удаляет. В общем все они сейчас лежат там.
Ну хотя бы из тех соображений, что яндекс-тренировки года три уже, наверное, проводятся, причем вроде бы каждую неделю, и очень сомнительно, что содержимое яндекс-контеста — это полный список того, что было сыграно на яндекс-тренировках.
Старые(до выхода яндекс-контеста) не на нем. Новые, как я понимаю все на нем. (По крайней мере, те что по субботам, на нем)
Ну или вот: http://video.yandex.ru/users/ilyakornakov/collection/1/ самое нижнее видео — разбор Japanese contest (Petrozavodsk Summer 2007). В списке на contest.yandex.ru ничего похожего нет
Хорошо. Только раньше тренировки проходили на другом сайте(не вспомню сейчас, на каком), и не удивительно, что их нет на этом. Но все новые (этого года) лежат на яндекс.контекст.
Просто до финала ацм там написано про онсайт личного контеста, на отбор к которому можно пользовать prewritten и этот онсайт планируется раньше :)
Плюс заботать пару десятков шаблонов эклипса довольно тривиально.
Имхо, вопрос не столько в интенсивности сколько в необходимости всё дорешивать и даже сданные решения доводить потом до ума, оттачивая свой код. Prewritten код — это хорошо, даже просто попытка что-то систематизировать уже даёт плюсы. Необязательно всегда переписывать его, можно и в голове держать ибо, к сожалению, на полуфинале (в отличие от финала) он запрещён.
Я тренился в свое время так:
Тренировки реального сета.
- Старался трениться не дома: в ВУЗе, у друга и т.д. Надо чтобы среда была непривычная.
- Решаешь точно 5 часов.
- 3 раза в неделю по 5 часов (по началу больше). Это помимо оф. контестов типа Кубка.
- На тренировке не вставать на задаче. То есть не сдается — бросай, иди дальше. Тут моник не важен.
- По началу тестил на трив проверялке с Тимуса. Потом написал свою систему.
- Стоит прикрутить вирт монитор, на контесте монитор важен.
- Найди хотя бы 1 команду еще. Писать с кем-то приятнее. Даже если другой город и тд
Тренировки дома.
Дорешивай. Алекс Скиданов не говорил, что дорешивание не нужно совсем. Просто когда ты решаешь перед мероприятием, там нет времени, надо отдыхать, а потом опять треня. Когда готовишься без срока — дорешивай! А то не научишься решать. Я выбирал задачи для дорешивания. Некоторые просто без толку решать (допустим там формулу вбить или еще что-то). Смотри разбор, прочти авторское, пойми и напиши.
ТС, Кодефорсес и тд
Где брать задачи?
Они везде. У меня за время АСМ накопилось что-то типа 50 Гб инфы о задачах. Просто ищи и решай. Сейчас еще и есть отличная тема Тренировки. По началу я рекомендую всякие контесты США. Потом Европа (не Польша). Потом наши четверти, школьные сборы. Потом Польша. Потом ПТЗ. НИИРК и финал не трогай пока не выйдешь :) Надеюсь у тебя все получиься :)
Что-то прямо заминусовали :) Немного отформатировал, извините, что не сразу :)
Да поддерживаю по поводу команды с которой решать. Помнится мы Алексом вместе порешивали и на tju, и на Ижевской системе. Также мы тренировались на виртуальных контестах с командами Магнитогорска и Астрахани. Классное было время, много возможностей, жаль что свой шанс я упустил когда он был так близок — второе невыходящее, 13-ое место (среди Вузов, 25-ое по факту), с квотами последних двух лет это выход.
Мне то как жаль :) Хотя цель достигнута все равно, так что все было не зря :) А решать сейчас стало приятнее, когда просто в кайф написать кубок или СРМ.
Вопрос к AlexFetisov и goo.gl_SsAhv — вы в таком режиме тренировались с самого начала или всё-таки было время (и как долго), когда вы решали всё-таки тематические задачи, изучали алгоритмы?
У меня самое начало было на 2 курсе, после сборов в Перми, когда мы заняли последнее место. Тогда небыло сайта Максима и чтобы учить алгоритмы и решать тематические задачи, надо было просто читать Кормена или другие книги. Я так и делал. Еще были статьи: помню статью о структурах данных. Там рассказывалось об интервальных деревьях и о дереве Фенвика. Кстати там было обобщение дерева Фенвика на макс/мин на интервале :) Так вот после тех сборов, где я как раз и познакомался с Алексом Скидановым и Алексом Прудаевым, увидил, как надо укатывать задачи, как это делают профи, я вернулся и стал тренироваться в очень интенсивном темпе. Это про начало. Я не решал конкретно тематических задач, но мне кажется, что сейчас для этого есть возможность. А как учили алгоритмы? Все на сборах. Спросил у кого-то, кто знает, он рассказал, ты написал, вот и новый алгоритм в базе знаний. Все алгоритмы изучились как-то сами собой. Вообще, если честно, мне кажется, что знание алгоритмов в АСМ не самое важное. Многие просто пытаються поставить это наверх. "ООО, да он пишет суффиксное дерево за 5 минут, он крут!" — это несовсем так. Можно уметь писать алгоритмы с e-maxx, но все равно не выходить в полуфинал, а можно не знать, что такое Ахо-Корасик, придумать его на финале и взять золото (есть у меня такой знакомый) :) Базовые вещи, типа дерева отрезков, КМП, обходов графа, или что сейчас база, я наверное уже не знаю, надо знать. Но важно все это не просто писать за 5 минут, а понимать и уметь сводить к ним задачи. Авторы редко просят вас написать конкретный алгоритм, если конечно, это не мой контест :о) Главное, просто решать, много решать, дорешивать, понимать идеи, общаться с ребятами (это вообще основное). Сейчас может быть имеет смысл в тематиках, но не на алгоритм, а на класс, например сегодня решаем задачи на строки, или на графы. Но никак не давайте решим 10 задач на Декартово дерево. Опять я что-то расписался, но видимо, много что хочется сказать :)
Скажу о своих результатах) Я начал заниматься олимпиадами 2 года назад. Что я понимаю под заниматься? До этого не решал ни одной задачи и не написал не одной проги сам. После стал иногда решать тимус(110 задач), писать кф контесты(55~ штук), прочитал половину Кормена и съездил на 3 сбора два Севастополя и один Харьков. В итоге стал учиться в универе на отлично(до этого еле на стипендию выходил). В плане психологии сильно помогло. Если раньше я даже не знал о интернатурах в больших фирмах, то теперь отсылаю резюме с надеждой. Почему я еще не фиолетовый(как минимум)? Думаю все дело в моем отношении к контестам и недостатке математической подготовки. За два года понял что любую тему можно натренировать, но самое сложное(для меня) динамика. Если с пеленок не писал динамику, то потом тяжело придумывать трехмерные динамики. Что делать? Учите математику и успех придет к вам)
Хотелось бы увидеть хотя бы одного человека, который бы писал динамику с пеленок;)
Если есть, то только tourist
Та тут половина пишет контесты с 7-8 класса, а до этого просто в школе решали задачки) Как говорили то ли Копелиович, то ли Нагин. Что Если реально оценивать то перед любым более менее жёлтым 5+ лет математики и программирования
Насколько я знаю, он начал заниматься программированием в 8 лет... немного поздновато для пеленок;)
Ну, если честно, не совсем согласен с последним. У меня мат база не ахти какая. Я все учил сам, по книгам. В ВУЗе не давали совсем ничего. Но динамика — одна из моих любимых тем. Хотя я раньше вообще ее не решал, не видел и не понимал, с пеленок не писал. Мне кто-то советовал решать ТС. И я согласен. Динамика на ТС одна из самых частых тем, по-моему. Что надо знать из математики для ДП? Тоерию вероятности, может быть иногда, комбинаторику, да вроде и все. ДП надо просто решать, вырабатывать подходы. Это не мои слова, а человека, который помог мне научиться решать задачи на ДП. Точнее подсказал, как надо анализировать эти задачи. Недостаток мат подготовки окупается на контестах уменеем решать задачи на другие темы. Хотя если под недостатком мат подготовки имеется в виду все алгоритмы, то да, это проблема.
Ну я заметил такую фишку. Люди которые "нарешали" много задач и благодаря этому стали желтыми(к примеру) после длительного перерыва в решении задач очень быстро скатываються к синему. А с "математиками" другое, они могут раз в пол года писать задачи и быть красными(к примеру). Мне рассказывали о венгерских математиках которые в составе команды выиграли KPI Open, при том что их не было на асм серверах(это я к тому что ребята не пишут программы каждый день)). И в составе участников олимпиады обошли глубоко красных). Или чего-то Миша(сорри, Женя) Капун вспоминается. Это все рассказывалось в пользу математики. В программировании как в спорте. Вы можете довольно быстро набрать форму(1-2 года), но вы ее и быстро потеряете. А математик годами нарабатывает свои знания и может годами их терять(как годами наработанные рефлексы и мышечную память).
Но 3 математика в команде это оверкилл :)
И вообще, программирование(ICPC) такой спорт, в котором имеет значение не больше двух контестов. Остальные — 100% развлечение.
А кто такой Миша Капун? Есть просто крутые люди. Но совершенно не согласен, что можно быстро скатиться к синему. Это значит, что для большинства тренировки, АСМ — просто потеря времени, так как все что нарешал все равно уйдет. Так вот — нифига! Теряется другое. Умение писать контесты. Форму можно потерять, но знания — нет! А форма восстанавливается за пару недель или месяцев.
Похоже, имелся ввиду eatmore, который Женя :)
Та да насчет потери знаний я согласен. (В тему блога) Я думаю что для поднятия своего уровня нужен человек который будет объяснять как делается та или другая задача, который простыми словами расскажет сложный алгоритм. И человек которого вы можете увидеть своими глазами. Что бы не было чувства одиночества в написании кода(призраки не в счет). И в конце концов, человек который напишет вам:"Давай напишем сейчас ВКОШП тренировку". у меня, к примеру, часто бывает что сейчас 19 часов и писать 5 часовой контест до 12 жалко времени, оно же вроде и в институт что-то учить надо и алго новый хочется выучить.
Можно же планировать тренировочный процесс. Например, договориться, что в среду с 5 до 10 вы пишете тренировку, потом обсуждаете идеи, а в четверг пару часов добиваете остатки.
Более того, систематичность тренировок тоже должна иметь свой эффект.
Часто бывает что кто-то предлагает заняться чем-то. И не скажешь в качестве аргумента что пишешь тренировку)(типа, я же серый — какие там тренировки, а для не посвященных друзей так вообще не аргумент)
Но можно же сказать, что идёшь в универ? Чем тренировка-то хуже?
Ты думаешь все сразу с красного начинают? Вообще все хотят, чтобы трениться было с кем :)