Saltar al contenido ForoHackers

Competitive programming: start here

Programación competitiva
#621 · Ophuscado · · Denunciar

Competitive programming is solving well-defined algorithmic problems against the clock: read a statement, find an algorithm, code it and pass hidden tests within time and memory limits. It sharpens problem solving, knowledge of algorithms and fast, correct coding, and the archive of past contest problems is a free, endless training set.

Key concepts

  • Complexity first: the input size tells you which running time can pass; a million items rules out a quadratic loop.
  • Core techniques: sorting, binary search, greedy choices, two pointers, prefix sums and dynamic programming.
  • Graphs and trees: BFS, DFS, shortest paths, union-find and spanning trees.
  • Number theory and counting: modular arithmetic, primes and combinatorics.
  • Testing: write a slow brute force and compare it with your fast solution on random small inputs to find counterexamples.

Vocabulary

  • Verdict: the judge's answer, such as accepted, wrong answer or time limit exceeded.
  • Time limit: the longest a solution may run on one test.
  • Editorial: the written solution published after a contest.
  • Template: reusable code you keep ready for input, output and common structures.

What to study, in order

  1. Pick one language, learn its standard library and its fast input and output.
  2. Solve easy problems on loops, arithmetic and sorting, and read the editorial of each one you miss.
  3. Learn binary search, prefix sums and greedy methods; then dynamic programming on the classic problems.
  4. Implement BFS, DFS, Dijkstra's algorithm and union-find from memory.
  5. Learn heaps, Fenwick and segment trees, and hash maps, and when each pays off.
  6. Take part in regular contests, practise under a timer, and upsolve every problem you missed.

Related tags

#algorithms #data-structures #complexity #graph-theory #combinatorics

Inicia sesión o únete para responder.