1 of 17

Beginner’s

Workshop

2 of 17

What is Competitive Programming?

  • Contest Structure
    • Range of problems from easy to hard involving implementation, data structures, and algorithms
    • Solve as many as you can while competing against other people
    • Compete as an individual or in teams of (up to) 3
  • Why?
    • Good way to learn and practice data structures / algorithms
    • Improve problem-solving abilities
    • Similar skills are tested in interviews

3 of 17

Example Problem

4 of 17

Input / Output

  • Input / output done through standard input / output
    • Console input / output, not command line arguments
  • Usually you will read in some input, do computation, and print your response
    • Some problems are “interactive” and involve multiple read/print stages
  • Sample cases are a good starting point, but shouldn’t be relied on entirely, as your program should work for arbitrary inputs that follow the constraints
    • Think about edge cases: what if n = 1?

5 of 17

Time Limits

  • Sometimes, a correct solution is not sufficient.
  • Your code also needs to run fast!
  • Sometimes, clever tricks can get you from O(n^2) to O(n * log(n)), etc.
  • Other times, you just need to decrease runtime by a factor of 1.5 or 2.
  • Typical time limits will be on the order of seconds.
  • A typical modern CPU does ~100,000,000 computations per second
    • plug constraints into big O notation and divide by 100,000,000 to get rough estimate.
  • Some operations are more expensive than others:
    • % vs + vs /, etc.
  • Maybe you have an infinite loop somewhere?

6 of 17

What happens when I submit and get…

  • Wrong Answer?
    • Test case 1 is generally the sample case
    • Double check output format
    • Think about edge cases
    • Integer overflow
  • Runtime Error?
    • Check for index out of bounds or divide by 0
    • Bad for loops are a common culprit
  • I get Time Limit Exceeded?
    • Check for infinite loops or recursion
    • Look at Big-O
  • I get Accepted?
    • :)

7 of 17

Templates

  • Some data structures or algorithms can be rather complex to code
    • E.g. Dijkstra’s algorithm
  • You may choose to build a library of helpful snippets to copy/paste
  • Some contests allow a limited amount of external help
    • E.g. ICPC allows 25 pages of reference material
  • Here are some basic templates for input and output:

8 of 17

How can I practice?

  • We use the platform Codeforces.com
    • Available problems 24/7
    • Get familiar with input/output
    • Problems of various difficulties on various topics

​

9 of 17

  1. Create an account & login

10 of 17

2. Choose a Problem

Problem name topics difficulty

11 of 17

3. Anatomy of a Problem

12 of 17

4. Submitting

13 of 17

5. Your result

14 of 17

5. Your result

15 of 17

Sample Problems

16 of 17

Tips to Approaching and Solving Problems

  • Getting a solution
    • Work out small examples by hand
    • Look for patterns or similarities in cases
    • Correct but slow solutions are better than fast and wrong ones!
  • Implementation
    • Remember your language’s data structures: arrays, lists, maps, etc.
    • Slow and steady wins the race – trying to code fast usually leads to bugs
    • Think about edge cases and write your own tests

17 of 17

Want to Learn More?

  • CS 104C!!
    • 1 hour elective to learn all about competitive programming, taught by us :)
  • UTPC
  • Competitive Programming Problems
    • Codeforces - lots of problems with editorials
    • Kattis - ICPC problem archive
    • CSES - classic problems and algorithms
  • Resources
    • usaco.guide
    • cp-algorithms.com