Introduction to Competitive Programming - YashasKamath/IECSE-Summer-Bootcamp-2022 GitHub Wiki

Let us first talk about how one should approach a problem in Competitive Coding. There are broadly 4 steps -

1. Understanding the problem: Try and figure out the basic logic behind the problem. If you don't understand how it's working, then the best way around it is to write up some random test cases and figure out the logic. This process helps you later to test your code more thoroughly.

2. The Algorithm: Come up with an algorithm. Don't start coding yet. Find cases where your code might be failing. Take care of these cases. This is an iterative process. Always look for cases you might be missing. More formally, prove the correctness of the algorithm. Run the algorithm over the test cases that you found in Step 1. This process is called a dry run.

3. Validate Constraints: Once you have an airtight logic, find the runtime of your algorithm. See if it's enough to pass the time limit considering the worst case, not the best case. If it isn't, find ways to optimize the code. Most of the time, it's a data structure that helps you out. Most people overlook this step and this almost always results in a Time Limit Exceeded Error.

4. Code: Write the code. Submit. If it doesn't pass, that means you went wrong in one of the previous steps. Start again at step 1 to check the problem statement and see if you've missed some tiny detail in the question. Then start thinking of possible edge cases where your code might be failing. If there is a timeout error, that shows that you didn't check if the runtime fits in the given constraints. The best way to fix it then is to check the values being computed and see if there are any anomalies.

A few tips for everyone -

Master your language. If you're doing it in C++, learn the STL well, the same goes for Java and Collections. Have the tools you need at your disposal. Learn the different space and time complexities for each data structure. Not knowing the underlying complexities often leads to wasting time on attempting the problem with unnecessary and costly implementations.

The key to improving yourself is practice. People chose different ways to do this. You can choose a standard platform and sort the problems by the number of people who have solved the problem. Keep solving. The most popular choices are Hackerrank and Codechef. If you can't solve a problem even after trying it out a lot, look at the editorials. Understand the solution, and then implement it on your own. Look at other people's submissions. Sometimes the red coders have very intriguing solutions to the simplest of problems.

For your practice, we are providing you with a few problems based on all the topics listed below. You can find them here

Start attempting contests. CodeChef long contests are really good for beginners. Since this contest runs for ten days, you'll have enough time to research and find the right algorithms for the problems. Once you're confident, you can start attempting short contests on platforms like codeforces, codechef, etc. The most important time of a contest is after the contest. This is when you try solving the problems that you couldn't solve during the contest. This is called up solving. This is a very efficient way of learning new tricks, optimizations, and concepts.

Also check this out.