Дорогое сообщество codeforces. Я 8 лет как не в рейтинге и 7 лет как ничего не послылал в систему. И вот однажды на днях меня резко переклинило и во мне проснулся фанат теории алгоритмов спустя 7 лет сна.
Вчера мне в голову пришла странная идея. А что если разработать алгоритм прокачки человека с новичка до топ 10 на codeforces.
И тут сразу пришли следующие соображения.
- Если человек не одарен талантом (гениальностью) его физический предел это 2450 (слабый гроссмейстер). Можно сколько угодно быть натренированным знасть высшую математику всю. Ну нет в человеке творческой нотки и все.
- Если вам кажется что вы гений — поздравляю вы неограничены ничем.
- С чего начинать (какие темы и сложность задач)
Если с темами все понятно — уже изъезженный вопрос, то вот второе — куда более интереснее. Я так понимаю что сложность задач в архиве — это значение почти минимального рейтинга человека решившего его на раунде где была эта задача (я проверял эту гипотезу просматривая результаты всех подряд раундов). Тогда алгоритм прокачки предельно прост
А. С помощью дихотомии по ответу находим границы сложностей задач. Нижняя граница — это самая простая задача которая заставляет сильно думать но не более 20 минут в среднем (но не халявка поэтому именно подумать надо) Например, у меня где-то 2000 вышло. Верхняя граница — это самая сложная задача которая вам поддалась с огромными усилиями вы без помощи смогли ее решить пусть даже это будет единичный случай. Например, у меня где-то 2500 вышло.
Б. Решаем задачи из этого диапазона сложностей потихоньку повышая сложность когда начинаете чувствувовать что способны на большее.
В. А как решать то? Я так понимаю что решение всех задач делятся на 2 этапа 1 — это построение алгоритма решения 2 — это реализация этого алгоритма с решением возможных технических моментов. А что делать если не получается? Тут длинная схема.
- Если придумали кучу алгоритмов решения (бывает и такое) кодируйте все их подряд по не получите полное решение не думая, натренируетесь на реализации покрайней мере новичкам и даже продвинутым будет очень полезно (вдруг вы структуры новые данных для себе открыли или новую тему осваиваете — вот потренируетесь).
- Но что если алгоритмы иссякли а полного решения нет? Тогда смотрим тесты только у которых написано "Неправильный ответ" (да, у некоторых читалей уже сгорело, предполагаю от этой строчки). Объясняю зачем — как понять что алгоритм неверен или баг в коде? Для экономии времени это лучший способ. Смотрите тест — большой — значит мелкий косяк в алгоритме (именно мелкий) или баг (что скорее всего). Если маленький — то в ручную своим алгоритмом посчитайте (как правило на маленьких и падает решение) Если ответ сошелся — баг если нет — алгоритм в корне не верен думайте дальше. Если баг — тогда САМИ (отмечу что сами) придумываете случаи когда программа работает не так как задумано (алгоритм), а не дебажить на том тесте что упало а то не научитесь искать ошибки в коде. Еще стоит обратить внимание на "ошибка во время исполнения или компиляции" — это точно баг в коде тест точно смотреть не надо.
- Читать разбор задач или нет? Мой ответ — однозначно нет. Он нужен лишь в двух случаях. Сравнить свое полное решение с авторским чтобы понять что вы решали нормально (ну или автор намудрил а вы решили проще). Второй случай — когда вы прошли кучу тестов и где-то далеко решение падает на "неправильный ответ" Тогда скорее всего у вас мелкий изъян в алгоритме (один раз только помню чтобы в корне неверное решение прошло все тесты кроме последнего помню был скандал на codeforces что претесты кривые но это очень большая редкость — исключение). Вот тогда возможно либо стоит подумать самим что не так или не мучать себя и почитать разбор — ну тут уже на ваше усмотрение. Интересно мнение сообщества по поводу такого алгортима подготовки до абсолютно любого уровня с любого уровня. P.S. Добавил абзацы а то тяжело читается.
Одно дело научиться решать задачи — придумывать алгоритм и кодировать его. А совсем другое дело — научиться их быстро решать в реальных "боевых" условиях когда время раунда сильно ограничено.
https://codeforces.net/blog/entry/69100
Вот несколько соображений по этому поводу — очень толково написано важность быстрого решения задач. И он прав по рейтингам у него IOI 2018, 2019 gold у меня IZhO 2014 silver — сейчас я совсем другой. Но тогда я был в рейтинге и фиолетовым так что его гипотеза про медали верна. IZho проще IOI но на IOI участников больше да сложность задач мало влияет на расположение мест лишь на точность замеров.
4) анжуманя
Часть про то как решать задачи — а где, собственно, совет как решать задачи, а не как модифицировать уже имеющееся решение ? Вопрос риторический скорее, потому что четкого алгоритма решения задач именно что не существует, но все-таки, тогда зачем столько писать о том, чего нет. Про то, что определить интересующие вас лично задачи сначала это правильно, делать это можно по разному, но суть полезна. Разбор читать или не читать — крайне спорно. Откуда научится чему-то новому тогда, если не брать информацию извне ? А вообще, любой алгоритм проверить бы сначала на каком-то реальном примере. В целом на глазок ничего вроде.
Очень грамотно рассуждаете. Нельзя заниматься только решением задач. А так вырастет опыт в решении задач с помощью только уже известной человеку теории. А новую лучше почитать. Для того чтобы изучать новую теорию необходима причина — в данном случае задача не решается. А как он поймет что именно эта теория нужна? Действительно остается только разбор и читать. Но для тех кто решает 2000+ сложность предполагается что он уже почти ходовое по теории знает и в 90% тупо не догадывается как ее использовать. Дельное замечание до 2000 стоит читать разбор — выше больше на медвежью услугу самому себе похоже.
А почему вы считаете что на 2000+ не появляется никаких новых алгоритмов ? Например, дерево отрезков с массовыми операциями, binary lifting, функция эйлера, множество других алгоритмов появляются на задачах с рейтингом 2100-2200 впервые, и, я думаю, на каждом уровне выше появлятся все новые более сложные алгоритмы для которые тоже надо будет узнать в какой-то момент для успешного решения задач.
Я слишком мало нарешал задач на 2000+ сложности. Возможны вы и правы. Но то что вы назвали это выше 2500+ но я не уверен. Пока я понял что задачи 2000-2500 решаются просто (алгоритм простой) (не нужно городить heavy-light персистентый и даже простой не нужно писать сложные запросы на деревьях отрезков и т.п.) но сложно догататься вот в чем сложность.
не нужно городить heavy-light персистентый и даже простой — да.
решаются просто ; то что вы назвали это выше 2500+ — нет.
Я знаю реальные примеры задач 2100-2200 рейтинга на каждый из названных мной пунктов и мой список можно очень сильно расширить на самом деле.
Ну вот вам например
Фунцкия Эйлера (2200)
Binary lifting (2200)
Дерево отрезков с массовыми операциями (2100)
Извиняюсь, со второй ссылкой промахнулся, не ту задачу дал — исправил, теперь все правильно.
Первые две вещи достаточно ходовые а вот третье — это уже больше на редкость (экзотику) похоже Задачи эти еще не смотрел по ссылкам. Но двоичный подъем я не припомню чтобы использовал часто.
Я соглашусь с вами в том плане, что алгоритмы на кф в целом, и в задачах 2000+, в частности, занимают не такое важное положение, умение думать и тренировка решают гораздо сильнее, но, все-таки ваш арсенал приемов/алгоритмов пополняется с переходом на каждую новую ступеньку и 2000-2500 здесь не исключение.
Кстати 2000-2500 довольно странно ставить в один диапазон — уж слишком большое различие между 2000 и 2500 как по мне.
а что такое персистентный heavy-light?
Есть персистентные структуры данных. Они хранят предудыщие версии самих себя и умеют быстро их откатывать. Например персистентное дерево отрезков. Поступили запросы прибавления на отрезке а потом потребовалось выдать запрос на предыдущие версии и надо быстро дерево откатить по версиям назад. Когда-то пытался здесь решить задачу про рыцаря на персистентную heavy-light декомпозицию. Но не смог освоить персистентность.
Я понимаю что такое персистентность, я не понимаю что такое "персистентный HLD"
HLD — это штука, которая любой путь в дереве разбивает на logn отрезков в перестановке вершин, и всё, куда тут сувать персистентность? :)
Это очень сложно, где-то видел такое.
Ну, 2100 берется только на математике, базовых идей и каком-то умении писать код)
Интересно, чего из этого нет у меня
У меня лично была такая тактика — тупо решать задачи с рейтингом
мой_рейтинг + 200
из архива, если в течении часа не могу решить — смотреть разбор. Нарешав 500 задач апнул КМ с серого ранга таким способом месяцев за 7.Для тех кто в рейтинге — такой вариант скорее всего идеальный. А вот для тех у кого нет рейтинга не ясно что делать. Предлагаю в посте именно для таких.
Рейтинг по идее за 3-4 написанных контеста очень сильно приблизится к реальному- так что люди без рейтинга недели за 2 могут его узнать. Или это какое-то искусственное условие "Не участвовать в раундах" ?
В принципе раунды проходят сейчас чаще всего на выходных и вполне реально найти время и поучаствовать. Единственное что раунды не точно определяют это может ли человек решить задачу в принципе. Были у меня самого случаи на раунде когда не хватило 10 минут докодить задачу С. Очень обидно было что оно получило полное решение на дорешивании. Конечно задачи надо решать быстро.
Да, есть такое, что рейтинг на кф может не полностью отражать твой скилл. Например из за непривычности формата по времени и т.д — если человек привык к 4-5 часовым ROI-style контестам а ему на кф дают два часа и много чуть других задач — естественно он напишет ниже своего уровня. Тут скорее надо смотреть какие задачи будут минимально сложными чисто для тебя и решать их. У меня просто такой проблемы не было, так как я только на кф сидел и больше нигде.
Как красный и тупой могу зявить — ты не умеешь пользоваться пронумерованным списком, а также первый пункт верный.
Вот тут уже давно все написано: https://codeforces.net/blog/entry/98806
Схема работает, до момента, когда упираешься в свой личный потолок
Очень хорошая схема предложена — спасибо за ссылку! Не читая понятно что автор прямо вот конкретно напрягся чтобы такую схему построить.