# CS 4991 - Week 1 ### The Competitive Programmer's Toolkit

### Schedule - Part 1 - Week 01 - Aug 28 - Toolkit - Week 02 - Sep 04 - Data Structures - Week 03 - Sep 11 - Priority Queues - Week 04 - Sep 18 - Binary Search - Week 05 - Sep 25 - Greedy Approach - Week 06 - Oct 02 - Dynamic Programming - Week 07 - Oct 14 - Fall Break (no meeting)

### Schedule - Part 2 - Week 08 - Oct 16 - 2D Dynamic Programming - Week 09 - Oct 23 - DP Approaches - Week 10 - Oct 30 - Graphs - Week 11 - Nov 06 - ACM ICPC Regional - Week 12 - Nov 13 - Weighted Shortest Path - Week 13 - Nov 20 - Minimum Spanning Trees - Week 14 - Nov 26 - Thanksgiving Break (no meeting) - Week 15 - bye bye

# Today's Goals - Navigate the Kattis platform

# Today's Goals - Navigate the Kattis platform - Interpret problem statements

# Today's Goals - Navigate the Kattis platform - Interpret problem statements - Estimate algorithmic feasibility

# Today's Goals - Navigate the Kattis platform - Interpret problem statements - Estimate algorithmic feasibility - Implement robust and efficient I/O

# Today's Goals - Navigate the Kattis platform - Interpret problem statements - Estimate algorithmic feasibility - Implement robust and efficient I/O - Diagnose common judging verdicts

## What is Competitive Programming? - Solving puzzle-like problems under time constraints - Emphasis on: - problem-solving - algorithms - efficiency - ACM ICPC

## The Kattis Online Judge - Anatomy of a [problem](https://open.kattis.com/problems/hello): - Statement - Input/Output Specs - Time/Memory Limits - The Submission Process - Understanding Verdicts: - Accepted (AC) - Wrong Answer (WA) - Time Limit Exceeded (TLE) - Run Time Error (RTE)

## Python I/O for Speed - Standard I/O patterns: - reading `n` lines ([practice](https://open.kattis.com/problems/carrots)) - reading to EOF ([practice](https://open.kattis.com/problems/different)) - `input()` is a bottleneck when `n` is large - Fast I/O: ([practice](https://open.kattis.com/problems/cd)) - `sys.stdin.readline()` - `sys.stdout.write()` - When to use fast I/O?

## Time Complexity & Feasibility -- Intuitive Big-O -- `$ \mathcal{O}(N^2)$` vs. `$\mathcal{O}(N\log N)$`

## Time Complexity & Feasibility The `$ 10^8 $` Operations Rule Typical modern CPU can execute approximately `$ 10^8 $` operations per second.

## Time Complexity & Feasibility Python - CON - Slower constant factor - PRO - built-in features - common algorithms - large integer support