Want to create interactive content? It’s easy in Genially!
Competitive Programming
Aaron Liu
Created on March 11, 2025
Start designing with a free template
Discover more than 1500 professional designs like these:
Transcript
Competitive Programming
A guide and introduction to the world of programming competitively
Let's go!
Introduction
Competitive Programming is a mind sport where participants seek to analyze and solve a series of problems as fast and efficiently as possible. The problems heavily utilize algorithms, data structures, math, and problem solving. This course serves to introduce the user to the world of competitive programming step by step.
Start course
Index
Evaluation
Objectives
Certificate
Modules
Survey
Activities
Objectives
- Learn the background of competitive programming
- Understand programming languages in the context of competitive programming
- Learn basic Time + Space Complexities
- Cover common data structures and algorithms
- Get hands on experience solving some common programming problems
The Modern Era
Rise of Programming
The Beginning
There are now numerous competitions hosted across multiple platforms hosting thousands of contestants at a time. The IOI becomes a popular contest for high school students, influencing the next generation.
With the rise of the internet, online competitions became easier and programming became more accessible. Online judges and competitions like Google Code Jam and Facebook Hacker Cup became popular.
The oldest programming competition can be traced back to 1970 with the International Collegiate Programming Contest (ICPC) at Texas A&M University hosting only 5 colleges
Competitive programming has had significant impact and contributions on the technology industry. It is often used as a talent indentification tool to hire individuals. Many techniques utilized in the competitions such as bit manipulations and number theory optimizations have influenced real-world applications.
Most importantly, competitive programming enhances a programmers ability to think through fundamental computer science adjacent problems. As a result, many schools such as MIT and Stanford has integrated competitive programming into their curriculum.
Modules
Briefly showcase some basic algorithms and common data structures
Common Techniques
Analyze competitive problems and their time/space constraints
Time/Space Complexities
Picking your first language and commonly used programming setups
Getting Started
What Language to use?
The three most commonly supported languages for competitive programming are C/C++, Python, and Java. The most common language is C/C++. While difficult to learn and pick up especially with no coding experience, it is an incredibly efficient language. On the other hand, python is incredibly fast to write and easy to pickup. However, it could take significantly longer to finish executing, making some of the most difficult competitive programming problems impossible to solve. For someone starting out, Python is a great language to learn.
VSCode is a highly recommended environment not only for competitive programming, but for most other coding activities. It is impressively lightweight and quick, and hosts numerous user-created extensions allowing you to customize. Sublime Text is another great choice, it is even more efficient and lighter than VSCode, however, it lacks internal debugging tools. VIM is an extremely popular choice due to being extremely fast to use and code in due to being keyboard driven. However, steep learning curve. Dev-C++ is provides a simple interface and easy for quick setups. However, it is old and lacks the modern feel.
Text Editors and IDEs
The preference of choice for most competitive programmers are light-weight, fast, and efficient text editors or integrated development environments that allow for quick debugging.
Module 2. Time/Space Complexity
In competitive programming, your solution needs to execute within a specified time constraint, usually a couple of seconds. It also needs to use less than a specified amount of memory. As a result, it becomes crucial to understand how to measure the speed and memory usage of your algorithm. By having a mastery of this concept, we can narrow down which types of algorithms can run in time and ultimately giving us a huge hint to what the problem is likely testing.
What is it?
Time/Space complexity is a concept difficult to understand at first glance. This video is to help your understand, and can be watched multiple times if some parts are confusing.
Time complexity Generalized
As the chart to the left indicates, certain time complexities are better than others, but that doesn't mean you should always target O(logn) or O(1) algorithms. Some programming problems are designed to be solved in O(n^2) or worse, and you'll find this to be common. Some may even be impossible to solve in faster complexities. The constraints indicated in the problem statements only serve to showcase the least efficient time complexity which is usually what the problem is asking for.
Complexity in Comp Programming
n = 10^5
10^9
Is the number that can utilize an O(n) algorithm and execute successfully.
Is the number of operations that will run in a second on most competitive programming platforms
n = 10
n = 10^3
Is small enough that can likey be brute forced by almost every algorithm known to man.
Is the number that can utilize an O(n^2) algorithm and execute successfully
Module 3. Common Techniques
In the short history of competitive programming, many common techniques from data structures to mathemtical numerical analysis have developed in order to solve problems and categorize them. Some of the more famous techniques are prefix-sum, sorting, and DFS/BFS. Now, you don't need to understand these techniques in this course since they can be their own separate course, but it is important to recognize that these are crucial for success in competitive programming.
Data structures are incredibly important to aid in the efficiency of your algorithm. It is like your toolbox at your disposal to build whatever creation you would like. Without a good understanding of data structures and the corresponding time complexities for each operation, it becomes hard to build any good code that will run in efficient time. It also will help prevent any mistakes from accidentally increasing your time complexity unwittingly. As a result, it is recommended to spend some time to learn some basic data structures. One of the most fundamental structures is the array.
Array
An array is a linear structure that holds elements of a certain size of a contiguous range of memory. Access to each element is efficient in O(1). Below is a link to a data structure visualization tool created by GT students for a better understanding of data structures.
+ csvistool
Example: Binary Search to find a number in a sorted list of 10^9 numbers.- Brute-force approach -> O(n) = 10^9 operations- Binary Search -> O(log(n)) = 20 operationsAs the example indicates, binary seach as able to signifcantly reducing our search time which is crucial for a lot of algorithms. Versatility is another strong point of algorithms. One algorithm could be utilized in multiple situations or problems. Example: Dijkstra’s Algorithm - famous shortest path graph algorithm- Navigation Apps (google maps)- Network routing- Game AI
Algorithms is the heart of your programming problem.
Many problems can be solved with a brute force solution, however, it just takes time... sometimes more than the existence of the universe. Thus, algorithms are designed to notice patterns or areas of redundant computations.
Practice makes perfect! Here is another problem which might need some data structure help.
Activity 2: Distinct Numbers
Here is a problem from codeforces that the most amount of people have solved. It should be a good introduction to competitive programming.
Activity 1: Watermelon
Evaluation
Here, we will test on the knowledge you have learned and gained throughout this course. Good luck and feel free to try as many times as you want!
1/5
2/5
3/5
4/5
5/5
YIPEE!
Congratulations!
Certificateof achievement
Congradulations on making it this far, and I hope you find some level of enjoyment in the field of competitive programming!
March, 2025