How to Competitive Programming
velu vijay
Posted on July 2, 2020
" Programming make us to think " -- Steve Jobs
By proving this statement competitive programming evolves. It is a Mind Sport , people who participating were considered as Sport Programmers.
LEVEL 1 :
pick a language ( c/c++, java, python)
Four languages are available to complete a given in competitive programming. C/C++ were prefered by most of the coders because of its Speed and Libraries ( STL Standard Template Library ). Comparing with C/C++ other two languages were slow at execution.
Following links for C++ tutorials and references :-
- CPP Tutorials (official cpp website, providing the cpp tutorials from basic)
- Tutorials point (Learn cpp with simple and elegant at Tutorials point)
LEVEL 2 :
DSA(Data Structures & Algorithms) and Maths
Eventhough, you completely learned C++, DSA and Maths takes a major role in Competitive Programming. The Problems were based on the Logicial and Non-Real world related things. In order to complete the levels you must learn the DSA and Maths.
Most Important DSA and Maths topics:-
Dijkstra's - depending on the type of contest, you might see basic pathfinding problems, or you might see problems with non-obvious reductions to pathfinding problems. Whenever you have a cost minimization problem with a (reasonably small) finite number of states, an initial state and a target state, you can look at it as a pathfinding problem.
Bellman-Ford is useful for pathfinding when edges may have negative costs. For example if you're navigating a maze with potions which boost health and hazards which lower it, Bellman-Ford would be a great approach.
Floyd-Warshall is useful for computing all paths. It is sometimes used in problems where you don't need all paths, because it's so easy to implement. It is slower than other pathfinding algorithms though, so whether Floyd-Warshall is an option depends on the graph size.
Edmonds-Karp for max flow/min cut problems. One common application is bipartite matching problems. For example, given N people, M food items, and a list of each person's food allergies, how many people can you feed?
The Hungarian algorithm for assignment problems. Similar to the above, but in these problems the edges have weights, and we're maximizing the total weight rather than just the number of matchings.
The sweep line "algorithm" (more of a general approach really) is useful for various geometric problems, like the nearest pair problem. Also useful for a variety of intersection-related problems, like finding intersecting line segments, or conflicting calendar events.
Graham scan or another convex hull algorithm, for problems such as building a minimal fence to enclose animals.An algorithm for finding strongly connected components , such as Tarjan's.
Prim's algorithm for minimum spanning trees.
Knuth-Morris-Pratt algorithm for string searching.
For Maths: Number Theory , Discrete Mathematics , combinatorics, graph theory, geomentry, string analysis .
LEVEL 3 :
welcome to wild life :)
After completing two levels, you can start participating in online programming contests. There are bunch of websites available today and try to complete the beginner's level and then move on to Montly, Weekly and Yearly challenges.
websites which providing competitive programming challenges:-
LEVEL 4 :
Process of Contests
Ranks were distributed by number of problems solved, time taken to got "Accepted" for a program and even more qualities such as execution time, length of the program, and algorithms. Red , Blue and Green badges were available for top 3 rank coders.
Solutions of a problem were available on the websites forum but don't look at those. Take a paper and write the possiblities of algorithm to solve a given problem. Take time to solve it. Even after a hour, you can't get the results then move on to the forum for references. Be patient and consistent with it.
Benefits and Critisim of Competitive Programming
Participation in programming contests may increase student enthusiasm for computer science studies. The skills acquired in Competitive like programming contests also improve career prospects, as they help to pass the "technical interviews", which often require candidates to solve complex programming and algorithmic problems on the spot.
There has also been criticism of competitive programming, particularly from professional software developers. One critical point is that many fast-paced programming contests teach competitors bad programming habits and code style (like unnecessary use of macros, lack of OOP abstraction and comments, use of short variable names, etc.). As real software projects typically have many thousands of lines of code and are developed by large teams over long periods of time.
Yet another sentiment is that rather than "wasting" their time on excessive competing by solving problems with known solutions, high-profile programmers should rather invest their time in solving real-world problems.
References:-
Posted on July 2, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related