COMPETITIVE PROGRAMMING IN PYTHON HANDBOOK 1 and 2
Certainly! Below is a concise handbook that covers frequently used algorithms and data structures in
competitive programming, with explanations and Python implementations.
# Competitive Programming Handbook
## Table of Contents
1. Introduction
2. Data Structures
- Arrays
- Linked Lists
- Stacks
- Queues
- Trees
- Graphs
- Hash Tables
3. Algorithms
- Sorting Algorithms
- Searching Algorithms
- Dynamic Programming
- Greedy Algorithms
- Graph Algorithms
- String Algorithms
4. Conclusion
---
## 1. Introduction
Competitive programming requires a solid understanding of algorithms and data structures to solve
problems efficiently. This handbook provides an overview of the most commonly used structures and
algorithms, along with Python implementations.
---
## 2. Data Structures
### Arrays
A collection of elements identified by index. Used for storing data in contiguous memory locations.
**Python Example:**
```python
arr = [1, 2, 3, 4, 5]
print(arr[2]) # Output: 3
```
### Linked Lists
A data structure consisting of nodes, where each node contains data and a reference to the next node.
**Python Example:**
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
```
### Stacks
A collection of elements that follows Last In First Out (LIFO) principle. Supports `push` and `pop`
operations.
**Python Example:**
```python
stack = []
stack.append(1)
stack.append(2)
print(stack.pop()) # Output: 2
```
### Queues
A collection of elements that follows First In First Out (FIFO) principle. Supports `enqueue` and
`dequeue` operations.
**Python Example:**
```python
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
print(queue.popleft()) # Output: 1
```
### Trees
A hierarchical data structure with nodes connected by edges. Each tree has a root and can have children.
**Binary Tree Node Example:**
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
```
### Graphs
A collection of nodes connected by edges. Can be directed or undirected.
**Adjacency List Example:**
```python
graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
```
### Hash Tables
A data structure that maps keys to values for efficient lookups, insertions, and deletions.
**Python Example:**
```python
hash_table = {}
hash_table['key'] = 'value'
print(hash_table['key']) # Output: value
```
---
## 3. Algorithms
### Sorting Algorithms
1. **Bubble Sort**: Repeatedly swap adjacent elements if they are in the wrong order.
2. **Quick Sort**: Divide and conquer algorithm selecting a 'pivot'.
3. **Merge Sort**: Divide the array into halves, sort and merge.
**Python Example (Merge Sort):**
```python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i=j=k=0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# Example usage:
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print(arr) # Output: [3, 9, 10, 27, 38, 43, 82]
```
### Searching Algorithms
1. **Linear Search**: Check each element until the target is found.
2. **Binary Search**: Efficiently find an item in a sorted array.
**Python Example (Binary Search):**
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example usage:
arr = [1, 2, 3, 4, 5]
print(binary_search(arr, 3)) # Output: 2
```
### Dynamic Programming
A method for solving complex problems by breaking them down into simpler subproblems, storing
results to avoid recomputation.
**Fibonacci Sequence Example:**
```python
def fibonacci(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Example usage:
print(fibonacci(10)) # Output: 55
```
### Greedy Algorithms
A method for solving problems by making a sequence of choices, each of which looks best at the
moment.
**Activity Selection Example:**
```python
def activity_selection(start, finish):
n = len(start)
activities = sorted(zip(start, finish), key=lambda x: x[1])
count = 1
last_finish_time = activities[0][1]
for i in range(1, n):
if activities[i][0] >= last_finish_time:
count += 1
last_finish_time = activities[i][1]
return count
# Example usage:
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
print(activity_selection(start, finish)) # Output: 4
```
### Graph Algorithms
1. **Depth First Search (DFS)**: Traverses the graph by exploring as far as possible along each branch.
2. **Breadth First Search (BFS)**: Explores all neighbors at the present depth prior to moving on to
nodes at the next depth level.
3. **Dijkstra’s Algorithm**: Finds the shortest path from a source to all vertices in a weighted graph.
**Python Example (BFS):**
```python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Example usage:
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0],
3: [1],
4: [1]
bfs(graph, 0) # Output: 0 1 2 3 4
```
### String Algorithms
1. **KMP Algorithm**: Efficient string searching algorithm.
2. **Rabin-Karp Algorithm**: Uses hashing for searching.
**Python Example (KMP):**
```python
def kmp_pattern_search(text, pattern):
lps = [0] * len(pattern)
j = 0 # length of previous longest prefix suffix
compute_lps_array(pattern, lps)
i = 0 # index for text
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
print(f"Pattern found at index {i - j}")
j = lps[j - 1]
elif i < len(text) and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
def compute_lps_array(pattern, lps):
length = 0
i=1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
# Example usage:
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_pattern_search(text, pattern) # Output: Pattern found at index 10
```
---
## 4. Conclusion
This handbook provides a solid foundation for understanding the data structures and algorithms
commonly used in competitive programming. Mastering these concepts will significantly improve your
problem-solving skills and performance in contests.
Practice implementing these algorithms and structures to build your proficiency!
Feel free to expand upon this handbook with more advanced topics or additional algorithms based on
your needs!
Great! Here’s a more detailed version of the competitive programming handbook, expanding on the
previous sections and including more advanced topics and algorithms.
# Competitive Programming Handbook
## Table of Contents
1. Introduction
2. Data Structures
- Arrays
- Linked Lists
- Stacks
- Queues
- Trees
- Binary Trees
- Binary Search Trees
- Heaps
- Segment Trees
- Fenwick Trees (Binary Indexed Trees)
- Graphs
- Hash Tables
3. Algorithms
- Sorting Algorithms
- Searching Algorithms
- Dynamic Programming
- Greedy Algorithms
- Graph Algorithms
- String Algorithms
- Number Theory
- Combinatorial Algorithms
4. Conclusion
---
## 1. Introduction
Competitive programming is a mental sport that involves solving algorithmic and mathematical problems
within a limited time frame. This handbook aims to equip you with the essential data structures and
algorithms frequently encountered in contests.
---
## 2. Data Structures
### Arrays
- **Definition**: A collection of elements stored at contiguous memory locations.
- **Time Complexity**: Access: O(1), Search: O(n), Insert/Delete: O(n).
**Example**:
```python
arr = [1, 2, 3, 4, 5]
print(arr[2]) # Output: 3
```
### Linked Lists
- **Definition**: A linear data structure where elements are stored in nodes, with each node containing
a reference to the next.
- **Types**: Singly Linked List, Doubly Linked List, Circular Linked List.
**Example**:
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, value):
new_node = Node(value)
if not self.head:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
```
### Stacks
- **Definition**: A collection of elements with Last In First Out (LIFO) access.
- **Operations**: Push, Pop, Peek.
**Example**:
```python
stack = []
stack.append(1)
stack.append(2)
print(stack.pop()) # Output: 2
```
### Queues
- **Definition**: A collection of elements with First In First Out (FIFO) access.
- **Operations**: Enqueue, Dequeue, Peek.
**Example**:
```python
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
print(queue.popleft()) # Output: 1
```
### Trees
#### Binary Trees
- **Definition**: A tree where each node has at most two children.
**Example**:
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
```
#### Binary Search Trees (BST)
- **Definition**: A binary tree where for each node, the left child’s value is less, and the right child’s
value is greater.
**Insertion Example**:
```python
class BST:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = TreeNode(value)
else:
self._insert_recursive(self.root, value)
def _insert_recursive(self, node, value):
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
else:
self._insert_recursive(node.left, value)
else:
if node.right is None:
node.right = TreeNode(value)
else:
self._insert_recursive(node.right, value)
```
#### Heaps
- **Definition**: A complete binary tree that maintains the heap property (max-heap or min-heap).
- **Time Complexity**: Insert: O(log n), Extract: O(log n).
**Example (Min-Heap)**:
```python
import heapq
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
print(heapq.heappop(min_heap)) # Output: 3
```
#### Segment Trees
- **Definition**: A tree used for storing intervals or segments, allowing efficient range queries and
updates.
**Example** (Range Sum Query):
```python
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (2 * self.n)
for i in range(self.n):
self.tree[self.n + i] = data[i]
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]
def update(self, idx, value):
idx += self.n
self.tree[idx] = value
while idx > 1:
idx >>= 1
self.tree[idx] = self.tree[idx << 1] + self.tree[idx << 1 | 1]
def query(self, left, right):
result = 0
left += self.n
right += self.n
while left < right:
if left & 1:
result += self.tree[left]
left += 1
if right & 1:
right -= 1
result += self.tree[right]
left >>= 1
right >>= 1
return result
# Example usage:
data = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(data)
print(seg_tree.query(1, 4)) # Output: 15
```
#### Fenwick Trees (Binary Indexed Trees)
- **Definition**: A data structure that provides efficient methods for cumulative frequency tables and
point updates.
**Example**:
```python
class FenwickTree:
def __init__(self, size):
self.size = size
self.tree = [0] * (size + 1)
def update(self, index, delta):
while index <= self.size:
self.tree[index] += delta
index += index & -index
def query(self, index):
sum = 0
while index > 0:
sum += self.tree[index]
index -= index & -index
return sum
# Example usage:
fenwick = FenwickTree(10)
fenwick.update(1, 5)
fenwick.update(2, 3)
print(fenwick.query(2)) # Output: 8
```
### Graphs
- **Definition**: A collection of vertices connected by edges. Can be directed or undirected.
#### Representations:
1. **Adjacency List**:
```python
graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
```
2. **Adjacency Matrix**:
```python
n=4
adj_matrix = [[0] * n for _ in range(n)]
adj_matrix[0][1] = 1
adj_matrix[0][2] = 1
```
---
## 3. Algorithms
### Sorting Algorithms
1. **Bubble Sort**: O(n²) complexity.
2. **Quick Sort**: Average O(n log n), worst O(n²).
3. **Merge Sort**: O(n log n).
4. **Heap Sort**: O(n log n).
**Example (Quick Sort)**:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage:
arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr)) # Output: [1, 1, 2, 3, 6, 8, 10]
```
### Searching Algorithms
1. **Linear Search**: O(n).
2. **Binary Search**: O(log n), requires sorted array.
**Example (Binary Search)**:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example usage:
arr = [1, 2, 3, 4, 5]
print(binary_search(arr, 3)) # Output: 2
```
### Dynamic Programming
- **Definition**: A method to solve problems by breaking them into simpler subproblems and storing
their solutions.
**Fibonacci Example**:
```python
def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n
+ 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Example usage:
print(fibonacci(10)) # Output: 55
```
### Greedy Algorithms
- **Definition**: A method for solving optimization problems by selecting the best option at each step.
**Example (Activity Selection)**:
```python
def activity_selection(start, finish):
activities = sorted(zip(start, finish), key=lambda x: x[1])
count = 1
last_finish_time = activities[0][1]
for i in range(1, len(activities)):
if activities[i][0] >= last_finish_time:
count += 1
last_finish_time = activities[i][1]
return count
# Example usage:
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
print(activity_selection(start, finish)) # Output: 4
```
### Graph Algorithms
1. **Depth First Search (DFS)**:
```python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
# Example usage:
graph = {
0: [1, 2],
1: [0, 3],
2: [0],
3: [1]
print(dfs(graph, 0)) # Output: {0, 1, 2, 3}
```
2. **Breadth First Search (BFS)**:
```python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Example usage:
bfs(graph, 0) # Output: 0 1 2 3
```
3. **Dijkstra’s Algorithm**:
```python
import heapq
def dijkstra(graph, start):
queue = []
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
heapq.heappush(queue, (0, start))
while queue:
current_distance, current_vertex = heapq.heappop(queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# Example usage:
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
print(dijkstra(graph, 'A')) # Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
```
### String Algorithms
1. **KMP Algorithm**: Efficient substring search.
2. **Rabin-Karp Algorithm**: Uses hashing for searching.
**Example (KMP)**:
```python
def kmp_pattern_search(text, pattern):
lps = compute_lps(pattern)
i = j = 0 # index for text and pattern
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
print(f"Pattern found at index {i - j}")
j = lps[j - 1]
elif i < len(text) and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
def compute_lps(pattern):
lps = [0] * len(pattern)
length = 0
i=1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
# Example usage:
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_pattern_search(text, pattern) # Output: Pattern found at index 10
```
### Number Theory
1. **GCD (Greatest Common Divisor)**:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
# Example usage:
print(gcd(48, 18)) # Output: 6
```
2. **Prime Factorization**:
```python
def prime_factors(n):
factors = []
for i in range(2, int(n**0.5) + 1):
while n % i == 0:
factors.append(i)
n //= i
if n > 1:
factors.append(n)
return factors
# Example usage:
print(prime_factors(100)) # Output: [2, 2, 5, 5]
```
### Combinatorial Algorithms
1. **Permutations**:
```python
from itertools import permutations
def get_permutations(elements):
return list(permutations(elements))
# Example usage:
print(get_permutations([1, 2, 3])) # Output: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
```
2. **Combinations**:
```python
from itertools import combinations
def get_combinations(elements, r):
return list(combinations(elements, r))
# Example usage:
print(get_combinations([1, 2, 3, 4], 2)) # Output: [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
```
---
## 4. Conclusion
This expanded handbook provides a comprehensive overview of essential data structures and algorithms
commonly used in competitive programming. Mastery of these topics will greatly enhance your
problem-solving abilities and performance in coding contests. Practice implementing these concepts and
tackling a variety of problems to solidify your understanding!
Feel free to adapt or expand upon this handbook based on your own experiences and needs! If you need
further details or specific topics, let me know!
