Лучшая дорожная карта конкурентного программирования 🔥🔥🔥

Думай быстро, опережай конкурентов и узнавай что-то новое.

В этой строчке вся суть соревновательного программирования. Вам предоставляется удобная среда для размышлений и быстрого решения поставленных вопросов.

Кроме того, решения должны быть приемлемыми для работы в течение заданного ограничения времени в 1 секунду.

Сначала выучите язык программирования. Это может быть C ++ или Java. Но не забудьте изучить тонкости языка. Узнайте, как работают различные типы циклов и операторов if-else. Я бы порекомендовал следующий курс по удеми, чтобы выучить оба прекрасных языка.

Я лично взял их оба. Но теперь я понимаю, что знание многих языков не имеет никакого значения ни для программирования соревнований, ни для прохождения собеседований в FAANGM.

Следующий шаг и бесконечный шаг - освоить структуры данных и алгоритмы.

Это самая сложная и забавная задача. Иногда вы хлопаете своим ноутбуком, и вам никогда не захочется его видеть в своей жизни. Посмотрите, что происходит со всеми, кто называет себя программистами.

Вот несколько сайтов, которые помогут вам на протяжении всего вашего путешествия. Они очень полезны.

1 набор основных вещей

1. Проблемы с печатью выкройки
2. анализ временной сложности
3. линейный поиск и представление кругового массива
4. палиндром и другие числа (идеальный, Армстронг) для основных задач с числами
5. Простая проблема хеширования (подсчет частоты и прочее)
6. Задачи суммы префиксов (1D и 2D) {codeforces}
7. Техника раздвижного окна (2 конкурса из 5)

Математика и теория чисел

Основы теории чисел

1. Бинарный поиск обязателен (2/5 конкурсов)
2. НОД 2 чисел в логарифмическом времени (евклидов и расширенный евклидов алгоритм)
3. линейное диофантово уравнение
4. Проверка простого в sqrt (n) сложности
5. Сито Эратосфена (очень сложно выполнять запросы на простое число)
6. Сегментированное сито
7. Нахождение разложения числа на простые множители в log (n) на запрос
8. Функция Эйлера-Тотента
9. Маленькая теорема Ферма
10. Теорема Вильсона

(gfg статьи и хакерские исследования земли за 8,9,10)

Более жесткая версия теории чисел

1. Нахождение x ^ n в log (n)
2. Модульная арифметика
3. Модульное обратное число
4. Модульное возведение в степень
5. Китайская теорема об остатках
6. Факториальный модуль Mod
7. Нахождение nCr и nPr для запросов (постоянное время)
8. Принцип включения-исключения (задачи комбинаторики) {у hackerearth есть замечательная связка} {codeforces}

Некоторые базовые алгоритмы.

1. узнать об основных алгоритмах сортировки (пузырь, выбор, вставка)
2. решать конструктивные задачи, в которых много терминов.
3. решить проблемы, связанные с подходом с двумя указателями.
4. Битовая манипуляция (сдвиг влево, сдвиг вправо, xor, или, и, установить бит, MSB, LSB и т. Д.)
5. Набор мощности данного массива или строки с использованием BIT
6. Количество подмассивов с XOR равным нулю (не алгоритм, но обязательная проблема) (HackerEarth имеет очень хорошее руководство по манипуляции с битами, кодирование блоков для правильного видео на бит) {для проблем посетите hackerearth}
7. Проблемы, связанные с тегом жадного алгоритма
8. Алгоритм Кадане и связанные с ним проблемы
9. Задача упорядочивания заданий и выбора действий (после выполнения 8 и 9 перейдите к кодированию и решите проблемы с жадным тегом на них.)

Давайте делать это снова и снова.

Fime, чтобы узнать рекурсию

1. начните с основных задач, таких как нахождение факториала и все такое.
2. реализовать бинарный поиск
3. реализовать модульное возведение в степень с помощью рекурсии
4. решать проблемы рекурсии, такие как поиск подмножества с данным и другие, чтобы получить сильную хватку
5. Узнайте о сортировке слиянием и быстрой сортировке
6. решать проблемы, связанные с сортировкой слиянием
7. Решайте проблемы с возвратом, такие как судоку и N Queen, это поможет вам, когда вы захотите решить проблемы DP Path

(для рекурсии вы можете обратиться к leetcode или к практике gfg, где вы обнаружите проблемы с рекурсией и возвратом)

После рекурсии:

1. Встречайте в середине алгоритм и проблемы, связанные с ним. 2. Разделяй и властвуй над проблемами {настоятельно рекомендуется использовать кодовые силы только для этого}
2. Следующий больший элемент и следующий меньший элемент с использованием стека
3. проблемы, связанные со скобками.
4. самая большая прямоугольная область на гистограмме. (концепция используется во многих задачах)
5. Проблемы, связанные с кучей (приоритетной очередью) (хотя она попадает в категорию жадных по приоритетной очереди, это поможет вам изучить встроенную стандартную библиотеку шаблонов или библиотеку коллекций Java)

Продвинутые части и игра решающая

Строковые алгоритмы:

1. хеширование строк (изучить и решить проблему, понять, когда происходит коллизия) {cpalgorithms написал замечательную статью об этом) {Spoj или codeforces}
2. Алгоритм Рабина Карпа (на cpalgorithm.com есть замечательный блог)
3. Функция префикса
4. KMP Алгоритм
5. Z-функция
6. Алгоритм Манчерса (как только вы завершите приведенные выше алгоритмы, решите на них кучу проблем (25–30) с разных платформ).

Алгоритм дерева:

1. Представление дерева / графика
2. Обход DFS / BFS в графике / дереве
3. Основные параметры (диаметр дерева, высота дерева, уровень дерева)
4. Эйлер тур по дереву (учиться и решать задачи)
5. Поиск LCA с помощью Euler Tour (14:00) (эффективное решение использует деревья сегментов)
6. Поиск LCA с помощью двоичного лифтинга.
7. Расстояние между двумя узлами.
8. Проблемы поддерева. (SPOJ также настоятельно рекомендуется для проблем с деревьями и codeforces D и E)

Графики:

1. Связанные компоненты.
2. Топологическая сортировка.
3. Обнаружение цикла в графике
4. Двудольный график регистрации
5. SCC с использованием алгоритма Косараджу
6. Алгоритм Дейкстры
7. Источники для изучения алгоритмов Беллмана-Форда: блоги HackerEarth и cpalgorithm
   (25–30 задач по вышеуказанным темам, SPOJ и codeforces, также HackerEarth)

Потом:

1. Мосты в графах
2. Точка сочленения на графике
3. Минимальное связующее дерево с использованием алгоритма Краскала
4. Алгоритм Прима
5. 0/1 BFS (большой спаситель)
6. Изучите поиск мостов онлайн (cpalgorithms) Решите проблему

Динамическое программирование:

1. Пройдите образовательные соревнования AtCoder по динамическому программированию (всего 26).
2. Решать проблемы из SPOJ (настоятельно рекомендуется, поскольку он не использует никаких других алгоритмов)
3. Проблемы с практикой динамического программирования Google, codeforces, у меня будет замечательный блог с множеством проблем. После всего вышеперечисленного стандартного DP изучите:
4. Понять, как мы пишем повторение для Digit DP (блог codeforces) (цифровая динамическая программа) и решать проблемы
5. читать о DP с Bitmasks и решать проблемы (блог HackerEarth)
6. DP на деревьях (статьи gfg, видео Рахит джайн)
7. SOS DP (блог cpalgorithm) Решите как можно больше проблем
8. Непересекающийся набор (cpalgorithms)
9. Автономные запросы с использованием Disjoint Set (проблема с красочным массивом от spoj)
10. Алгоритм Крускала с использованием непересекающегося множества Решите кучу проблем, описанных выше
11. Разреженный стол (не тот чертенок)
12. Дерево Фенвика и двоичный подъем на дереве Фенвика (прочтите также о трюке с обновлением диапазона)
13. проблемы на дереве Фенвика
14. Возведение в степень матрицы (проблемы)
15. Техника Sqrt Decomposition (gfg, cpalgorithms или codeforces)
16. Операции обновления и запросов
17. Алгоритм Мо (решение мощного массива из codeforces) (блог codeforces)
18. Алгоритм Мо на деревьях
19. Дерево сегментов (обязательно) (запросы диапазона и обновления точек)
20. Ленивое распространение на деревьях сегментов

Затем несколько необязательных и редких:

1. Теория Спрага-Гранди
2. Потоки и связанные с ними проблемы
3. Разложение тяжелого легкого
4. Алгоритм выпуклой оболочки
5. БПФ / NTT

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

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

Даже я страдал от того, что было много тем, о которых я не знал всех, из-за которых я не мог решать вопросы, я продолжал и продолжал целый день, не решая ни одного вопроса.

Идея здесь состоит в том, чтобы дать вопросу свежие 15–20 минут, 30–40 минут в зависимости от уровня сложности вопроса. Если вы все еще не можете хорошо отвечать на вопросы, посмотрите, как в редакционной статье этого конкретного вопроса есть небольшой намек, а затем используйте свой мозг. и полный вопрос должен быть решен в течение 1 часа.

Делая это инвестируя более 6 часов в день в течение 4 месяцев, вы решите около 720+ вопросов, которых более чем достаточно, чтобы достичь кандидата в мастера в Codeforces или взломать любую компанию FAANGM.

Пожалуйста, следуйте за мной, поделитесь с друзьями.

🤫Как я использую свое понятие, чтобы повысить уровень подготовки к суточным.