This article is to guide you to attempt your 1st coding contest, to make familiarize yourself with the procedure, and kickstart your journey with competitive programming.
What is Competitive Programming?
CP(Competitive Programming) is basically a mind sport where you are given a problem statement and you are required to give an optimized solution under various constraints by using your programming skills.
If you think it's difficult, as kids we are given word problems and we had to convert them into mathematical statements, similarly here we're given English statements and we need to convert them into programming problem statements. What's different is in math we use concepts like addition, product, etc.. and here we use concepts like loops, arrays, sorting, etc..
Prerequisites?
Learn a Language: In order to get started all you need is to learn a programming language (eg- C, C++, Java, Python, etc). Generally, c++ is the most preferred language by many people because it's comparatively fast and offers a very powerful library STL (Standard Template Library) which makes it easy for Competitive coding. But any language based on your comfort is fine.
Understand the Workflow: As a beginner, understanding how things happen is really necessary, if you have time for your next contest or else after the contest read over the article linked below to get insights into what all topics are required to be good at CP.
Some Basic concepts to be covered
- Brute Force
- Test-Cases
- Constraints
- Custom Input
- Possible Wrong Solutions
- Example Program
1. Brute Force:
To get well versed with Brute Force let's consider an example, Consider a program to check whether the given input is a prime number or not.
- The idea to solve this problem is to iterate through all the numbers starting from 1 to n and check whether each number is a factor of a given number. The given number will be prime if the number of factors is two, otherwise, the number is not prime. The above method will be Brute Force for the given problem. But we can optimize this solution to make it more efficient.
- One of the optimizations can be iterating the loop up to n/2 as after n/2 there will be no factors obviously.
- But the best-optimized way is to iterate the loop up to the square root of n.
- For further reference: link
You might be wondering why this factor is important in CP, you'll understand its importance as you go further in this article.
2. Test-Cases:
One of the main aspects of CP will be test cases. Test cases are the multiple inputs for the given problem of varying constraints. The test cases of the problem will be hidden, your solution will be evaluated on these test cases and your solution will pass only if all the test cases are satisfied.
3. Constraints:
Constraints will tell us about the range and nature of various parameters associated with the problem. Generally, constraints will have the range of 10^5, 10^9, or even higher.
4. Custom Input:
It's a very new stunning aspect of CP! Unlike our classic programming way where we give comments like "enter your input: " we shouldn't add such things in our program because all the inputs are given by the computer which is already set and we just need to take the inputs in space-separated order.
The above picture is a sample of custom input for the addition of two numbers, wherein the first line of custom input is the number of test cases.
5. Possible Wrong Solutions:
- Wrong Answer (WA)
- Run Time Error
- Compilation Error
- Time Limit Exceeded (TLE)
All might know about the first three cases, and you might be new to the fourth case (TLE). For each problem, the problem setter will set a time limit (generally 1 second) for the whole execution of your solution over all the test cases. For a problem, if you apply a brute force with time complexity O(N), O(n^2), or even higher, you may get TLE most of the time, to avoid that we need to optimize our approach every time.
Generally an ideal system can perform 10^8 operations in a second
For example, if your algorithm has a time complexity of O(n) and given constraints is 1<n<10^9 then you'd probably get a TLE when you submit. So, now you have to try to optimize your solution to O(logN) or even lower.
6. Example Program:
Approach to Solution:
Let's consider different ways to approach the solution. First, let us look at the naive approach...
Naive Solution: As is clearly given in the question, you have to choose a number A from a range of [2, N], and you have to fit exactly A number of cupcakes in each package, Chef is allowed to eat the remaining cupcakes. The number of packages and size of the package are not your concern. So our naive approach will be iterating the number of cupcakes from 2 to N through a loop and checking in which case the count of remaining cupcakes will be maximum.
Program:
If you submit the above program, you'll get a TLE for sure since the Time Complexity is O(n*t) which won't fit our constraints because the value of n is in the range [0, 10^8] and the number of test cases (given) is 10^3, so the for loop would run for about 10^11 times which takes more than a second which exceeds the limit!
Let's try to optimize our solution,
- Better Solution:
Let's look at an example, Consider 5, we can represent 5 as 1+4, 2+3, 3+2, 4+1.
In the case of 1+4 or 4+1 if we have chosen 1 as A, obviously the remaining cupcakes will be 0 as we can fit each cupcake in 5 packages.
If we choose A as 4, the number of cupcakes left will be 1.
In the case of 2+3 or 3+2, if we choose 2 as A, one cake will be left as we can fit 2 cupcakes each in 2 packages.
If we choose 3 as A, 2 cupcakes will be left and we have chosen 3 as our a and we can't fit 2 remaining cupcakes in any other package.
Now, let's generalize this observation, If we are choosing A as (half of N)+1, the remaining cupcakes will be (half of N) - 1 which is the possible maximum count of leftovers in any case. By this approach, the time complexity would be O(t) which is really better!
Solution for the above problem in a few popular languages:
- In C:
#include <stdio.h>
int main(void) {
int t;
long int n,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%ld",&n);
printf("%ld\n",n/2+1);
}return 0;
}
- In C++ :
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout<<n/2+1<<"\n";
}
}
- In java :
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- !=0)
{
int n;
n = sc.nextInt();
int ans = n/2+1;
System.out.println(ans);
}
}
}
- In Python:
t=int(input())
for i in range(t):
n=int(input())
print((n//2)+1)
Output Solution
The aim of this example is for you to understand the importance of time complexity in your solution...
That's all for now, if you want to know more about CP in detail and road maps to learn, refer to the article given: link