Beginner - 1

Beginner Section -1

Contents:-

1.   I/O in c++
2.   Understanding Test Cases.
3.   Time Complexity and time limits

Hey guys!
This is just a small effort to introduce you to the art of Competitive Programming.
Give it a read if you love or are enamoured by coding, and even if you are not this is
something which might cause a certain stir in your mind and get you fascinated with
the Art of Programming.

Programming basically entails analysing a given problem statement and working on
the data given in the problem ( by storing it in variables, data structures like arrays,

strings , graphs etc ) and carefully devising a technique ( an Algorithm ) to solve the
question to produce the desired output.


One of the highly recommended and preferred languages for Competitive Programming
(CP) is C++14. You can go through a basic extended tutorial on C++ on this mentioned
link: http://www.ntu.edu.sg/home/ehchua/programming/cpp/cp0_introduction.html

Those who are familiar with programming might agree with the fact that until now
probably you have yourself been giving the desired input to your programs and
running it to print the desired output in any format you please.

HOWEVER, this will not work in CP.

https://www.hackerearth.com/practice/notes/getting-started-with-the-sport-of-programming/
Most CP Practice will take place on Online Platforms like Codechef, Codeforces,
Hackerrank, Hackerearth etc. and the Online Judges(OJ) on these platforms are
as you might guess obviously automated.
This means that an input file with all the different inputs on which the question setter
wants to test your program is fed into your code using standard Input Methods
( cin , scanf() , get() etc ) in a particular format which is always specified in the question.

Also, your program should return/ print output in the specified format given in the
question as the output is compared with an output file provided to the OJ by the setter.

Since these two processes are automated, we need to make sure that the formats
are ditto as specified in the question.

https://www.codechef.com/problems/SPELLBOB

http://codeforces.com/contest/1020/problem/B

Another thing in CP which is tested along with the implementation of the problem is the
efficiency of the algorithm.

The Efficiency of an algorithm: is measured by the Time Complexity of the Algorithm
(obviously within a limited amount of Space Complexity as well ).
The Time Complexity is determined in terms of the Maximum Input Size ( N ) and we
check whether our algorithm’s time complexity as a function of N; T(N) will pass the
given Time Limit of the Question.
Time Limit is given in terms of seconds; with most Modern CPUs computing 100M = 108  

operations in a few seconds.

These operations are usually determined by the number of iterations in our loops or
the number of calls to our recursive function.
A Linear Algorithm -> O(N) is one in which each element is operated on a constant
O(1) number of times.

A Quadratic Algorithm -> O(N2) is one in which each element is operated on a linear
O(N) number of times.

We can estimate the desired Time Complexities of the solutions by checking the Upper
Bounds of all the Input Variables and by Trial and Error figuring out what may pass
within the time limit.

Another thing to keep in mind is that we need to use appropriate data types according to what the maximum value can be, which is stored in that variable.
Typically a integer global array of size 108 is amongst the largest contiguous
space declaration we can make, and local arrays of size 107 are permissible.

Overflow of DATA is also a problem which flummoxes one and all, and a seemingly
correct algorithm produces Wrong Answers. Read about overflow here:
https://www.hackerearth.com/practice/notes/getting-started-with-the-sport-of-programming/

What happens basically is that if the data to be stored increases the max value
which can be stored in a variable of that particular type ( limits given down below ),
it actually loops around and starts from 0 again (modulus operation effectively takes place)
leading to possible errors in the Output which of course the Compiler cannot detect.
This will be covered in more detail on a write-up on Modular Arithmetic and
OverFlow Handling, but as of now you need to know the possibility of this happeningand ensure the use of appropriate data types to suit the purpose.

Some light hands on practice can be done here as well too. Though simple make sure
you carefully analyse and understand the significance of each line of code to get a feel
of what you are supposed to code and where.
https://www.hackerearth.com/practice-onboarding/welcome-to-online-programming-1/

Competitive Programming 3 by Steven Halim/Felix Halim

Written By:
Himanshu Mundhra
Vivek Gupta