Техминимум

15 лет назад, # ^ |

Ты не знаешь алгоритм Быковой-Афанасьева-Делюкина.

Все алгоритмы знать невозможно.

Перечисли подмножество множества всех алгоритмов, которые ты считаешь необходимыми?

→ Ответить

Fefer_Ivan

15 лет назад, # |

Это, конечно, шутка. Но близка к правде.

Алгоритмов много. Сайт e-maxx в этом плане хорош. Там мало совсем неприменимых алгоритмов.

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

→ Ответить

15 лет назад, # ^ |

← Rev. 2 →

Я зачастую раньше писал кривой алгоритм Дейкстры, а много дней назад написал Форда-Беллмана, а потом уже узнал про него (специально для всезнающего forest :).

→ Ответить

forest

14 лет назад, # ^ |

Дейкстра мужского рода

→ Ответить

15 лет назад, # |

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

Это будет особенно полезно для новичков.

→ Ответить

http://mirror.codeforces.com/blog/entry/151

15 лет назад, # |

вот человек выкладывал классификатор, из чего видно что большинство задач на ДП.

→ Ответить

15 лет назад, # ^ |

ТО большинство задач можно решить зная только одно ДП)

→ Ответить

15 лет назад, # ^ |

Большое множество не есть наибольшее количество. =)

→ Ответить

15 лет назад, # ^ |

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

ЗЫ я бы написал, но не обладаю таким опытом.

→ Ответить

15 лет назад, # |

Several years ago I saw very competent list. It was PDF in Russian - list with many items. But I don't remember where I saw it :(

→ Ответить

15 лет назад, # ^ |

So, why we can't create such list?

→ Ответить

15 лет назад, # ^ |

Good idea. Begin the work in your topic and add items in it from the comments. It will be really interesting. You can try from e-maxx, organize the list as multilevel by topics.

→ Ответить

Harta

14 лет назад, # ^ |

can you put a link to "Tutorial", then you put some topics, every members can edit the text in those topics :). I think this way is more effective and efficient, users also don't have too much burden :)

→ Ответить

yasith

14 лет назад, # ^ |

Something that I had lying around. Might need a lot of editing and changes. But would be a good starting point to create such a list. This one was for the IOI btw.

Introduction

Intro to the IOI
Ad hoc problems
The order of time of an algorithm
Basic sorting and searching

Linear search
Bubble sort
Selection sort
Insertion sort
Address sort
Why bubble sort is less efficient that the selection/insertion sort

Recursion

Generating permutations and combinations
Divide and conquer

Application of divide and conquer to:

Binary search
Mergesort
Quicksort
Traveling salesman problem

Why (simple) divide and conquer can sometimes yield inefficient solutions

Techniques for improving the efficiency of a recursive search

Iterative deepening
Branch and bound

Graphs

Explicit graphs
Implicit graphs
DFS

Finding a path thorough a graph using DFS
Finding all sub-graphs of a graph using DFS
Optimizing a DFS (for weighted graphs)

Finding a path through a graph using BFS
Finding the shortest path through an unweighted graph

Search space and Implicit graphs

The concept of search space
How to represent search space
Why it is usually takes too much space to represent implicit graphs using conventional representations (ex: adj. matrices)

Dynamic programming

The reasoning behind DP

Breaking down a recursive problem
Graph of solutions and sub-solutions
Exponential number of paths but linear number of nodes
Independence of sub-solutions
Storage to avoid recomputation

Recognition of search space

The fact that the search space is effectively an implicit graph
Mechanical method to recognize the search space

Evaluation of search space

Visualization of traversal of search space
Recursive evaluation (e.g. a memory function)
Iterative evaluation (e.g. true dynamic programming

Finding the shortest paths

Dijkstra's algorithm

Theory behind Dijkstra's algorithm
O(N 2) implementation
Adaptability of Dijkstra's algorithm

Floyd's algorithm

Theory behind Floyd's algorithm
O(N 3) implementation
Adaptability of Floyd's algorithm
Using Floyd's algorithm to find a minimum cost cycle of minimum length

Floyd vs. Dijkstra

Pros and cons of each algorithm

Complete paths

Eulerian paths

Identifying an Eulerian graph
Finding a Eulerian path

Recursive method
Iterative method

Network flow

Visualization
FF maxflow method

Explanation of the FF method
Edmonds-Karp implementation of the FF method

Adaptability of the FF method

Finding the maximal matching using the FF method
Finding the minimal cutset using the FF method
Maximal disjoint paths using the FF method

Disconnecting graphs

Disconnecting via edges

Finding bridges
Eliminating all bridges in a graph by adding as few edges as possible (can be done in Polynomial time)

Disconnecting via nodes

Finding articulation points
Eliminating all articulation points in a graph by adding as few edges as possible (is NP-Complete)

Biconnectivity of graphs

Finding the biconnected components of graphs
How the collapsible set structure is used to yield an amortized time complexity of O(N lg N)

Mincut type disconnection

Minimum cost spanning trees

MCST theorem
Prim's algorithm

How Prim's algorithm makes use of the MCST theorem
Prim's innovative data structure to keep track of the nodes to be added to the MCST
O(N 2) implementation of Prim's algorithm

Kruskal's algorithm

How Kruskal's algorithm makes use of the MCST theorem
The collapsible set structure used in Kruskal's algorithm
O(E lg E) implementation of Kruskal's algorithm

Adaptability of Kruskal's and Prim's algorithms

The fact that it is more or less impossible to introduce new constraints to these algorithms without breaking them.

Kruskal vs. Prim

Pros and cons of each algorithm

→ Ответить

brainail

15 лет назад, # |

На IOI 2006 было выдвинуто предложение ОЧЕРТИТЬ список тем, которые должен знать олимпиадник - это и есть IOI Syllabus.

http://www.win.tue.nl/~wstomv/publications/ioi-syllabus-proposal.pdf

Вообще разработчики IOI Syllabus, по-моему, подошли к этому весьма оригинально.

Две ведущие ассоциации компьютерных профессионалов (ACM и IEEE) совместно выпустили аналогичный документ для ВЫПУСКНИКОВ ВУЗОВ. Он называется Computing Cirricula. Там по 5 специальностям. Одна из них - Software Engineering наиболее близка к олимпиадному программированию.

Так вот они просто ВЫЧЕРКНУЛИ кое-что из того, что должны знать студенты - а остальное школьники должны знать

Темы: 623
Сообщений: 5514

А это Российский теорминимум
(использовался при приеме в Летнюю Компьютерную Школу - 2007 )

1. Циклы
2. Массивы
3. Двухмерные массивы
4. Процедуры и функции
5. Работа с текстовыми файлами: ввод из файла, вывод в файл
6. Рекурсия
7. Алгоритм Евклида вычисления НОД двух чисел
8. Проверка: является ли данное число простым методом перебора делителей
9. Сортировка массива пузырьком
10. Сортировка подсчетом
11. Сортировка массива: быстрая сортировка
12. Сортировка массива: сортировка с помощью кучи
13. Структуры данных: списки, хранение списка в массиве
14. Очереди: хранение, операции добавления и извлечения элементов
15. Стеки: хранение, операции добавления и извлечения элементов
16. Деки
17. Обход в ширину, поиск кратчайших расстояний в невзвешенном графе
18. Обход в глубину
19. Выделение компонент связности
20. Выделение мостов, точек сочленения, компонент реберной и вершинной двусвязности
21. Топологическая сортировка
22. Топологическая сортировка за O(N)
23. Выделение компонент сильной связности, конденсация графа
24. Алгоритм Дейкстры
25. Алгоритм Штайна
26. Алгоритм Флойда
27. Алгоритм Форда-Беллмана
28. Алгоритм Прима
29. Алгоритм Краскала
30. Построение эйлерова цикла в графе
31. Длинное сложение, вычитание
32. Длинное умножение
33. Длинное деление и извлечение корня
34. Алгоритм Карацубы
35. Вычисление чисел Cnk.
36. Перебор всех подмножеств данного множества
37. Быстрый перебор подмножеств заданной мощности данного множества
38. Быстрая генерация i-ой в лексикографическом порядке перестановки из N элементов
39. Быстрая генерация i-ой в лексикографическом порядке правильной скобочной последовательности из N пар скобок
40. Скалярное, векторное, смешанное произведения векторов
41. Нахождение площади многоугольника
42. Расстояние от точки до прямой
43. Нахождение точки пересечения двух прямых
44. Проверка пересечения отрезков
45. Нахождение выпуклой оболочки
46. Динамическое программирование: задача о рюкзаке
47. Динамическое программирование: наибольшая возрастающая подпоследовательность
48. Динамическое программирование: общие принципы
49. Метод рекурсивного спуска
50. Польская инверсная запись, алгоритм построение по выражению
51. Конечные автоматы, регулярные выражения
52. Контекстно-свободные грамматики, проверка принадлежности слова КС-языку
53. Коды Хаффмана
54. Алгоритм Кнута-Морриса-Пратта
55. Бор. Алгоритм Ахо-Корасик
56. Ab-отсечение, перебор с возвратом
57. Функция Гранди
58. Бинарные деревья, хранение в массиве
59. AVL-деревья
60. RB-деревья
61. Декартовы деревья
62. Нахождение наименьшего общего предка в дереве
63. Алгоритм Джонсона
64. Построение гамильтонова цикла в графе
65. Построение максимального паросочетания в двудольном невзвешенном графе
66. Венгерский алгоритм решения задачи о назначениях
67. Поиск максимального потока
68. Матрицы: определитель, обратная матрица, матричное произведение
69. Метод Гаусса решения систем уравнений
70. Дискретное преобразование Фурье
71. Дерево интервалов и его реализация
72. Динамическое дерево Тарьяна-Слейтора
73. Хэш-таблицы
74. Системы непересекающихся множеств
75. Обобщенный алгоритм Евклида, решение диофантовых уравнений
76. Метод шифрования RSA
77. Суффиксное дерево. Алгоритм Укконена.
78. Суффиксный массив. Построение без суффиксного дерева
79. Преобразование Бэрроуза-Уилера

Курс лекций по олимпиадному
программированию Михаила Густокашина
(Тоже некий теорминимум)

http://g6prog.narod.ru/lessons.html

→ Ответить

15 лет назад, # ^ |

25. Алгоритм Штайна
49. Метод рекурсивного спуска
50. Польская инверсная запись, алгоритм построение по выражению
51. Конечные автоматы, регулярные выражения
52. Контекстно-свободные грамматики, проверка принадлежности слова КС-языку
55. Бор. Алгоритм Ахо-Корасик
56. Ab-отсечение, перебор с возвратом
59. AVL-деревья
60. RB-деревья
61. Декартовы деревья
63. Алгоритм Джонсона
66. Венгерский алгоритм решения задачи о назначениях
67. Поиск максимального потока
72. Динамическое дерево Тарьяна-Слейтора
75. Обобщенный алгоритм Евклида, решение диофантовых уравнений
76. Метод шифрования RSA
77. Суффиксное дерево. Алгоритм Укконена.
79. Преобразование Бэрроуза-Уилера

Вот эти вещи я вообще не знаю
Требовать знание фурье кажется странным, равно как RSA, и уж точно Укконена. Кто-нибудь когда-нибудь на контесте писал Укконена?

→ Ответить

valergrad

15 лет назад, # ^ |

Ну, 63 наверное знаете, просто не в курсе, что так называется.
67 и 75 - трудно поверить что вы ни разу не кодили задачу на макс поток и не решали уравнение вида ax+by=c в целых числах.
Также 50 тоже как-то любой должен знать.
56 - это перебор с отсечениями, думаю тоже не раз кодили, хоть и не называя его гордым словом альфа-бета.
В общем, трудно поверить что можно стать красным на топкодере не зная всего из этого списка :)

→ Ответить

15 лет назад, # ^ |

Макс.поток - это опечатка, я хотел оставить поиск обратной матрицы. Я с тех пор еще как экзамен по линейке сдавал, не мог запомнить как она находится.
Про расширенного эвклида - все что я о нем знаю это то, что он копипастится с e-maxx :о) Наизусть я его не знаю, хотя и выводил как-то очень давно.
Остальные из списка я могу теоретически знать но не знать название. Скажем метод рекурсивоного спуска - я могу предположить, что так называется когда динамику пишут не циклом, а рекурсией с запоминанием. Что касается Ахо-Карасика, то на финале в 2008 я решил задачу какую-то на строки, которая оказалась нашей седьмой и принесла нам золото, и когда я рассказал свое решение какой-то команде, мне сказали, что это Бор и Ахо-Карасик. Так что видимо это такой алгоритм, который очевидным кажется когда рука натискана. Вообще строки можно чаще всего сдавать хешами.

Кстати, в списке нет 2-SAT. Нужный алгоритм на мой взгляд. Хотя на сборах в Ижевске Пономарев из перьми его вывел за контест, но потратил на это время. Лучше все же знать :о

Чтобы стать красным на топкодере надо знать очень мало. Там чаще задачи на то, чтобы извилинами пошевелить. Задачи на поток либо 1000 либо 600 - это уже о чем-то говорит :о) И за всю историю я только один раз видел задачу на фурье. Думаю, координаторы контестов там просят авторов не давать задачи на что-то специализированное. Иван Метельский вроде как там один из координаторов, он лучше знает. Правда не думаю, что он читает тут прямо все ветки, и заметит вопрос :о)

→ Ответить

ivan.metelsky

15 лет назад, # ^ |

На ТопКодере для успешного выступления изучением множества специализированных алгоритмов заниматься (почти) бесполезно. Просто наиболее реальный результат использования задачи, которая очень сильно базируется на каком-то сложном алгоритме, который мало кто знает -- либо никто не решит, либо решат те, кто погуглят и возьмут его откуда-нибудь из интернета. Оба случая малоинтересны.

Задача на Фурье действительно один раз была, но она решалась также и алгоритмом Карацубы, причем это решение было авторским. Хотя в результате так ее решил вроде бы только Petr, а остальные достали Фурье из загашников (ну и еще Psyho вроде написал лобовое решение с ассемблерными вставками). Т.е. получилась полная ерунда, ну и фидбек по задаче был соответствующий - в стиле "одна из худших 1000-задач за все время на ТС". Так что это скорее такое исключение, которое подтверждает правило.

Иногда (но тоже редко) бывает, что задача использует какой-нибудь (относительно) малоизвестный факт. Например, в январе была задача, существенно основанная на том, что любой двудольный граф имеет реберную раскраску в кол-во цветов, равное его максимальной степени. Так что в принципе изучение сложных алгоритмов может помочь, если их детально изучать, с обоснованием, плюс если знать много разных сопутствующих фактов. Но это тоже, мне кажется, довольно редкая вещь.

→ Ответить

removed1

15 лет назад, # ^ |

БПФ должно быть в наборе библиотек, доступных на контесте.

→ Ответить

e-maxx

15 лет назад, # ^ |

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

→ Ответить

winger

14 лет назад, # ^ |

У меня помнится тоже было решение с Карацубой

→ Ответить

maksay

15 лет назад, # ^ |

Бытует мнение ( хотя я и не знаю конкретных примеров, но кажется верным), что чтобы стать на топкодере красным, достаточно быстро решать 250 в каждом из срмов. А какие конкретно алгоритмы есть в 250? Кроме Эвклида ничего не припомню, всякие там 250 финалов ТСО не в счёт:)

→ Ответить

15 лет назад, # ^ |

Бывала и динамика по рваному краю, думаю, что были и другие спец. темы

→ Ответить

valergrad

15 лет назад, # ^ |

Не, по-моему недостаточно. Надо еще иногда решать и 500.
А вот если все время решать 250 и 500 - можно стать таргетом.

→ Ответить

maksay

15 лет назад, # ^ |

Наверное. Но я, вообще, хотел поставить ударение на том, что ad hoc - ов, задач без чётких алгоритмов, гораздо больше(на ТС, да и не только). Да и кроме задач на общую "сёку" и алгоритмических, есть еще 3 класс, хеширование, динамика, дерево отрезков - описывают только общую идею, решить конкретную задачу помогает практика. Иначе говоря, лучше решить на контесте некую общую задачу, которую решило еще 10 человек, чем быть единственным, написавшим триангуляцию Делоне или другой, не менее ужастный алгоритм:) ИМХО.

→ Ответить

maksay

15 лет назад, # ^ |

P.S. Не хочу чтобы меня поняли превратно) Лучше, конечно, решить обе, но если времени на обе не хватает - то..

→ Ответить

ivan.metelsky

15 лет назад, # ^ |

Неужели правда была динамика по рваному краю в 250? Я не встречал, но вообще для 250 это было бы слишком сложно (если брать уровень сейчас, а раньше вроде бы было легче).

→ Ответить

dened

15 лет назад, # ^ |

Впервые вижу термин "динамика по рваному краю". Это, случайно, не то же, что и динамика по профилю?

→ Ответить

brainail

15 лет назад, # ^ |

Это можно сказать тоже самое, только профиль используется не на полную, а он рваный.. это ускоряет время и память ... =0 но такие задачи не такие частые ... =0

→ Ответить

Alex_KPR

15 лет назад, # ^ |

динамика по изломанному профилю

→ Ответить

14 лет назад, # ^ |

сорри за то что поднимаю старую тему, кто нибудь знает номер SRM'а этой *задачи?

*ДП по рваному краю на 250

→ Ответить

caustique

14 лет назад, # ^ |

Как Вам удалось успешно выступать в ACM ICPC без знания решения задачи про диофантовы уравнения?:)

Я читал блог и выяснил, что Вы работаете в Microsoft. А какой теорминимум нужен для того, чтобы попасть на такую работу? Как Вы нашли такую работу и что полезного Вы вынесли из университета? (я имею ввиду, какие курсы сейчас Вам более всего помогают в работе)

→ Ответить

caustique

14 лет назад, # ^ |

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

→ Ответить

14 лет назад, # ^ |

На интервью в майкрософт дают очень базовые задачки. Перельмана надо почитать, чтобы готовиться :о)
Проблема не пройти интервью, проблема попасть на интервью :о) Для этого очень хорошо помогает резюме вида

Я бла бла бла
Закончил бла в короде бла
Achievements:
Золотая медаль чемпионата мира ACM ICPC 2008
Еще парочка бла бла

Ну и там автоматически попадаешь на интервью :о)
Такая же система работает с Facebook и Google :о) Но Microsoft - это кул, потому что штат Washington хоть и дождливый зимой, но невероятно красивый (see my blog). И Ванкувер рядом :о)
А с точки зрения работы как таковой мне кажется везде одно и тоже.

→ Ответить

Edvard

14 лет назад, # ^ |

На одном из этапов открытого кубка надо было найти наименьший циклический сдвиг. У нас в команде никто не знал алгоритм Дюваля и мы написали Укконена и он прошёл.

→ Ответить

14 лет назад, # ^ |

Наверное написать за O(n log n) с помощью полиномиальных хешей вам показалось несказанно сложно по сравнению с Уконеном? :о)

→ Ответить

KirillB

14 лет назад, # ^ |

хмм, а разве можно найти наименьший циклический сдвиг с помощью полиномиальных хешей

→ Ответить

AlexFetisov

14 лет назад, # ^ |

Конечно!) циклом идешь по строке, храня текущий best, и бин поиском подбираешь общий префикс. Смотришь следующую букву, если она у cur < best, то best = cur

→ Ответить

KirillB

14 лет назад, # ^ |

спасибо, не знал)

→ Ответить

Edvard

14 лет назад, # ^ |

Там были такие ограничения, что решение за O(n * log n) наверняка не прошло бы. И что такое полиномиальные хеши? В чём отличие от обычных хешей?

→ Ответить

14 лет назад, # ^ |

O(NlogN) наверняка прошло бы, иначе бы решения на Java не успевали бы считывать ввод :D

Полиномиальный хэш от строки S = s_1s₂...s_n есть $\text{[math]}$ , где p и P - какие-то числа, обычно простые, причем p - маленькое большее размера алфавита, P - большое. Удобства - если посчитать такие хэши для всех префиксов S (это можно сделать за O(N)), то потом для каждой подстроки можно вычислить хэш за O(1) (как - додумаетесь сами:)).

→ Ответить

14 лет назад, # ^ |

O(NlogN) наверняка прошло бы, иначе бы решения на Java не успевали бы считывать ввод :D
Полиномиальный хэш от строки S=s_1s_2 ... s_n есть (\sum_{i=1}^{n}s_{i}p^{i}) mod P, где p и P - какие-то числа, обычно простые, причем p - маленькое большее размера алфавита, P - большое. Удобства - если посчитать такие хэши для всех префиксов S (это можно сделать за O(N)), то потом для каждой подстроки можно вычислить хэш за O(1) (как - додумаетесь сами:)).

→ Ответить

Egor	14 лет назад, # ^ \| 0 Ну вот у меня кастомный ридер для Java работает быстрее scanf ;) → Ответить

14 лет назад, # ^ |

Вообще в идеале mod P не должно быть
В идеале считаешь в 32-ух/64-ех битных числах, доверяя просто их переполнению. Потому что использование модуля (которые видимо меньше чем maxInt / p) повышает заметно шансы на коллизию
Я не помню тока что в ява происходит при переполнении - не выбрасывает ли она исключения.

→ Ответить

14 лет назад, # ^ |

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

Насчет явы не наю - я там даже быстрее чем scanf считывать не умею...

→ Ответить

Egor	14 лет назад, # ^ \| 0 нету в Java эксепшнов на переполнение. Не паскаль чай → Ответить

it4.kp

14 лет назад, # ^ |

В си шарпе они есть, хотя он тоже "не паскаль" :)

→ Ответить

14 лет назад, # ^ |

Ну в C# они есть (их можно обойти обернув в unchecked нужный кусок кода). Хотя, как известно, за C# и Delphi стоит один и тот же человек :о)

→ Ответить

14 лет назад, # ^ |

А существует ли алгоритм Штайна :) ?

→ Ответить

Connector

14 лет назад, # ^ |

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

В самой статье говорится, что второе название этого алгоритма "Stein's algorithm" Вроде совпадает.

→ Ответить

skaramouche

14 лет назад, # ^ |

Меня нервирует алгоритм Карацубы. Из какой это параллели?

→ Ответить

forest

14 лет назад, # ^ |

У меня для вас плохие новости...

→ Ответить

dened

15 лет назад, # |

На сайте http://neerc.ifmo.ru/school/ в архиве учебно-тренировочных сборов за 2008 г. имеется файлик "Программа международных олимпиад по информатике вер 04072007.doc" ("Примерная программа по информатике для подготовки сборной команды России к международной олимпиаде"), который тоже представляет из себя некий теорминимум, причем разбитый по разделам, а сложные темы помечены одинарными и двойными звездочками. Олимпиаднику должно быть полезно.

→ Ответить

15 лет назад, # ^ |

Ух, я посмотрел. Там много. :) :) Много-много.

→ Ответить

14 лет назад, # |

Список тем, входивших в team notebook моей команды:

1 Длинная арифметика

1.1 Длинное умножение

1.2 Деление длинного числа на короткое

2 Графы

2.1 Алгоритм нахождения мостов, точек сочленения, компонент вершинной двусвязности

2.2 Алгоритм нахождения эйлерова цикла

2.3 Максимальный поток за N^3

2.4 Алгоритм для игр на циклических графах

2.5 Наименьший общий предок (LCA)

2.6 Паросочетания и смежные задачи

3 Геометрия

3.1 Пересечение прямой и окружности

3.2 Пересечение двух окружностей

3.3 Касательные к двум окружностям

3.4 Поворот точки на угол

3.5 Расстояние от точки до прямой в параметрическом виде

3.6 Расстояние между двумя прямыми в параметрическом виде

3.7 Плоскость по трем точкам

3.8 Пересечение плоскости и прямой

3.9 Проверка отрезков на пересечение

3.10 Площадь и объем шарового сегмента

3.11 Площадь и объем шарового сектора

3.12 Обход Грэхема

3.13 Вертикальная декомпозиция

3.14 Выделение граней плоского графа

3.15 Построение касательных лучей к многоугольнику

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

4.1 Префикс-функция

4.2 Z-функция

4.3 Суффиксное дерево за O(N^2)

4.4 Алгоритм Ахо-Корасик

4.5 Суффиксный массив

4.6 Алгоритм Дюваля

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

5.1 Поиск наибольшей возрастающей подпоследовательности

5.2 Числа Каталана

5.3 Количество разбиений на слагаемые

5.4 Количество сочетаний

6 Модулярная арифметика

6.1 Расширенный алгоритм Евклида

6.2 Решение уравнения ax=b (mod n)

6.3 Вероятностный тест Миллера-Рабина

6.4 Китайская теорема об остатках

7 Быстрое преобразование Фурье

8 Алгоритм Гаусса

9 Формулы интегрирования

10 Бор

11 Дерево Фенвика

12 Обратная польская нотация

13 Дерево отрезков

13.1 Рекурсивное дерево отрезков, update на отрезке, RMQ

13.2 Нерекурсивное дерево отрезков

14 Декартово дерево

14.1 Декартово дерево с неявным ключом

14.2 Декартово дерево с явным ключом

15 Разное

15.1 Лемма Бернсайда

15.2 Задача Джонсона для N=2

15.3 2-CNF-SAT

15.4 Интерполяционный многочлен (в форме Лагранжа и Ньютона).

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

Также в нем нет ничего ненужного. Все эти алгоритмы нам понадобились на ACM ICPC, сборах в Петрозаводске или Открытом Кубке.

→ Ответить

14 лет назад, # ^ |

Так, то, что все алгоритмы здесь нужны, это понятно. А есть нужные алгоритмы (кроме дефолтных), которых здесь нет?

Судя по полуфиналу этого года в геометрию ещё можно добавить центр масс пространственного тела. :o)

→ Ответить

14 лет назад, # ^ |

А вообще список очень классный. Спасибо!

→ Ответить

it4.kp

14 лет назад, # ^ |

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

→ Ответить

14 лет назад, # ^ |

Можно нубу чуть подробнее пояснить?

→ Ответить

14 лет назад, # ^ |

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

Например, что касается центра масс пространственного тела, то я лично вывела эту формулу на контесте. После того, как не заработало решение "найти среднее арифметическое координат вершин". :)

Кое-что важное, что не вошло в список: потоковые алгоритмы, функция Гранди для игр.

→ Ответить

14 лет назад, # ^ |

А вот мы что-то не догадались вывести и так и остались с тремя задачами при правильном решении с неверной формулой.

В любом случае спасибо большое за адекватный список.

→ Ответить

Jokser

14 лет назад, # ^ |

Что-то не верится мне, что вы не сможете написать поиск возрастающей подпоследовательности без бумажки :)

→ Ответить

14 лет назад, # ^ |

Имеется в виду алгоритм за NlogN (без дерева отрезков). Его я не могу быстро и правильно написать без бумажки. Проверено на горьком опыте:(

→ Ответить

KADR	14 лет назад, # ^ \| 0 Имеется в виду замена дерева отрезков каким-то другим деревом или совсем другой алгоритм? → Ответить

KirillB

14 лет назад, # ^ |

дак ведь там же просто бинарный поиск зачем вообще деревья

→ Ответить

slalex

14 лет назад, # |

Хотел поинтересоваться у тех, кто участвовал в ACM ICPC....

Слышал, что на соревновании можно пользоваться бумажными материалами, действительно ли это так? 8)

→ Ответить

14 лет назад, # ^ |

По крайней мере до 2008 года команда могла пронести с собой тонну макулатуры с чем угодно на финале
На полуфинале ничгео нельзя брать с собой.

В 2010 я не видел печатных материалов ни у кого на столе на финале, есть подозрение, что убрали это дело.
В любом случае, мы на финале в приготовленную папку заглянули один раз - ручку взять :о)
Задачи, насколько я помню все финалы которые прорешивал, не требуют каких-то экстраординарных знаний обычно.

→ Ответить

MBabin

14 лет назад, # ^ |

Там можно было пользоваться распечтками (notebooks вроде назывались), которые заверялись при регистрации. Единственное, что могло пригодится это геома (но все равно не спасло)

→ Ответить

14 лет назад, # ^ |

Раньше каждая команда могла принести с собой на финал team notebook. Это папка с эмблемой университета, содержащая раздаточные материалы (расписание, задача пробного тура, указания к решению задачи пробного тура и прочая макулатура), канцтовары, чистая бумага и reference document, содержащий не более 25 страниц с текстом, читаемым для человека с нормальным зрением. В reference document как раз и можно включить нужные алгоритмы, формулы и т.п.

В 2010 году team notebooks отменили, но reference document принести было можно. Мы (Saratov SU #1) его использовали.

→ Ответить