Rivand's blog

Need an advice.
By Rivand, 12 years ago, translation, In English

How to prepare myself for olympiad programming without any help(selfstudy)? Need advice on how to prepare, what to teach, the list of topics, sequence of topics, any links, any literature, tips, trick, any information is welcome.Waiting for answers.

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
12 years ago, # |
← Rev. 6   Vote: I like it +1 Vote: I do not like it

  • "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]

→ Reply