Competitive Programming

Я просто хочу пройти алгоритмический собес 🥺

Тут будут какие-то заметки, когда я столкнусь с чем-то сложным/интересным/новым для себя.

Кроме этого сформирую базу ссылок того что читал/смотрел/изучал.

На текущий момент основная платформа LeetCode.

Алгоритмы

• KMP — поиск подстроки в строке за O(m + n). Встретился в 28. Брутфорс ушёл в TL. Алгос списал с псевдокода на вики: Knuth–Morris–Pratt algorithm.
• Prefix sum — быстрый ответ на множество вопросов "Какая сумма на подмассиве от L до R?" (pref[0] = a[0]; pref[i] = pref[i - 1] + a[i]. Q: pref[r] - pref[l - 1] или pref[r] если l == 0). Точ в точ задача 303. Интересное и легкое усложнение задачи в 724.
• Kadane's algorithm — подмассив с наибольшей суммой (tSum += a[i]; tSum = max(tSum, a[i]); res = max(res, tSum)).

Заметки

• В 1408 допустил ошибку при оценке временной сложности. Там не O(N^2*L), а O(N*L), где L сумма длин всех строк. Потому что несмотря на вложенный цикл мы выполняем поиск в строке за длину строку, а циклы порождают сравнение строки с каждой другой. Где каждую другую можно заменить на сумму длин всех строк (L). Поэтому оценка количество строк умноженное на сумму длин (N*L). Что меньше моей изначальной оценки, так как в условии задачи максимальная длинна строк 30, а количество слов 100.
• Долго мучался с 11 (бассейн с двумя бортиками). Брутфорс конечно не зашёл, прочитал подсказки, частично дорешал, не справившись отловить баг пошёл в обсуждения к задаче. Посмотря на чужой код понял, что нафантазировал ненужные дополнительные условия (diff). В итоге списал с чужого кода, но свою ошибку понял (кажется). Upd. 121 задача мне сильно напомнила эту.
• В 1337 первый раз использовал кучу. В условии задачи условия повторяют сравнение пары интов. Если первые элементы (сила строки AKA кол-во единиц в ней) равны, то сравниваем вторые (индекс в массиве по задаче). Так как по условию нам нужно вывести слабейших, то используем кучу для поиска минимума (std::priority_queue<T, vector<T>, greater<T>>).
• В 231 сраные граничные случаи с -2^31 и 2^31-1.

Ссылки на почитать

Сайты с темами

• brestprog by @kodek16
• algorithm gitbook by @lzl124631x
• USACO Guide

Конкретные темы

• Maximum subarray problem (Kadane's algorithm). LeetCode 53
• Sliding Window Technique
• Префиксные суммы. XOR. Задачи на запросы
• Полное бинарное дерево. Куча. Очередь с приоритетом
• Hamming weight. LeetCode 191
• Custom impl of __builtin_popcount
• Hamming distance
• How to count leading zeros in integer (__builtin_clz and pure impls)

Ссылки на посмотреть

• Четыре задачи на два указателя
• Алгоритм Кнута-Морриса-Пратта
• Динамическое программирование это просто
• Задача о рюкзаке. Динамическое программирование
• Прямая и обратная польская нотация
• Популярная в собеседованиях гугл задача. Разбор и решение (Guess the word 843 на LeetCode)
• Хитрая задача на Стек
• Поиск Знаменитости. Метод двух указателей
• Динамическое Программирование: Количество Уникальных Путей
• What is Bitmasking
• Bitwise Operations tutorial #1 | XOR, Shift, Subsets
• Плейлист АиСД year2020 s1
• Что такое sliding window: Solve subarray problems FASTER (using Sliding Windows)
• Что такое dynamic programming: Mastering Dynamic Programming - How to solve any interview problem (Part 1)
• Linked List Cycle - Floyd's Tortoise and Hare
• Найти позицию начала цикла (len(head -> cycle_start) == len(equal_pointers -> cycle_start)) Floyd's Cycle Detection
• How Dijkstra's Algorithm Works