Slides used in ACM-CPSIG 2017

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⁴⁰⁰.

MIT math for cs link not working due to an linefeed character in the link. Please update.

I fixed it. It's working now. Thanks for pointing out!