Форум DL

Мой профиль

Оттолкнутся предлагаю от обсуждения это поста на CF
[Tutorial] A way to Practice Competitive Programming : From Rating 1000 to 2400+
Masataka Yoneda, Япония, Токио - международный гроссмейстер

Вот мой конспект важных мыслей этого поста

Быстро писать!

1000 - > 1400  
       Достаточно за 5-10 минут писать переборы и симуляции, и уметь выделять случаи в задаче (N=2, N=3, N>=4)
1.	Я не понял, почему до 1400 лучше тренироваться на atcoder?
2.	Разборы на японском – а автопереводы на английский возможны?

1400 -> 1900

     Надо знать по теории 
         Brute force DP DFS BFS Dijkstra Bitmasks Binary Search
         Mod inverse https://cp-algorithms.com/algebra/module-inverse.html
         nCr, nPr         Функции сочетания (nCr)  и перестановки (nPr)  
         https://support.casio.com/global/ru/calc/manual/fx-82ESPLUS_85ESPLUS_95ESPLUS_350ESPLUS_ru/function_calculations/permutation.html
         Binary Indexed Tree    https://en.wikipedia.org/wiki/Fenwick_tree
         поднять общую математическую подготовку (возможно точнее умение придумывать решение)


1900 –> 2200

     Надо вдобавок знать по теории
          segment tree with lazy propagation

          There is one more important thing to gain rating in Codeforces. 
          To solve problem fast, you should equip some coding library (or template code). For example, I think that  equipping 
              segment tree libraries, 
              lazy segment tree libraries, 
              modint library, 
              FFT library,
              geometry library, etc. is very effective.

2200 -> 2400

            You should solve difficult problems which are only solved by less than 100 people in Div1 contests

Мой профиль

My opinion on how to practice competitive programming
(легендарный гроссмейстер Mateusz Radecki, Польша)

Соревноваться на регулярной основе – не реже раза в неделю.
Практиковаться при первой возможности.
Не противопоставлять занятия жизни. Да, они отнимут много времени. Не нравится – не занимайтесь.
Решайте задачи на те темы, в которых Вы слабы.

What I believe you should do to get out of Gray
гроссмейстер Shayan

1. Решить много простых задач (Задача, которую Вы решаете, должна соответствовать Вашему текущему уровню.)
2. Реализация, перебор, математика! (Начните с задач этих трёх типов).
3. Решите 300 задач на CF
4. Участвуйте во всех CF-контестах
5. Читайте коды других участников

Competitive Programming Roadmap (target: [gray, blue])
гроссмейстер Valerio Stancanelli, Италия,

Коротко, для тех, кто не любит много читать
• Список и порядок решения задач Здесь (до синего на CF).
• Список содержит ~ 100 "must-know"(должен знать) задач по различным темам: ad-hoc(конструктив), STL, дихотомия, ДП, теория чисел, графы.
• В конце документа есть подсказки к решениям всех этих задач – пользуйтесь, если не можете придумать.

Почему?
Вы должны идти в двух направлениях "what to think" и "how to think"
• "What to think": нужно знать определённое количество стандартных алгоритмов
• "How to think": уметь придумывать решения.

Как работает «список и порядок задач»?
Он содержит ~ 100 задач, в основном с AtCoder, Codeforces и Italian online judge.
• "What to think": это задачи от div2A до div2D-E.
• "How to think": это нестандартные задачи, большинство из них требует новых конструктивных идей.
• Условия короткие, не требуется излишних деталей реализации.
• Задачи разделены по темам. Однако секции 5 и 6 содержат задачи без тем – для тренировки.
• Включены задачи различных уровней сложности (от 0 до 6 звёздочек)
• Если Вы не можете решить задачу – почитайте подсказки в конце документа – если и это не поможет – читайте авторские описания решений на Codeforces и AtCoder).
В идеале, чтобы сдать задачу, Вы должны читать подсказки не более чем в половине задач и смотреть авторские описания решений всего несколько раз.
В то же время, после сдачи задачи, полезно почитать и то, и другое для саморазвития.

Что потом?
USACO Guide
Codeforces problemset
AtCoder problemset

Мой профиль

Pro Tips — get them while they are free
Легендарный гроссмейстер Алексей Данилюк, Украина, Харьков (Um_nik)

Не беспокойся о рейтинге
Не используй более одного аккаунта
Пиши контесты
Пиши AtCoder
Не решай по темам
Дорешивай на свой следующий уровень

Не навязывай себе идеи или алгоритмы при решении проблем.
(Do not force ideas or algorithms on problems)

Задай себе вопросы

Когда читаешь условия задачи
• Почему здесь такие ограничения? Как изменится задача, если не будет этих ограничений?
• Что необычного?
• Что задача требует от меня сделать ?
• Могу ли я переформулировать задачу как некоторую стандартную? Как специальный случай некоторой сложной (NP-полной может быть) задачи?

Когда решаешь задачу:
• Как я могу решить более простую версию этой задачи? Уменьши ограничения. Измени объект исследование на что-то более простое:
[граф] > [связный граф] > [кактус] > [цикл] > [дерево] > [бамбук/массив] или [звезда]; [матрица/решётка] > [массив].
Есть ли наблюдение, которое верно и для более общего случая?
• Как ответить на один запрос?
• Как я могу решить маленький пример на бумаге? Как я могу решить задачу без ограничений по времени и памяти??

Прежде чем писать решение:
• Какова сложность?
• Я правильно понимаю задачу?
• Какие функции мне нужны?
• Какие места самые сложные? Что я должен помнить, чтобы корректно их реализовать? Могу ли я сделать их проще?
• Какое место самое медленное? Где я должен беспокоиться о константе-множителе? Где я могу выбрать более медленную но более простую реализацию?

Если решение не прошло
• Я помнил обо всех сложных местах?
• Это решение правильное?
• Я правильно понимаю условие задачи?

Если у тебя есть тест на котором решение даёт неправильный ответ
• Решение делает то что планировалось?
• Проблема в коде или илее?

Если стресс-тест не может найти контр-тест:
• Я точно правильно понял условие задачи
• Моё переборное решение точно полное? Оно использует некоторые предположения наблюдения из основного решения?
• Я генерирую все возможные варианты? В задаче мультитесты? Я генерирую мультитесты?

После того, как решение прошло
• Что я мог сделать лучше?
• Что заняло у меня больше времени чем я думал?
• Есть ли возможность упростить реализацию?

Мой профиль

The Reason You are Bad at Codeforces — You are Not Russian Enough
Международный мастер Zhongtang Luo, Purdue University (макс. гросмейстер)

Я разделяю все проблемы спортивного программирования на три группы
1. Observation — способность понять задачу и придумать нетривиальные свойства.
2. Technique — способность применить хорошо известные алгоритмы и структуры данных к задаче
3. Implementation — способность быстро кодировать и отлаживать.

Я связываю их с национальностями так: «Русскость», «Китайскость», «Американскость»

Observation (Russian-ness) - Наблюдение

Observation означает, что Вы работаете над какой-то задачей значительное количество времени и Вы способны в результате свести её к более простой задаче.
Пример такой задачи 1889D. https://codeforces.com/contest/1889/problem/D
Несмотря на то, что её рейтинг 3000, она решается в 30 строк тривиального кода. Конечно, есть и другие такие задачи, например 1916D https://codeforces.com/contest/1916/problem/D и 1916H1 https://codeforces.com/contest/1916/problem/H1
но суть в том, что задача требует хорошее математическое мышление и ничего больше.
Я называю этот аспект трудности Русским, потому что такой тип задач наиболее часто встречается на русских ICPC контестах, особенно OpenCup и ICPC-лагерях.
Они также являются самым популярным стилем задач на Codeforces и AtCoder.
Этот навык настолько коррелирует с математическими навыками, что Вы буквально можете решать задачи финалов международной олимпиады школьников
по математике(IMO) вместо задач Codeforces. Например, если Вы посмотрите на этот список задач с IMO 2022 https://www.imo-official.org/problems/IMO2022SL.pdf
и комбинаторные задачи в нём, Вы можете увидеть, что они прекрасно трансформируются в задачи Codeforces Div 1.
Есть поговорка, что в Codeforces специалисты по математике имеют преимущество перед специалистами по программированию и я думаю,
что это в некоторой степени оправдано.

Technique (Chinese-ness) - Техника

Technique это наиболее общая вещь, которую Вы можете изучить в спортивном программировании, например бинарное возведение в степень, дерево отрезков и т.д.
Очевидно трудно полностью разделить технику и наблюдение, но я рассматриваю технику как способность разработать правильный код для поставленной задачи.
Поэтому динамическое программирование и жадный более русские, а дерево Фенвика или дерево отрезков – более китайские. Я называю эти задачи китайскими
потому что на китайских OI и ICPC имеется тенденция давать задачи которые решаются только с помощью продвинутых структур данных, а это возможно
только если у Вас есть заготовленный правильный код (reference code). Например, 104857 https://codeforces.com/gym/104857/problem/C решается только
деревом палиндромов, а 104857 решается только если вы прошли этот курс https://zhtluo.com/cp/lll-yet-another-paper-reading-problem.html.
Я думаю, это наиболее поддающаяся обучению часть и чем будет заниматься большинство изучающих спортивное программирование.
Теперь становится интуитивно понятно, почему так тяжело улучшить свой рейтинг на Codeforces: Вы стараетесь стать китайским, вместо того чтобы стать русским.

Implementation (American-ness) - Реализация

Это относится в основном к задачам, которые требуют много времени на реализацию, таким как геометрические задачи, которые очень популярны на американских
контестах, например, 104757С https://codeforces.com/gym/104757/problem/C с последней ECNA. Я думаю, что есть две основные трудности в реализации.
Первая – что код длинный, хотя и не особо сложный, как например задача «Кубик Рубика» https://www.acmicpc.net/problem/6063.
Другая сложность – что код состоит из рассмотрения множества случаев и и это тяжело сделать правильно, например 104869I https://codeforces.com/gym/104869/problem/I
Я называю такие задачи американскими, потому что они очень популярны в американских региональных ICPC-олимпиадах.

Summary

А какое место во всем этом занимает Codeforces?
Здесь я сделаю одно смелое заявление: сейчас для Codeforces вам нужен только курс по математике Leetcode для средней и старшей школы,
чтобы добраться до синего.
Я попытаюсь обосновать это в этих двух утверждениях.

Утверждение 1. Чтобы стать синим, достаточно завершить Div2 A,B,C в течение часа.

Это тривиально проверяется анализом прошедших контестов.

Утверждение 2: Div. 2 A, B, C не требуют ничего кроме основ программирования и хороших навыков в математике.

Это более спорно. Но это моё мнение.
Теперь мы можем ответить на главный вопрос:

Как я могу улучшить свой рейтинг на Codeforces?

Множество людей на Codeforces отвечают, что надо просто решать больше задач. Это, очевидно, правда, но напоминает мне интересную шутку.
Как научиться плавать? Просто прыгни в реку. Это работает для каждого, кто выживет!

Я думаю, что в конечном итоге такой подход просто выводит людей из спортивного программирования, потому что они думают, что они недостаточно умны.
Я надеюсь, этот блог подскажет Вам что для людей ниже div1 ничего не делается с программированием, но всё – с математикой.
Поэтому чтобы учиться для Codeforces должны изучать не программирование, а математику.

Почему я не становлюсь лучше на Codeforces после чтения cp-алгоритмов?

Потому, что надо изучать математику, а не программирование.

Мой профиль

Every Technique and Algorithm I Used to Become Grandmaster
Noble Mushtak, Northeastern University (USA)

Я стал гроссмейстером сегодня и решил вспомнить, как это было.

Вот перечень алгоритмов, которые мне не понадобились

• Sparse tables, Fenwick trees, and segment trees
• String algos, like rolling hashes, Knuth-Morris-Pratt, suffix arrays, and Aho-Corasick
• Shortest path algos, like Dijkstra's algorithm, Bellman-Ford, and Floyd-Warshall
• Flow algos, like Edmonds-Karp, Dinic's, and push-relabel
• Convex hull trick
• Fast Fourier transform and number theoretic transform

А вот которые понадобились

CodeForces Round #362 (Div. 2): Rating went from 1500 to 1504 (back then, default rating was 1500 instead of 0)
• Problem A: Ad hoc reasoning and math
• Problem B: Basic string manipulation
Codeforces Round #363 (Div. 2): Rating went from 1504 to 1536 (+36)
• Problem A: Brute force
• Problem B: Brute force
• Problem C: Ad hoc reasoning and basic bitmasks (there is a dynamic programming solution, but that's not how I solved it)
Codeforces Round #553 (Div. 2): Rating went from 1540 to 1566 (+26)
• Problem A: Brute force
• Problem B: Brute force and bitwise operations
• Problem C: Ad hoc reasoning and math
Codeforces Round #570 (Div. 3): Rating went from 1566 to 1732 (+166)
• Problem A: Basic number theory
• Problem B: Ad hoc reasoning and math
• Problem C: Ad hoc reasoning and math
• Problem D: Greedy and priority queue
• Problem E: Ad hoc reasoning with strings (there is a BFS solution, but that's not how I solved it)
• Problem H: Dynamic programming (I used the count unique subsequences of a given length algorithm)
Educational CodeForces Round 68: Rating went from 1732 to 1766 (+44)
• Problem A: Ad hoc reasoning and math
• Problem B: Brute force and row/column sums
• Problem C: Ad hoc reasoning with strings and subsequences
• Problem D: Game theory
CodeForces Global Round 4: Rating went from 1776 to 1807 (+31)
• Problem A: Greedy
• Problem B: Dynamic programming
• Problem C: Binary exponentiation
• Problem D: Ad hoc reasoning with graphs
• Problem E: Deques
Educational Codeforces Round 74: Rating went from 1807 to 1920 (+113)
• Problem A: Ad hoc reasoning and math
• Problem B: Greedy and sorting
• Problem C: Greedy
• Problem D: Ad hoc reasoning and combinatorics
Codeforces Round #600 (Div. 2): Rating went from 1920 to 1877 (-43)
• Problem A: Ad hoc reasoning and math
• Problem C: Sorting, prefix sums, and dynamic programming
• Problem D: Depth-first search and connected components
Codeforces Round #601 (Div. 2): Rating went from 1877 to 2005 (+128)
• Problem A: Ad hoc reasoning and math
• Problem B: Ad hoc reasoning with graphs and sorting
• Problem C: Ad hoc reasoning with graphs and permutations
• Problem D: Ad hoc reasoning with grids
• Problem E1: Greedy
Codeforces Global Round 14: Rating went from 2005 to 1877 (-128)
• Problem A: Ad hoc reasoning with sorting
• Problem B: Ad hoc reasoning with number theory
• Problem C: Greedy and priority queue
Deltix Round, Spring 2021: Rating went from 1877 to 1975 (+98)
• Problem A: Ad hoc reasoning with simulations
• Problem B: Ad hoc reasoning and math
• Problem C: Stacks
CodeForces LATOKEN Round 1: Rating went from 1975 to 1974 (-1)
• Problem A: Ad hoc reasoning with grids
• Problem B: Ad hoc reasoning and math
• Problem C: Cycle decomposition and binary exponentiation
• Problem D: Ad hoc reasoning with trees
Codeforces Round #729 (Div. 2): Rating went from 1974 to 2132 (+158)
• Problem A: Ad hoc reasoning and math
• Problem B: Ad hoc reasoning with number theory
• Problem C: Ad hoc reasoning with number theory
• Problem D: Binary exponentiation and dynamic programming
• Problem E1: Dynamic programming and combinatorics (I used the count permutations with given number of inversions algorithm, the numbers of permutations with a given number of inversions are also known as Mahonian numbers)
Hello 2022: Rating went from 2132 to 2085 (-47)
• Problem A: Ad hoc reasoning with grids
• Problem B: Greedy
• Problem C: Cycle decomposition
Codeforces Round #765 (Div. 2): Rating went from 2085 to 2092 (+7)
• Problem A: Greedy and bitwise operations
• Problem B: Ad hoc reasoning and maps
• Problem C: Dynamic programming
Educational Codeforces Round 122: Rating went from 2092 to 2168 (+76)
• Problem A: Ad hoc reasoning with number theory
• Problem B: Greedy
• Problem C: Brute force
• Problem D: Dynamic programming
• Problem E: Kruskal's algorithm and binary search tree maps
Codeforces Round #808 (Div. 1): Rating went from 2168 to 2138 (-30)
• Problem A: Greedy
• Problem B: Ad hoc reasoning with simulations
Codeforces Global Round 23: Rating went from 2138 to 2239 (+101)
• Problem A: Ad hoc reasoning and math
• Problem B: Greedy with stacks
• Problem C: Ad hoc reasoning with permutations
• Problem D: Tree DP
• Problem E: Ad hoc reasoning, with inspiration from binary search
Codeforces Global Round 24: Rating went from 2239 to 2291 (+52)
• Problem A: Ad hoc reasoning and math
• Problem B: Ad hoc reasoning with number theory
• Problem C: Prefix sums and maps
• Problem D: Modular arithmetic, extended Euclidean algorithm, and combinatorics
• Problem E: Greedy, sorting, and binary search tree sets
Good Bye 2022: 2023 is NEAR: Rating went from 2291 to 2358 (+67)
• Problem A: Greedy and binary search tree sets
• Problem B: Ad hoc reasoning with permutations
• Problem C: Ad hoc reasoning with number theory (I did use Miller-Rabin, but only to generate the primes <100, which could have been hardcoded instead)
• Problem D: Disjoint set union, and I also used DFS trees for the intuition behind this solution
• Problem E: Tree DP and extended Euclidean algorithm
Hello 2023: Rating went from 2358 to 2331 (-27)
• Problem A: Ad hoc reasoning with simulations
• Problem B: Ad hoc reasoning and math
• Problem D: IntervalContainer and maps
• Problem E: Sorting and ad hoc reasoning with graphs and strongly connected components
TypeDB Forces 2023: Rating went from 2331 to 2416 (+85)
• Problem A: Ad hoc reasoning and math
• Problem B: Miller-Rabin, Pollard's rho algorithm, and number theory
• Problem C: Dynamic programming
• Problem D: Tarjan's SCC algorithm and DP over directed acylic graphs
• Problem E: Greedy and bitwise operations
• Problem F: Binary exponentiation, extended Euclidean algorithm, and cycle decomposition

Означает ли твой пост, что всё зависит от таланта и интеллекта?

Определённо, нет.
Я шёл к своему результату почти семь лет.
Я думаю, самое главное - практиковаться эффективно и учиться на своих ошибках.

Мой профиль

How to practice Competitive Programming [Um_nik version]
Алексей Данилюк, Украина, Харьков, легендарный гроссмейстер

Спортивное программирование о решении задач быстро.
Но по моему мнению РЕШАТЬ и БЫСТРО очень различные и почти независимые части и их нужно тренировать отдельно.

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

Ваш результат на контесте зависит от того, насколько быстро Вы сможете решить простые для себя задачи.
Поэтому собственно на контесте Вы учитесь решать задачи БЫСТРО.
А где Вы учитесь РЕШАТЬ задачи?
Это нужно делать в архиве.
Отсортируйте задачи по возрастанию сложности и решайте их (без ограничения по времени).
По мере развития навыков можно увеличивать сложность решаемых задач.
Я заметил многие новички начинают с CF-контестов, и я думаю это неправильно.
- на контесты стараются придумывать новые задачи с новыми идеями, а новичкам для начала полезно ознакомиться со старыми/базовыми идеями

Вопросы и ответы
Q: Сколько времени я должен думать над задачей, прежде чем посмотреть в описание решения? 30 минут достаточно?
A: Вы не должны читать описания решений. Идеальный вариант выбрать архив где их нет вообще, чтобы не было соблазна посмотреть решение.

Q: И что я должен делать, если я не могу придумать решение?
A: Прекрати работать над ней сейчас. Переключись на другую задачу, а к этой вернись позже. Мой обычный подход – открыть 10-15 задач, прочитать их внимательно, выбрать одну и постараться её решить,
Если не получается – переключаюсь на другую задачу.

Q: Ок но как я научусь новым алгоритмам, если не буду читать описания решений. Я же не могу придумать всё сам.
A: В большинстве случаев, нет необходимости в изучении новых алгоритмов. Просто ты недостаточно стараешься или не уделяешь внимание деталям. По-моему, большинство русских школьников, которые занимаются спортивным программированием, знают слишком много алгоритмов.

Q: Но есть задачи, которые требуют знания стандартных вещей.
A: Да. По мне лучше всего, чтобы ты мог у кого-то спросить – должен я что-то знать новое, чтобы решить эту задачу, и если да, чтобы этот кто-то сказал, что и дал нужную ссылку. А если нет - ты должен продолжить поиски решения сам.