Блог пользователя daftcoder

Автор daftcoder, 14 лет назад, По-русски

Тема стара как мир. Как мир спортивного программирования.

Какие алгоритмы надо знать человеку (команде), чтобы иметь возможность решить наибольшее количество задач?

Хочу услышать Ваши мнения. 

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Все.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
вот человек выкладывал классификатор, из чего видно что большинство задач на ДП.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ТО большинство задач можно решить зная только одно ДП)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Большое множество не есть наибольшее количество. =)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        тогда надо провести частотный анализ использования алгоритмов в задачах, и выявить самые используемые.

        ЗЫ я бы написал, но не обладаю таким опытом.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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 :(
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    So, why we can't create such list?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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 :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      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)
      • BFS
        • 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
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На 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

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

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

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну, 63 наверное знаете, просто не в курсе, что так называется.
      67 и 75 - трудно поверить что вы ни разу не кодили задачу на макс поток и не решали уравнение вида ax+by=c в целых числах.
      Также 50 тоже как-то любой должен знать.
      56 - это перебор с отсечениями, думаю тоже не раз кодили, хоть и не называя его гордым словом альфа-бета.
      В общем, трудно поверить что можно стать красным на топкодере не зная всего из этого списка :)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Макс.поток - это опечатка, я хотел оставить поиск обратной матрицы. Я с тех пор еще как экзамен по линейке сдавал, не мог запомнить как она находится.
        Про расширенного эвклида - все что я о нем знаю это то, что он копипастится с e-maxx :о) Наизусть я его не знаю, хотя и выводил как-то очень давно.
        Остальные из списка я могу теоретически знать но не знать название. Скажем метод рекурсивоного спуска - я могу предположить, что так называется когда динамику пишут не циклом, а рекурсией с запоминанием. Что касается Ахо-Карасика, то на финале в 2008 я решил задачу какую-то на строки, которая оказалась нашей седьмой и принесла нам золото, и когда я рассказал свое решение какой-то команде, мне сказали, что это Бор и Ахо-Карасик. Так что видимо это такой алгоритм, который очевидным кажется когда рука натискана. Вообще строки можно чаще всего сдавать хешами.

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

        Чтобы стать красным на топкодере надо знать очень мало. Там чаще задачи на то, чтобы извилинами пошевелить. Задачи на поток либо 1000 либо 600 - это уже о чем-то говорит :о) И за всю историю я только один раз видел задачу на фурье. Думаю, координаторы контестов там просят авторов не давать задачи на что-то специализированное. Иван Метельский вроде как там один из координаторов, он лучше знает. Правда не думаю, что он читает тут прямо все ветки, и заметит вопрос :о)
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          На ТопКодере для успешного выступления изучением множества специализированных алгоритмов заниматься (почти) бесполезно. Просто наиболее реальный результат использования задачи, которая очень сильно базируется на каком-то сложном алгоритме, который мало кто знает -- либо никто не решит, либо решат те, кто погуглят и возьмут его откуда-нибудь из интернета. Оба случая малоинтересны.

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

          Иногда (но тоже редко) бывает, что задача использует какой-нибудь (относительно) малоизвестный факт. Например, в январе была задача, существенно основанная на том, что любой двудольный граф имеет реберную раскраску в кол-во цветов, равное его максимальной степени. Так что в принципе изучение сложных алгоритмов может помочь, если их детально изучать, с обоснованием, плюс если знать много разных сопутствующих фактов. Но это тоже, мне кажется, довольно редкая вещь.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            БПФ должно быть в наборе библиотек, доступных на контесте.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Да ладно, в чём проблема его написать? Это совсем не сложный алгоритм, обычный разделяй-и-властвуй, скажем, на уровне с алгоритмом поиска ближайшей пары точек. И уж попроще многих строковых алгоритмов.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            У меня помнится тоже было решение с Карацубой
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Бытует мнение ( хотя я и не знаю конкретных примеров, но кажется верным), что чтобы стать на топкодере красным, достаточно быстро решать 250 в каждом из срмов. А какие конкретно алгоритмы есть в 250? Кроме Эвклида ничего не припомню, всякие там 250 финалов ТСО не в счёт:)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Бывала и динамика по рваному краю, думаю, что были и другие спец. темы
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Не, по-моему недостаточно. Надо еще иногда решать и 500.
            А вот если все время решать 250 и 500 - можно стать таргетом.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Наверное. Но я, вообще, хотел поставить ударение на том, что ad hoc - ов, задач без чётких алгоритмов, гораздо больше(на ТС, да и не  только). Да и кроме задач на общую "сёку" и алгоритмических, есть еще 3 класс, хеширование, динамика, дерево отрезков - описывают только общую идею, решить конкретную задачу помогает практика. Иначе говоря, лучше решить на контесте некую общую задачу, которую решило еще 10 человек, чем быть единственным, написавшим триангуляцию Делоне или другой, не менее ужастный алгоритм:) ИМХО.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                P.S. Не хочу чтобы меня поняли превратно) Лучше, конечно, решить обе, но если времени на обе не хватает - то..
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Неужели правда была динамика по рваному краю в 250? Я не встречал, но вообще для 250 это было бы слишком сложно (если брать уровень сейчас, а раньше вроде бы было легче).
            • 14 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится
              Впервые вижу термин "динамика по рваному краю". Это, случайно, не то же, что и динамика по профилю?
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Это можно сказать тоже самое, только профиль используется не на полную, а он рваный.. это ускоряет время и память ... =0 но такие задачи не такие частые ... =0
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            сорри за то что поднимаю старую тему, кто нибудь знает номер SRM'а этой *задачи? 
            *ДП по рваному краю на 250
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Как Вам удалось успешно выступать в ACM ICPC без знания решения задачи про диофантовы уравнения?:)

      Я читал блог и выяснил, что Вы работаете в Microsoft. А какой теорминимум нужен для того, чтобы попасть на такую работу? Как Вы нашли такую работу и что полезного Вы вынесли из университета? (я имею ввиду, какие курсы сейчас Вам более всего помогают в работе)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Первый вопрос снимается, я невнимательно читал обсуждение.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        На интервью в майкрософт дают очень базовые задачки. Перельмана надо почитать, чтобы готовиться :о)
        Проблема не пройти интервью, проблема попасть на интервью :о) Для этого очень хорошо помогает резюме вида

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

        Ну и там автоматически попадаешь на интервью :о)
        Такая же система работает с Facebook и Google :о) Но Microsoft - это кул, потому что штат Washington хоть и дождливый зимой, но невероятно красивый (see my blog). И Ванкувер рядом :о)
        А с точки зрения работы как таковой мне кажется везде одно и тоже.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      На одном из этапов открытого кубка надо было найти наименьший циклический сдвиг. У нас в команде никто не знал алгоритм Дюваля и мы написали Укконена и он прошёл.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          хмм, а разве можно  найти наименьший циклический сдвиг с помощью полиномиальных хешей
          • 14 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            Конечно!) циклом идешь по строке, храня текущий best, и бин поиском подбираешь общий префикс. Смотришь следующую букву, если она у cur < best, то best = cur
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Там были такие ограничения, что решение за O(n * log n) наверняка не прошло бы. И что такое полиномиальные хеши? В чём отличие от обычных хешей?
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            O(NlogN) наверняка прошло бы, иначе бы решения на Java не успевали бы считывать ввод :D

            Полиномиальный хэш от строки S = s1s2...sn есть , где p и P - какие-то числа, обычно простые, причем p - маленькое большее размера алфавита, P - большое. Удобства - если посчитать такие хэши для всех префиксов S (это можно сделать за O(N)), то потом для каждой подстроки можно вычислить хэш за O(1) (как - додумаетесь сами:)).
          • 14 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            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) (как - додумаетесь сами:)).
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ну вот у меня кастомный ридер для Java работает быстрее scanf ;)
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Вообще в идеале mod P не должно быть
              В идеале считаешь в 32-ух/64-ех битных числах, доверяя просто их переполнению. Потому что использование модуля (которые видимо меньше чем maxInt / p) повышает заметно шансы на коллизию
              Я не помню тока что в ява происходит при переполнении - не выбрасывает ли она исключения.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                да, я тоже считаю просто с переполнением. а в том после я указал P потому что так принято везде, где я читал про полиномиальные хэши.

                Насчет явы не наю - я там даже быстрее чем scanf считывать не умею...
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                нету в Java эксепшнов на переполнение. Не паскаль чай
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  В си шарпе они есть, хотя он тоже "не паскаль" :)
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Ну в C# они есть (их можно обойти обернув в unchecked нужный кусок кода). Хотя, как известно, за C# и Delphi стоит один и тот же человек :о)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А существует ли алгоритм Штайна :) ?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Меня нервирует алгоритм Карацубы. Из какой это параллели?
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
На сайте http://neerc.ifmo.ru/school/ в архиве учебно-тренировочных сборов за 2008 г. имеется файлик "Программа международных олимпиад по информатике вер 04072007.doc" ("Примерная программа по информатике для подготовки сборной команды России к международной олимпиаде"), который тоже представляет из себя некий теорминимум, причем разбитый по разделам, а сложные темы помечены одинарными и двойными звездочками. Олимпиаднику должно быть полезно.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Список тем, входивших в 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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Так, то, что все алгоритмы здесь нужны, это понятно. А есть нужные алгоритмы (кроме дефолтных), которых здесь нет?

    Судя по полуфиналу этого года в геометрию ещё можно добавить центр масс пространственного тела. :o)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А вообще список очень классный. Спасибо!
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В последнее время бывает попадаются задачи на минимальное покрытие путями.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Конечно, список можно продолжать до бесконечности. Но всего, что может пригодиться, все равно не предугадаешь заранее и не выучишь. До чего-то приходится додумываться самостоятельно. 

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

      Кое-что важное, что не вошло в список: потоковые алгоритмы, функция Гранди для игр.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А вот мы что-то не догадались вывести и так и остались с тремя задачами при правильном решении с неверной формулой.

        В любом случае спасибо большое за адекватный список.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Что-то не верится мне, что вы не сможете написать поиск возрастающей подпоследовательности без бумажки :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Имеется в виду алгоритм за NlogN (без дерева отрезков). Его я не могу быстро и правильно написать без бумажки. Проверено на горьком опыте:(
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Имеется в виду замена дерева отрезков каким-то другим деревом или совсем другой алгоритм?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        дак ведь там же просто бинарный поиск зачем вообще деревья
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хотел поинтересоваться у тех, кто участвовал в ACM ICPC....

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


  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По крайней мере до 2008 года команда могла пронести с собой тонну макулатуры с чем угодно на финале
    На полуфинале ничгео нельзя брать с собой.

    В 2010 я не видел печатных материалов ни у кого на столе на финале, есть подозрение, что убрали это дело.
    В любом случае, мы на финале в приготовленную папку заглянули один раз - ручку взять :о)
    Задачи, насколько я помню все финалы которые прорешивал, не требуют каких-то экстраординарных знаний обычно.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Там можно было пользоваться распечтками (notebooks вроде назывались), которые заверялись при регистрации. Единственное, что могло пригодится это геома (но все равно не спасло)
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Раньше каждая команда могла принести с собой на финал team notebook. Это папка с эмблемой университета, содержащая раздаточные материалы (расписание, задача пробного тура, указания к решению задачи пробного тура и прочая макулатура), канцтовары, чистая бумага и reference document, содержащий не более 25 страниц с текстом, читаемым для человека с нормальным зрением. В reference document как раз и можно включить нужные алгоритмы, формулы и т.п.

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