Competitive programming : A warm-up
Looking into the basics
If you’re reading this, you are probably prompted to start competitive programming but cannot figure out how. You’ve probably tried solving problems but are unable to get your solutions accepted. Competitive programming is quite different from other programming paradigms and usually, easier to grasp. You don’t need descriptive variable names or well-documented code. But that does not necessarily mean you code haphazardly because you will have to debug it if it doesn’t work.
The only thing you need to know to begin is a programming language the grader accepts. ACM-ICPC grader accepts C/C++, Java and Python. Almost all graders you’ll encounter will accept these languages (unless if a problem is made for a particular language).
C++ is by far the the most popular language of choice for competitive programmers across the world as it is usually faster than Java and Python, and most of the resources are available in C++. C++ also has a vast library called STL(Standard Template Library) which makes life a lot easier for competitive coders. GNU/G++ is the standard compiler for C++ and C++ 14 is the latest updated version of C++ available on online judges.
Python is an amazingly user friendly language as its codes are shorter and more concise than those in other languages and is especially used by most programmers in questions where there is a chance of integer overflow as python allows one to code without any limit on the integer value. The only flaw that python possesses though is of being slow. In comparison to C/C++ and Java, it is quite slow and thus on online coding platforms, the time limit for Python is usually higher than that of C++. To improve the speed of code execution for input/output intensive problems, like C++ python too has various input and output procedures. Normally one uses raw_input() (Python 2.7)/ input() (Python 3.5) to read and print to write. Though one can make use of sys.stdin and stdout.write() which are faster as compared to the normal input/output formats. For more information regarding fast i/o in python you can refer to here.
Java is an Object Oriented Programming Language. It is the next most popular programming language after C/C++ in competitive coding. It too has many libraries for data structures called Collections in JAVA. It is bit slower than C/C++. Fetching input using Scanner class, many times, leads to a TLE verdict. BufferedReader can be used for faster input. For its complete usage, you can refer from here. Java has the BigInteger library to handle the numbers larger than 64-bit Integers but it is cumbersome to use and problems involving large numbers can generally be solved using some math in C++.
After you know about programming languages, the next part is how to solve the problem. To solve a problem, just follow these simple steps :
- Read the Question: Not difficult at all. The problems generally contain long stories about some people and what not. You don’t need these to solve the problem. Read the input/output formats and constraints very carefully. If the output format doesn’t match with the required output format, it would give a Wrong Answer. Constraints are really very important part of the problem as it sometimes hints to the expected time complexity of the solution.
- Understand the Problem: Understand what is asked and what is given in problem. Verify your understanding with the sample test cases and the explanation given.
- Make an Algorithm: This is the most important part of solving. Use your problem solving abilities to think of an efficient algorithm for the problem satisfying the required time constraint. If the problem requires a standard algorithm that you know, you’re good to move on to the next step. Generally, this wouldn’t be the case in a contest. First try to think of a naive approach and see if it fits the time constraint. If not, see for some optimisation. If it still does not work, try to reduce the problem into simpler solvable problems. More and more practice will help you figure out how to solve more complex problems.
Naive Solution : Also called brute-force method. Simply do what the problem states. For instance if you need to find the sum of first n natural numbers, the naive method would be to do this :
But the optimized way would be to use the formula like :
4. Code(or write) the Solution: Before writing the solution, think of the data structures required, what data needs to be arranged in maps/arrays/vectors etc. Choosing right data structures according to the need of the solution helps in solving the problem much easily. If you think carefully before coding you wouldn’t get confused while writing the code. As you practice more and more, you’ll get better at thinking faster.
If you get stuck on a problem during a contest, it’s best to try your best before searching on the Internet or asking someone for the solution. Don’t give up if you get stuck. At times, competitive programming can be quite demotivating; but only persistence will help you learn and be a better coder. A lot of effort goes into improving your speed and accuracy in competitive programming.
Here are some FAQs people generally have while beginning :
Q. Which language should I use?
A. If you are new to the world of programming and have no prior knowledge for any other language it’s advisable to start with C++ for the reasons specified above.
Q. How should I learn C++?
A. cplusplus.com has some great tutorials and each function is elaborated. While learning about STL (Standard Template Library), these tutorials and the documentation comes in very handy. Rather than learning all concepts and then starting practice, it’s better to try problems and look for it whenever you’re stuck.
Q. What are the basic topics I need to cover to get started?
A. You need to know the basics : taking input and giving output, basic statements : iterative(loops), selective(if else) and basic data structure implementations like arrays and strings. Once you’re comfortable with these basic concepts (including functions and recursion), you can move on to learning other algorithms like sorting, binary search and gcd. Once you’re acquainted with these, you are ready to move to the advanced algorithms.
Q. What should i do if i don’t know the size of array? Can we have variable array size? Can I use pointers instead?
A. int x[n]; This is fine only when you know the value of n before hand otherwise it will result in compile time error. Similarly, int *x = new int[n]; is also fine if the value of n is defined before writing this statement. Also, keep one thing in mind that if you have to store 10000 elements, declare an array of size greater than 10000 e.g. int x[10010] and never forget to initialize them. This is because there might be situations in which you try to access an array location which is out of bound which can lead to runtime errors. Declaring array of somewhat large size can prevent this from happening. If you really want to declare an array of unknown size, don’t use pointers. Use vectors. Pointers can be hard to implement and debug.
Q. What is an algorithm? From where can I learn them?
A. An algorithm is basically a process which solves the problem in a finite time and finite number of steps. There maybe many ways of finding the result of the same problem so each of those ways qualifies as an algorithm. MIT OpenCourseware is the best place to learn them. If you prefer books, you can read CLRS ( Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein ) although fair warning : it is quite bulky! While the book is the Bible of algorithms and a great resource for learning, its size can be quite demotivating for a competitive coder. If you want something similar and comprehensive, the book by Skiena (The Algorithm Design Manual ) is nice.
Q. Why am I getting a Runtime Error/Wrong Answer/TLE?
A. Here is a good collection of FAQ regarding online judges and the judge verdicts.
Q. What sites should I practice on?
A. SPOJ has a vast collection of problems so it is pretty good for practice. Codechef has a good classification on basis of difficulty. Codechef Long Challenge is really good for learning as you have 10 days for 10 problems of all difficulties. It should be considered a must-do for beginners. Codeforces, AtCoder and CSAcademy have regular contests with good editorials. HackerRank has questions divided by topic and difficulty. TopCoder has great quality problems but the SRMs are (ir)regular and the arena is not very user-friendly.
The Big-O Time Complexity
Analyzing your algorithm is pretty crucial in competitive programming. The efficiency of algorithms are generally measured in Time Complexity and Space Complexity. Generally, we do not need to worry about Space Complexity as a lot of memory is available to us. But, it’s still not infinite. We cannot define Arrays and Strings with size larger than ~10⁸.
Time complexity is comparing the time required for algorithm to run in terms of the size of the input. A machine can perform up to 10⁷-10⁸ steps in 1 second.
Say, you want to find the maximum of N integers in an array. You would use the following code :
We need to think of the worst-case scenario while calculating time complexity. The exact time depends on the machine so we’re just interested in the asymptotic value of time complexity i.e. if the input size N tends to infinity how would time vary with N.
In the above example the total time would be would be a.N+b where a and b are arbitrary machine-dependent constants so the complexity would be O(N). You can read about Big-O notation here.
So,if you’re using Selection Sort or Bubble Sort(which has a time complexity of O(N²)) for an array of 10⁵ numbers, it’ll be around 10¹⁰ operations i.e. 100–1000 seconds. So it’s better to use Merge Sort or Heap Sort which has time complexity of O(N logN) which is around 1600000 operations and takes less than 1 second. As you can see, time complexity is not affected by small constant coefficients.
For a better understanding of time complexity, you can see this.
Programming and Algorithms Group, commonly known as PAG, is a student run group that fosters competitive programming under the Software Development Section at IIT, Roorkee. We have a forum open to all doubts pertaining to competitive programming for everyone.
