[go: up one dir, main page]

DEV Community

Cover image for How to Competitive Programming
velu vijay
velu vijay

Posted on

How to Competitive Programming

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

  1. CPP Tutorials (official cpp website, providing the cpp tutorials from basic)
  2. 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.

Screenshot from 2020-06-29 18-01-55.png

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

  1. Getting started

  2. Big O Notation

  3. Quora

  4. Introduction to programming contests

  5. Learn to code by Hacker Earth

  6. Competitive programming tutorials

  7. Related Algorithms

  8. CodeMonl

  9. Number Theory

  10. Stanford references

  11. CodeForces Blog #1

  12. CodeForces Blog #2

  13. Introductions to Algorithms

  14. Discussion
    Cpp refernces

  15. Quora

Top comments (11)

Collapse
 
rakshakannu profile image
Raksha Kannusami • Edited

Even though people criticize, only DS/Algo + competitive programming will get you your first job as a developer.

Collapse
 
yuripredborskiy profile image
Yuri Predborskiy

Depends on where you want to work. In my country nobody asked ds/algorithm questions at junior and middle roles, some easy questions appeared for senior role. But that could be because it is not emphasized in higher edication.

I'm studying competitive programming myself and find it useful as an extra skill for a developer, but not a deciding factor for a hire. I highly recommend making a few projects that you can showcase with open source code. Like a portfolio project or some api - these work for a web developer. They emphasize a far more important skill - ability to decide on a project and do it from start to finish.

Collapse
 
rakshakannu profile image
Raksha Kannusami • Edited

Most of the companies that recruit freshers test the student's DSA skills and conduct online coding test upon which we will be shortlisted for face to face interview. It's important to be good at coding as well as have some good projects on our resume.

Collapse
 
veluvj profile image
velu vijay

Exactly 💯

Collapse
 
mamunmohamed profile image
mamunmohamed

Awsome post buddy

Collapse
 
veluvj profile image
velu vijay

Thanks buddy 😊

Collapse
 
rohitkumarvarma1 profile image
Rohit kumar varma

That was an awesome article, can you please suggest the best resources to study the topics mentioned.. Plzz cause it would be a headstart for competitive programming beginners like me!!

Collapse
 
veluvj profile image
velu vijay

Many resources included in the post itself. Do check them first.

Collapse
 
onlinecodingblocks profile image
Kajal Singhal

Thanks for sharing this informative blog. Keep update your blog.

Collapse
 
divyakelaskar profile image
Divya Kelaskar

Thanks for the detailed compilation !
Saved !

Collapse
 
veluvj profile image
velu vijay

Always welcome :)