CPToolkit

Personal Competitve Programming Toolkit - used for Codeforces and other occasions.

Algorithms

• longest_common_subsequence.cpp: finds the Longest Common Subsequence (LCS) using DP.
• longest_increasing_subsequence.cpp: finds the Longest Increasing Subsequence (LIS) using binary search.
• max_subarray_sum.cpp: finds the maximum subarray sum using Kadane’s Algorithm.

Divide and Conquer

• bigint_mul.cpp: performs large integer multiplication using D&C.
• count_inversions.cpp: finds the number of inversions in an array using D&C.
• mergesort.cpp: standard Merge Sort implementation.

Dynamic Programming

• max_cons_elements.cpp: finds the maximum sum of array elements with at most n consecutive elements.
• rod_cutting.cpp: finds the maximize sum from cutting a rod into pieces (rod cutting problem).

Bitmask DP

• count_tilings.cpp: count the number of ways to fill an n * m grid using 1 * 2 and 2 * 1 tiles using bitmask DP.

Graphs

• bfs.cpp: standard Breadth First Search (BFS) traversal.
• dfs.cpp: standard Depth First Search (DFS) traversal.
• topological_sort.cpp: performs Topological Sorting on a DAG.

Minimum Spanning Tree

• kruskal.cpp: finds Minimum Spanning Tree using Kruskal’s Algorithm.

Range Queries

• segment_tree_max.cpp: implements Segment Tree for range maximum queries.
• segment_tree_min.cpp: implements Segment Tree for range minimum queries.
• segment_tree_sum.cpp: implements Segment Tree for range sum queries.
• segment_tree_recursive.cpp: implements Segment Tree using recursive approach.

Shortest Path

• dijkstra.cpp: finds shortest paths using Dijkstra’s Algorithm.
• dijkstra_path.cpp: finds shortest paths using Dijkstra’s Algorithm with path reconstruction.
• bellman_ford_negative.cpp: detects negative cycles using Bellman-Ford's algorithm.
• bellman_ford.cpp: finds shortest paths using Bellman-Ford algorithm.
• floyd_warshall.cpp: finds shortest paths using Floyd-Warshall's Algorithm.
• shortest_xor_path.cpp: finds the shortest XOR path on a graph.

Tools

• binpow.cpp: finds a^n using Binary Exponentiation