sharmaeklavya2/cpintro.md

## cpintro.md

      
    Raw
  

              cpintro.md
            
          
    Introduction to Competitive Programming

--
Presentation summary


What is competitive programming (CP)?
Why do CP?
How and where to practice?
Comparison of programming languages
Programming language specific tips
Programming environment - tools and runtime errors
Fast IO
Time complexity
Containers/Collections
Modular arithmetic

--
Learn programming


Choose a language
Read tutorials
Practice (usually by competitive programming).

--
What is CP?


Programming according to input/output specification.
Example: https://www.codechef.com/problems/FCTRL

--
Why do CP?


It's fun. It's definitely fun for those who like programming and math.
You don't have to memorize much and it's very objective.
It's easy to start. CP is very practical. (compare to OS)
It's the most asked thing in CS placements.
It will make you a good and fast programmer.
It's a good way to learn a language.
It will improve your problem solving skill.

--
Where to practice?

Popular online judges:

Codechef
Codeforces
Hackerrank
Hackerearth
SPOJ
Topcoder

--
How to practice?


Try to solve problems which are challenging but not too difficult.
Start with easy problems (usually the ones with most submissions) initially.
If you can't solve a problem, read the problem's editorial.
Occasionally look at others' code.
Discuss problems with your peers.
Keep learning about a programming language if you haven't already.

--
Participating in contests


Start participating in contests:

Codechef long challenge
Codeforces rounds
Codechef cookoff
Other contests on other OJs


Contests provide a competitive, time-constrained environment.


--
Afterwards


Once you solve around 30-40 problems,
you should learn about new algorithms and data structures.
DiSCo - MIT Math for CS.
Do problems on Math, DP when starting out.
I used NPTEL for DSA (youtube videos).
Above resources aren't enough, but they cover a good amount.
You must keep learning from other resources.
LightOJ is a good resource to practice problems from a specific topic.

--
Comparison of programming languages


C
C++
Java
Python

--
Programming language specific tips


Integer overflow
Storage classes in C, C++
Runtime errors (SIGSEGV, SIGFPE, SIGABRT) in C/C++.
Exceptions in Java and Python.
Return code
GCC Flags
GNU Debugger

--
Programming environment


Linux vs Windows vs Mac.
Text editor and command-line, benefits like redirection.
IDE
Checking execution time

--
Fast IO


scanf and printf are faster than cin and cout in C++.
BufferedReader is faster than Scanner in Java.
sys.stdin.readline() is a bit faster than input() in Python.

--
Time complexity


It's a way to measure efficiency of code.
Example: Linear Search
Example: selection sort
Example: Binary Search
Example: Merge sort
Example: Finding number of distinct elements in a list
Finding expected time complexity from constraints.

--
Containers/Collections and common algorithms


vector, linked-list, set, map, algorithms, iterators
http://en.cppreference.com/w/
https://docs.oracle.com/javase/8/docs/api/overview-summary.html
https://docs.python.org/3/

--
Modular Arithmetic


What is it?
Addition, Subtraction, Multiplication
Exponentiation

--
Quick Problem

Find the last digit of 3⁴⁰⁰.