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!