Competitive programming demands a solid grasp of algorithms to solve complex problems efficiently. This article explores key algorithms frequently used in contests, their applications, and practical code snippets to help programmers elevate their problem-solving skills.
1. Sorting and Searching Algorithms
Sorting is foundational in optimizing data processing. Quick Sort and Merge Sort remain staples due to their O(n log n) average-case performance. For example, Merge Sort’s divide-and-conquer approach ensures stability:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
L, R = arr[:mid], arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
Binary search is another critical technique for O(log n) searches in sorted arrays. It’s often adapted for solving optimization problems, such as finding the minimum valid value in a monotonic function.
2. Graph Algorithms
Graph traversal methods like Breadth-First Search (BFS) and Depth-First Search (DFS) underpin solutions for connectivity and shortest-path challenges. BFS, using a queue, efficiently finds the shortest path in unweighted graphs:
void bfs(int start, vector<vector<int>>& graph) {
queue<int> q;
vector<bool> visited(graph.size(), false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
For weighted graphs, Dijkstra’s Algorithm with a priority queue solves single-source shortest paths efficiently. Advanced contestants also leverage Floyd-Warshall for all-pair shortest paths.
3. Dynamic Programming (DP)
DP breaks problems into overlapping subproblems. A classic example is the Knapsack Problem, where optimal substructure is exploited:
def knapsack(values, weights, capacity):
n = len(values)
dp = [[0] * (capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(1, capacity+1):
if weights[i-1] > w:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1
