Binary Search Methodologies

Integer binary search typically relies on partitioning a range [left, right] based on a predicate function. Two common partitions are used depending on whether the midpoint belongs to the left or right sub-interval.

// Partition: [left, pivot] | [pivot + 1, right]
int find_first_valid(int left, int right) {
    while (left < right) {
        int pivot = left + (right - left) / 2;
        if (predicate(pivot)) 
            right = pivot;
        else 
            left = pivot + 1;
    }
    return left;
}

// Partition: [left, pivot - 1] | [pivot, right]
int find_last_valid(int left, int right) {
    while (left < right) {
        int pivot = left + (right - left + 1) / 2;
        if (predicate(pivot)) 
            left = pivot;
        else 
            right = pivot - 1;
    }
    return left;
}

For floating-point ranges, exact equality is avoided. Instead, we iterate until the interval shrinks below a predefined epsilon threshold.

double find_float_value(double lower, double upper) {
    const double tolerance = 1e-7;
    while (upper - lower > tolerance) {
        double center = (lower + upper) / 2.0;
        if (predicate(center)) 
            upper = center;
        else 
            lower = center;
    }
    return lower;
}

Prefix Sum Acceleration

Prefix sums allow $O(1)$ range sum queries. A 1D prefix array P stores cumulative totals, where the sum between indices L and R equals P[R] - P[L-1].

const int MAX_N = 100010;
int arr[MAX_N];
int pref[MAX_N];

void build_prefix_sum(int n) {
    pref[0] = 0;
    for (int i = 1; i <= n; ++i) {
        pref[i] = pref[i - 1] + arr[i];
    }
}

int query_range(int L, int R) {
    return (R >= L) ? pref[R] - pref[L - 1] : pref[L] - pref[R - 1];
}

In two dimentions, the inclusion-exclusion principle extends this concept. The submatrix defined by top-left (x1, y1) and bottom-right (x2, y2) is calculated as:

const int MAX_C = 1010, MAX_R = 1010;
int mat[MAX_R][MAX_C];
int s_mat[MAX_R][MAX_C];

void build_2d_prefix(int rows, int cols) {
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            s_mat[i][j] = s_mat[i-1][j] + s_mat[i][j-1] - s_mat[i-1][j-1] + mat[i][j];
        }
    }
}

int query_2d_rect(int x1, int y1, int x2, int y2) {
    return s_mat[x2][y2] - s_mat[x1-1][y2] - s_mat[x2][y1-1] + s_mat[x1-1][y1-1];
}

Difference Array Updates

When frequent range addition operations are required, difference arrays provide an efficient solution. To add val to every element in [L, R], modify diff[L] += val and diff[R+1] -= val. The original array is recovered via a cumulative pass.

One-Dimensional Reconstruction

const int N = 100010;
int diff_arr[N];

void apply_update(int L, int R, int val) {
    diff_arr[L] += val;
    diff_arr[R + 1] -= val;
}

void restore_original(int n) {
    for (int i = 1; i <= n; ++i) {
        diff_arr[i] += diff_arr[i - 1];
        printf("%d ", diff_arr[i]);
    }
}

Two-Dimensional Block Modifications

Similar to 1D, 2D updates affect four corners to preserve the grid integrity:

const int SZ = 1010;
int diff_grid[SZ][SZ];

void apply_rect_update(int r1, int c1, int r2, int c2, int val) {
    diff_grid[r1][c1] += val;
    diff_grid[r1][c2 + 1] -= val;
    diff_grid[r2 + 1][c1] -= val;
    diff_grid[r2 + 1][c2 + 1] += val;
}

void reconstruct_2d_grid(int rows, int cols) {
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            diff_grid[i][j] += diff_grid[i-1][j] + diff_grid[i][j-1] - diff_grid[i-1][j-1];
            printf("%d ", diff_grid[i][j]);
        }
        puts("");
    }
}

Dual Pointer Optimization

The two-pointer technique efficiently reduces time complexity by maintaining a moving window or synchronizing iterations across sequences.

// Single sequence: Sliding window maintenance
for (int head = 0, tail = 0; head < n; ++head) {
    while (tail < head && invalid_condition(head, tail)) {
        tail++;
    }
    // Process valid window [tail, head]
}

// Dual sequence: Merging ordered streams
int i = 0, j = 0;
while (i < size_A && j < size_B) {
    if (compare(A[i], B[j]) <= 0) {
        process(A[i++]);
    } else {
        process(B[j++]);
    }
}

Disjoint Set Union (DSU) Structures

Path compression and union-by-rank/size optimize near-constant amortized lookup times.

Base Implementation

const int LIMIT = 100010;
int parent[LIMIT];

int locate_root(int node) {
    if (parent[node] != node)
        parent[node] = locate_root(parent[node]);
    return parent[node];
}

void merge_sets(int u, int v) {
    int root_u = locate_root(u);
    int root_v = locate_root(v);
    if (root_u != root_v)
        parent[root_u] = root_v;
}

Size-Weighted Variant

int dsu_parent[LIMIT];
int set_size[LIMIT];

void init_dsu_size(int total_nodes) {
    for (int i = 1; i <= total_nodes; ++i) {
        dsu_parent[i] = i;
        set_size[i] = 1;
    }
}

void union_by_size(int u, int v) {
    int root_u = locate_root(u);
    int root_v = locate_root(v);
    if (root_u != root_v) {
        if (set_size[root_u] < set_size[root_v])
            std::swap(root_u, root_v);
        dsu_parent[root_v] = root_u;
        set_size[root_u] += set_size[root_v];
    }
}

Distance-Aware Variant

Tracks offset distances from nodes to their respective roots.

int dist_dsu[LIMIT];

int find_with_dist(int node) {
    if (dist_dsu[node] == node) return node;
    int orig_parent = dist_dsu[node];
    int root = find_with_dist(orig_parent);
    current_dist[node] += current_dist[orig_parent]; // Note: requires auxiliary dist array
    dist_dsu[node] = root;
    return root;
}

(Note: In practice, a separate offset array is maintained alongside parent. The recursive traversal accumulates the path length before compressing.)

Hash Mapping Architectures

Chaining resolves collisions using linked lists, while open addressing probes sequentially for empty slots. String hashing leverages base-$P$ polynomial rolling hashes with natural modular arithmetic via unsigned long long overflow.

Chaining Implementation

const int HASH_MOD = 100003;
int h_val[HASH_MOD];
int e_data[HASH_MOD];
int next_ptr[HASH_MOD];
int idx_counter = 0;

void insert_into_chain(int key) {
    int bucket = (key % HASH_MOD + HASH_MOD) % HASH_MOD;
    e_data[idx_counter] = key;
    next_ptr[idx_counter] = h_val[bucket];
    h_val[bucket] = idx_counter++;
}

bool search_chain(int key) {
    int bucket = (key % HASH_MOD + HASH_MOD) % HASH_MOD;
    for (int curr = h_val[bucket]; curr != -1; curr = next_ptr[curr]) {
        if (e_data[curr] == key) return true;
    }
    return false;
}

Open Addressing Probe

const int OAD_SIZE = 200000;
int oad_table[OAD_SIZE];
const int NULL_VAL = 0x3f3f3f3f;

int probe_insert(int key) {
    int pos = (key % OAD_SIZE + OAD_SIZE) % OAD_SIZE;
    while (oad_table[pos] != NULL_VAL && oad_table[pos] != key) {
        pos++;
        if (pos == OAD_SIZE) pos = 0;
    }
    return pos;
}

Rolling String Hash

const int BASE = 131;
const int STR_LEN = 100010;
typedef unsigned long long ULL;
ULL str_hash[STR_LEN];
ULL power_base[STR_LEN];
char input_str[STR_LEN];

void init_string_hash(int len) {
    power_base[0] = 1;
    for (int i = 1; i <= len; ++i) {
        str_hash[i] = str_hash[i - 1] * BASE + input_str[i];
        power_base[i] = power_base[i - 1] * BASE;
    }
}

ULL extract_substring_hash(int l, int r) {
    return str_hash[r] - str_hash[l - 1] * power_base[r - l + 1];
}

Graph Traversal Fundamentals

Depth-First Search explores branches recursively, while Breadth-First Search processes levels iteratively using a queue.

const int VERTICES = 100010;
const int MAX_EDGES = 200010;
int head[V], nxt[MAX_EDGES], to[MAX_EDGES], wt[MAX_EDGES];
int edge_cnt = 0;
bool visited[V];

void add_directed_edge(int u, int v, int weight) {
    to[++edge_cnt] = v;
    wt[edge_cnt] = weight;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// Recursive DFS
void perform_dfs(int u) {
    visited[u] = true;
    for (int e = head[u]; e != -1; e = nxt[e]) {
        int v = to[e];
        if (!visited[v]) perform_dfs(v);
    }
}

// Iterative BFS
void perform_bfs(int start_node, int total_nodes) {
    std::queue<int> q;
    q.push(start_node);
    visited[start_node] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int e = head[curr]; e != -1; e = nxt[e]) {
            int next_node = to[e];
            if (!visited[next_node]) {
                visited[next_node] = true;
                q.push(next_node);
            }
        }
    }
}

Shortest Path Computations

SPFA (Queue-Optimized Bellman-Ford)

Suitable for sparse graphs with potentially negative weights. Includes negative cycle detection.

int dist_spfa[VERTICES];
bool in_queue[VERTICES];
int hop_count[VERTICES];

int execute_spfa(int source, int target) {
    std::memset(dist_spfa, 0x3f, sizeof(dist_spfa));
    dist_spfa[source] = 0;

    std::queue<int> q;
    q.push(source);
    in_queue[source] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        in_queue[curr] = false;

        for (int e = head[curr]; e != -1; e = nxt[e]) {
            int next_v = to[e];
            if (dist_spfa[next_v] > dist_spfa[curr] + wt[e]) {
                dist_spfa[next_v] = dist_spfa[curr] + wt[e];
                if (!in_queue[next_v]) {
                    q.push(next_v);
                    in_queue[next_v] = true;
                }
            }
        }
    }
    return (dist_spfa[target] > 1e9) ? -1 : dist_spfa[target];
}

bool detect_negative_cycle(int n) {
    std::queue<int> q;
    std::memset(hop_count, 0, sizeof(hop_count));
    for (int i = 1; i <= n; ++i) {
        q.push(i);
        in_queue[i] = true;
    }

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        in_queue[curr] = false;

        for (int e = head[curr]; e != -1; e = nxt[e]) {
            int next_v = to[e];
            if (dist_spfa[next_v] > dist_spfa[curr] + wt[e]) {
                dist_spfa[next_v] = dist_spfa[curr] + wt[e];
                hop_count[next_v] = hop_count[curr] + 1;
                if (hop_count[next_v] >= n) return true;
                if (!in_queue[next_v]) {
                    q.push(next_v);
                    in_queue[next_v] = true;
                }
            }
        }
    }
    return false;
}

Dijkstra (Priority Queue Optimized)

Guarantees optimal paths for non-negative edge weights.

using Pair = std::pair<int, int>; // {distance, vertex}
std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;

int run_dijkstra(int source, int target, int num_verts) {
    std::memset(dist_spfa, 0x3f, sizeof(int) * (num_verts + 1));
    dist_spfa[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        auto [curr_dist, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (dist_spfa[v] > curr_dist + wt[e]) {
                dist_spfa[v] = curr_dist + wt[e];
                pq.push({dist_spfa[v], v});
            }
        }
    }
    return (dist_spfa[target] > 1e9) ? -1 : dist_spfa[target];
}

Floyd-Warshall (All-Pairs Dynamic Programming)

Computes shortest paths between all vertex pairs in $O(V^3)$.

const int INF_D = 1e9;
int adj_matrix[V][V];

void init_floyd(int n) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            adj_matrix[i][j] = (i == j) ? 0 : INF_D;
}

void compute_all_pairs_shortest(int n) {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                adj_matrix[i][j] = std::min(adj_matrix[i][j], adj_matrix[i][k] + adj_matrix[k][j]);
}

Minimum Spanning Tree Construction

Kruskal's algorithm sorts edges by weight and greedily merges disjoint components.

struct EdgeInfo {
    int src, dest, cost;
    bool operator<(const EdgeInfo& other) const {
        return cost < other.cost;
    }
};

EdgeInfo edges[MAX_EDGES];
int mst_parent[MAX_V];

int find_root_kruskal(int node) {
    if (mst_parent[node] != node)
        mst_parent[node] = find_root_kruskal(mst_parent[node]);
    return mst_parent[node];
}

int execute_kruskal(int vertices_count, int edge_count) {
    std::sort(edges, edges + edge_count);
    for (int i = 1; i <= vertices_count; ++i) mst_parent[i] = i;

    int total_cost = 0;
    int edges_merged = 0;

    for (int i = 0; i < edge_count; ++i) {
        int u = find_root_kruskal(edges[i].src);
        int v = find_root_kruskal(edges[i].dest);
        if (u != v) {
            mst_parent[u] = v;
            total_cost += edges[i].cost;
            edges_merged++;
        }
    }
    return (edges_merged < vertices_count - 1) ? -1 : total_cost;
}

Calendar Mathematics Helpers

Accurate date validasion and leap year calculations are critical for temporal problems.

const int DAYS_PER_MONTH[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool is_calendar_leap(int year) {
    return (year % 400 == 0) || ((year % 4 == 0) && (year % 100 != 0));
}

int get_days_in_current_month(int month, int year) {
    if (month == 2)
        return is_calendar_leap(year) ? 29 : 28;
    return DAYS_PER_MONTH[month];
}

bool validate_calendar_date(int year, int month, int day) {
    if (month < 1 || month > 12) return false;
    if (day < 1) return false;
    int max_day = get_days_in_current_month(month, year);
    return day <= max_day;
}