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

Помогите советом.
Автор Rivand, 12 лет назад, По-русски

Пусть и баян, но все таки... Скажите как готовиться по олимпиадному программированию? Готовлюсь сам без чьей либо помощи, времени для подготовки хватает.Нужен совет как готовиться, что учить, список тем, последовательность тем, какие-то отрезки времени, за которые должен что-либо изучить, методика, литература, ссылки, советы, любая инфа, пусть даже и кэпская, вообщем приветствуется все. Жду с нетерпением.

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

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Поможет чтение книг (и сайт e-maxx.ru) и прорешивание архивов.

Книги — Меньшиков, Скиена, Кормен и др. архивы — acm.timus.ru, и др.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Вы указали в тегах "подготовка", но ведь сделав поиск по этому тегу уже находится не мало.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    имеет ли это столь огромное значение?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

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

      → Ответить
»
12 лет назад, # |
← Rev. 6   Проголосовать: нравится +1 Проголосовать: не нравится

  • "Mathematical reasoning" or "talent" is fundamental to problem solving . This is different from mathematical 'knowledge'. "Reasoning" is to reasonably justify algorithmic steps you think of in the process of arriving at a solution.A useful method is to solve some problems from math olympiads from time to time.

  • implementation skills are important, dozens of adhoc / BF ACM regional problems are available on UVa online judge.

  • Elementary Complexity theory (Big O notation)

  • Useful Data Structures (e.g BST) + powerful features of your programming language (e.g C++ STL)
  • Binary Search
  • Bit manipulation
  • Graph theory :
  1. Graph traversal (depth-first and breadth-first search 'DFS — BFS')
  2. finding connected components of undirected graphs
  3. finding strongly connected components of directed graphs
  4. topological order of directed acyclic graph
  5. Shortest Paths (Dijkstra + heap , Bellman-Ford , Floyd-Warshall "Transitive closure" )
  6. Minimum Spanning Tree (Kruskal's Algorithm — Prim's algorithm)
  7. Network flow / Bipartite Matching
  • Greedy algorithms
  • Dynamic Programming : [some classical problems include:] — Longest Common Subsequence LCS — Longest Increasing Subsequence LIS — Edit Distance
  • Computational Geometry : — Sweeping Line method (closest pair problem , line-segment intersection problem) — Convex Hull algorithms
  • More advanced data structures : — Segment Tree — Binary-Indexed Tree — Disjoint sets(Union-find)

  • Useful theoretic content is available on the following links [TopCoderTutorials

  • algorithmic Wiki ]

  • Popular Online Judges : [SPOJ , UVa , POJ]

→ Ответить