What are the "must known" algorithms for online programming contests?

Hello,

I can add a few more topics:

  • Suffix Arrays;
  • LCP;
  • Heuristic Algorithms;
  • Gaussian Elimination;
  • Numerical Integration/Differentiation;
  • Line Clipping;
  • Advanced Maths Ad-Hoc problems;
  • Aho–Corasick string matching algorithm;
  • Knuth–Morris–Pratt algorithm;

Sadly, this list is endless and the hardest part is to understand which of these topics need to be applied to solve a given problem.
As a bonus, you can have variations of these standard topics which may require mixing some of these concepts.

I will edit the above post with all these suggestions, except some of the suggestions given by @n2n_, since putting on the same bag, FFT and Sieve of Eratosthenes for finding primes, seems a bit overkill to me, as the second one is a basic algorithm and not needed to advanced problems I would say :slight_smile:

Best regards,

Bruno

15 Likes