You are not logged in. Please login at www.codechef.com to post your questions!

×

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

126
112

Hello all,
I've been practicing at Codechef for a while and now I'm gradually moving toward medium/hard problems. However many algorithms at these levels are very difficult to predict, and I was always stuck because I'm not aware of them. So I open this topic, my hope is to have a wish-list of most used algorithm for online programming contest that I can look up for reference. Here is my short-list up to now:

  1. Segment tree (with lazy propagation)
  2. Interval Tree
  3. Binary Indexed Tree
  4. Fast Modulo Multiplication (Exponential Squaring)
  5. Heuristic Algorithms
  6. KMP string searching
  7. Manacher's Algorithm
  8. Union Find/Disjoint Set
  9. Trie
  10. Prime Miller Rabin
  11. Matrix Recurrence + Fast Modulo Multiplication for counting
  12. Stable Marriage Problem
  13. Extended Euclid's algorithm
  14. Ternary Search
  15. Fast Fourier Transform for fast polynomial multiplication
  16. Djikstra's algorithm, Bellman-ford algorithm, Floyd-Warshall Algorithm
  17. Prim's Algorithm, Kruskal's Algorithm
  18. RMQ, LCA
  19. Flow related algorithms, assignment problem, Hungarian algorithm
  20. Bipartite matching algorithms
  21. Heavy-light decomposition
  22. Sweep line algorithm
  23. Z algorithm
  24. Convex Hull
  25. Suffix Arrays
  26. LCP
  27. Suffix Tree
  28. Gaussian Elimination
  29. Numerical Integration/Differentiation
  30. Line Clipping
  31. Advanced Maths Ad-Hoc problems
  32. Aho–Corasick string matching algorithm;
  33. Calculate nCr % M Lucas's Theorem
  34. Heavy Light decomposition in trees
  35. Inverse Modulo operations
  36. Pollard Rho Integer Factorization
  37. Catalan Numbers

Add some more...

This question is marked "community wiki".

asked 24 Jul '13, 13:02

tyrant's gravatar image

1★tyrant
1.2k202734
accept rate: 12%

edited 17 Sep '13, 18:15

n2n_'s gravatar image

5★n2n_
1.8k61319

11

It will be great if we can build on this to give links of useful resources against each algorithm and also mention problems which require these algorithms to be solved.

(24 Jul '13, 19:48) admin ♦♦0★
1

@admin nice thought...it will be very very helpful :)

(24 Jul '13, 20:16) donofgaya4★
2

@admin: Great suggestion. Will do when I have time ;)

(24 Jul '13, 22:25) tyrant1★
4

Should we make this as a community wiki and people can keep adding and editing it there? The down side is that the votes that you have gathers will be lost. Or we can create another community wiki with the contents of this thread and the community can edit it there. What say?

(25 Jul '13, 13:54) admin ♦♦0★
11

@admin: Please do, I don't mind those votes as long as it will help the community ;).

(26 Jul '13, 22:42) tyrant1★

@admin: Although many of the things listed above are covered in society like Topcoder, codeforce as well there are content available at the internet too. The more detail list is available at (http://www.codechef.com/getting-started -> List of Topics for programming Competitions). Again if the things are missing and we have better solutions, we can write it under the tutorial section in codechef.

(12 Aug '13, 16:48) ravishanker3★
1

I have added link to my tutorial about point 3 on the original post... If you find it good enough feel free to add it to codechef for schools page as well! It would be an honor :D

(12 Aug '13, 22:59) kuruma2★

Added link to point 12 :)

(14 Aug '13, 02:46) kuruma2★
1

I'm bringing this back up to let you all know that I will use my own problem, MARBLESGF to write a tutorial on BIT/Fenwick Trees :) I will post it when its complete and also provide link here :D

(02 Jan '14, 06:25) kuruma2★

Awesome compilation of all stuff in one place, appreciate everyone's hardwork :)

(07 Jun, 11:26) godslayer122★
showing 5 of 10 show all

  • Euclid's GCD Algorithm
  • Extended Euclid's algorithm
  • Binary Search, Ternary Search
  • Sieve of Eratosthenes for finding primes
  • Fast Fourier Transformation for fast polynomial multiplication
  • Graph algorithms - BFS, DFS, finding connected components
  • Djikstra's algorithm, Bellman-ford algorithm, Floyd-Warshall Algorithm
  • Prim's Algorithm, Kruskal's Algorithm
  • RMQ, LCA
  • Flow related algorithms, assignment problem, Hungarian algorithm
  • Bipartite matching algorithms
  • Heavy-light decomposition
  • Sweep line algorithm
  • Z algorithm
link

answered 24 Jul '13, 13:39

n2n_'s gravatar image

5★n2n_
1.8k61319
accept rate: 9%

edited 24 Jul '13, 13:42

19

A very useful link ,list in-dept analysis of basic to advanced algorithm ,many which are listed above ,very helpful read http://e-maxx.ru/algo/ though in russian but google translator might help. :)

link

answered 27 Jul '13, 03:48

johri21's gravatar image

2★johri21
436137
accept rate: 12%

13
  • Kruskal's or Prim's algorithm
  • Dijkstra's algorithm
  • Convex Hull

Edit: It would be a nice idea to group these algorithms. For example, KMP algortihm, Aho-Corasick algorithm, Rabin-Karp algorithm all fall under the category of String Match, and hence should be put under the category of string match algorithms; and so on for other algorithms as well.

Grouping would help newbies like me to explore a particular group and learn all the algorithms in that.

link

answered 24 Jul '13, 13:45

bugkiller's gravatar image

3★bugkiller
8.6k194898
accept rate: 9%

edited 24 Jul '13, 15:25

13

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 :)

Best regards,

Bruno

link

answered 24 Jul '13, 14:23

kuruma's gravatar image

2★kuruma
17.2k72143208
accept rate: 8%

Hello @all and especially @admin,

Is the idea of linking all of the above topics to some resource with a tutorial and suggested problems still up?

Because if it is, I can try to write about the topic 3. Fast Modulo Multiplication (Exponential Squaring), as it is a topic I master relatively well, and, when I'm finished with my tutorial I can provide the link here :D

What do you think?

Best regards,

Bruno

link

answered 12 Aug '13, 16:39

kuruma's gravatar image

2★kuruma
17.2k72143208
accept rate: 8%

1

Great job!

(14 Aug '13, 11:34) tyrant1★

We still have much more to do :D And me, personally, I have way much more to learn :p

(14 Aug '13, 15:20) kuruma2★

This website can also of great help in learning basic algorithms: http://www.learnalgorithms.in/

link

answered 14 Aug '13, 10:37

coding_addict's gravatar image

4★coding_addict
310347
accept rate: 0%

link

answered 13 Aug '13, 06:20

akrai48's gravatar image

2★akrai48
180237
accept rate: 0%

I'd suggest further adding

Some useful resources : come on code on

Some cool problems : Nikhil Garg's blog on quora

link

answered 14 Aug '13, 10:16

code_master01's gravatar image

5★code_master01
1.1k132229
accept rate: 0%

edited 14 Aug '13, 10:27

Tutorial on disjoint set and union find with supporting heuristics. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure

link

answered 14 Jul '14, 13:01

anuragjain's gravatar image

3★anuragjain
161
accept rate: 0%

Levenshtein distance algorithm

link

answered 24 Oct '14, 04:52

pranjalranjan's gravatar image

4★pranjalranjan
2.0k21432
accept rate: 20%

> Catalan numbers

Why?

This is not an algorithm. The way they can describe a lot of stuff is nice, but I've never ever seen them used in a solution in competitive programming (unless you count "bruteforce the first few numbers and google them in OEIS" an algorithm, which I don't).

Similarly, anything that contains "ad-hoc" is not an algorithm, practically by definition. "Ad-hoc" means something that doesn't fall under a well-known algorithmic technique.

link

answered 24 Oct '14, 05:19

xellos0's gravatar image

7★xellos0
5.7k53875
accept rate: 10%

Being a beginner and a little weak at Data Structures particularly from where should I start to get a good grip eventually?

link

answered 26 Oct '15, 03:45

raunak_parijat's gravatar image

4★raunak_parijat
8726
accept rate: 0%

There is an "awesome" resource for this and a lot other things. https://github.com/sindresorhus/awesome Though I don't remember the original author's name, this is the best I've come across. Be sure to check it out.

link

answered 26 Oct '15, 13:51

wiseboy's gravatar image

2★wiseboy
129110
accept rate: 0%

sieve of eratosthenes and segmented sieve

link

answered 29 Nov '16, 21:37

chunky_2808's gravatar image

3★chunky_2808
496
accept rate: 0%

You can also add data structures as DS + Algo's = Programs. I suggest adding a few basic data structures which would help. Also you could add topics like DP.

link

answered 30 Nov '16, 12:38

mathecodician's gravatar image

5★mathecodician
2.2k216
accept rate: 8%

Centroid Decomposition of Tree

link

answered 30 Nov '16, 12:58

abhi1shek1's gravatar image

4★abhi1shek1
365
accept rate: 16%

Can anyone also mention the approaches that we have to know like Dynamic Programming or any other approaches for programming contests. Classifying these algorithms based on the approach will also really be beneficial, may be i am asking for more here :).

link

answered 13 Apr, 17:43

sai_praneeth's gravatar image

2★sai_praneeth
614
accept rate: 0%

"Sorry You don't have enough reputation to upvote" How to get reputations :'( ??

link

answered 07 Jun, 05:33

tanmoy_datta's gravatar image

4★tanmoy_datta
1
accept rate: 0%

Google "Codechefs new karma system" and go through the list.

(07 Jun, 10:13) vijju1233★

Hey guys have a look at this blog :::: Important Data Structures and Algorithms

link

answered 07 Jun, 07:23

harrypotter0's gravatar image

2★harrypotter0
355
accept rate: 0%

link

answered 07 Jun, 11:32

kaush1's gravatar image

3★kaush1
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×1,311

Asked: 24 Jul '13, 13:02

Seen: 39,521 times

Last updated: 07 Jun, 11:32