### TheScienceGuy's blog

By TheScienceGuy, history, 6 months ago, ,

Hi, I think it is a good idea to add standard problems (like DFS, find cycle in graph, Convex Hull...) in codeforces problemset which most of competitive programmers learn, so that we can test our solutions as we are learning the algorithm. The problems should look exactly like the original ones (for example, the problem of printing a cycle from an unweighted directed graph should look like this: "Given the vertices of an unweighted directed graph, print any of the cycles in this graph. If it has no cycles, print -1"; then we describe the limits and IO format. Formulating problems this way saves time while training). I will start writing a list of standard problems/algorithms, feel free to add:

Sorting: 1. MergeSort 2. QuickSort 3. SelectionSort 4. RadixSort 5. BucketSort 6. Binary Search

Graph Algorithms: 1. DFS 2. BFS 3. Finding Cycle 4. Checking if graph is bipartite 5. Dijkstra's algorithm 6. Floyd-Marshall's algorithm 7. Checking connectivity 8. Kruskal’s Minimum Spanning Tree Algorithm 9. Finding if there is a path between two vertices

Dynamic Programming: 1. Knapsack problem 2. Edit Distance 3. Longest increasing subsequence 4. Longest common subsequence

Computational Geometry: 1. Constructing Convex Hull 2. Checking orientation of 3 points

I will add more problems/algorithms to the list if the users like the idea. Creating and adding problems is discussed in this post: https://codeforces.com/blog/entry/52135 . I will add some problems, but it is better if the users with high rank do this.

•
• +36
•

 » 6 months ago, # |   0 Auto comment: topic has been updated by TheScienceGuy (previous revision, new revision, compare).
 » 6 months ago, # | ← Rev. 2 →   +5 I will be glad if someone translates this post into Russian.
 » 6 months ago, # |   0 There are SPbSU training contests in gym, which contain many standard problems. Unfortunately, their statements are in Russian.
•  » » 6 months ago, # ^ |   0 Thank you. Training contests in gym are still different though, there you can not see on which tests your solution fails, which significantly slows down the learning process.
 » 6 months ago, # |   +6 First of all I don't see why something like this should be added in CF since you can find almost each and every one of these standard problems in SPOJ, asked as is. Now about sorting I don't see how a problem asking you to implement merge sort can be tested accurately (meaning you will get WA if you sort using another algorithm).
•  » » 6 months ago, # ^ | ← Rev. 2 →   +22 Output 1 on the second line if you used merge sort
•  » » 6 months ago, # ^ |   0 It is very simple to test it: the output should be the values of the elements being merged. Even though there are several ways to implement merge sort, the core idea is the same so demanding to implement one of them is a reasonable choice for learning process.
•  » » » 6 months ago, # ^ |   0 You have still the problem that with mergesort, if the set to partition has odd number of elements, then the implementation can decide where to place the element in the middle, and the implementation would be correct in both cases.But even if you figure that out, checking if something was sorted with quicksort can be a challenge.
•  » » » » 6 months ago, # ^ |   0 That is why a certain implementation can be demanded which will have a unique output. If the user understand the main concept of merge sort then implementing it in a certain way should not be a problem. Agree on quicksort, but as I said, it is for the learning process (not for the contest) so it is up to the user to actually submit the quick sort implementation and not just use sort() function or whatever.
 » 6 months ago, # |   -11 What the fuck is Floyd-Marshall's algorithm?
•  » » 6 months ago, # ^ |   0 "Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles)." https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
•  » » » 6 months ago, # ^ |   +14 LOL. Floyd Marshall != Floyd Warshall
•  » » » » 6 months ago, # ^ |   +26 Sorry my bad, always called it Marshall.
•  » » 6 months ago, # ^ |   +26 They misspelled a single letter. Get over yourself.
•  » » » 6 months ago, # ^ | ← Rev. 3 →   -15 I would certainly like to see you misspell a single letter in your variable name in the next contest.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -9 The most basic form of respect that you can give to the inventors of the algorithm is to spell their names correctly.
 » 6 months ago, # |   -7 DSU Sieve of Eratosthenes segment tree Trie persistent segment tree persistent trie convex hull trick