Skip to the content ForoHackers
Log inJoin

Competitive programming: start here

Competitive programming
#3127 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply