This is a curated list of algorithm thinking problems, focusing on those with minimal code complexity but requiring creative problem-solving. Problems marked with (!) are foundational examples, while (*) denote highly insightful problems that build problem-solving intuition. Updates will be made periodically as new problems are added.

P2804 Mysterious Number

Problem Analysis:

• For small constraints (n² feasible), compute prefix sums and brute-force all subarrays.
• For larger datasets (2e6 elements), an O(n log n) approach is required.
• Transform the array by subtracting the mean value m from each element, then compute prefix sums. A subarray has an average greater than m if its corresponding prefix sum difference is positive. This translates to counting the number of pairs (i,j) where j > i and prefix[j] > prefix[i] (similar to counting inversions).
• Add a zero at the start of the prefix sum array, then use a Fenwick Tree (Binary Indexed Tree) to count these valid pairs efficiently.

Orac and Medians (*)

Property-Focused Problem:

• If the sequence does not contain k, the answer is immediately "impossible".
• For n=2: The median of two elements is the smaller one, so at least one element must be ≥k.
• For n=3: The median is the second element when sorted. If there exist two adjacent elements both ≥k, or an element ≥k surrounded by two elements ≥k, we can transform the sequence to have k as the median.
• Generalization: The answer is posssible if there exists a pair of adjacent elements ≥k, or an element ≥k with at least one neighbor ≥k.
• Similar Problem: Given a sequence, find how many distinct values can be turned into the entire sequence by repeatedly replacing a subarray with its majority element. The solution relies on finding values that appear in at least two out of three consecutive positions.

XOR-gun (!)

Key Insight: Binary Digit Groups:

• The problem asks for the minimum number of adjacent XOR operations to break the non-decreasing order of the sequence.
• Split the sequence into groups where each group contains numbers with the same highest set bit. If any group has 3 or more elements, the answer is 2 (since we can XOR the first two to get a number smaller than the third, breaking the order).
• For groups with ≤2 elements each, we can brute-force all possible adjacent pairs across neighboring groups, as the total number of groups is at most 32 (for 32-bit integers), leading to an O(32²) check.

P8775 [Blue Bridge Cup 2022 Provincial A] Frog Crossing River

Binary Search + Interval Sum Check:

• Instead of simulating 2x frogs jumping x times, we can model it as 2x frogs each jumping once.
• Use binary search to determine the maximum possible distance d such that all frogs can cross. For a candidate d, check if every consecutive d-length interval in the river has a sum of heights ≥2x. This ensures there's always space for the frogs to land as they move forward.

P6608 [Code+#7] Mysterious Sequence

Cycle Detection + Binary Search Construction:

• Forward simulation: Traverse the sequence, setting a[i] to 0 if a[i] = i, then increment all previous elements by 1. This is computationally expensive for large k.
• Backward Simulation: Reverse the process: start from the final sequence (all zeros), and whenever a zero is found at position i, set a[i] to i and decrement all previous elements by 1. Observing cycles in this process reveals a pattern where each number i repeats every (i+1) steps.
• Binary Search Approach: Find the minimal sequence length such that applying n operations results in a valid sequence. Then construct the sequence using the cycle counts.

Rewritten Code:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
const ll SQRT_FACTOR = 1.7724566;

bool is_possible(ll target, ll candidate_len) {
    ll remaining = candidate_len + target;
    ll current_group = 1;
    while (remaining > 0) {
        remaining = remaining * current_group / (current_group + 1);
        current_group++;
    }
    return current_group - 1 <= candidate_len;
}

int main() {
    ll target_ops;
    cin >> target_ops;
    
    ll initial_guess = sqrt(target_ops) * SQRT_FACTOR;
    ll left = max(initial_guess - 100, 2LL);
    ll right = initial_guess + 100;
    
    while (left < right) {
        ll mid = (left + right) / 2;
        if (is_possible(target_ops, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    ll total_steps = target_ops + left;
    vector<ll> cycle_counts;
    ll current_group = 1;
    while (total_steps > 0) {
        ll prev = total_steps;
        total_steps = total_steps * current_group / (current_group + 1);
        cycle_counts.push_back(prev - total_steps);
        current_group++;
    }
    
    int seq_length = cycle_counts.size();
    vector<ll> original_seq(seq_length + 1);
    ll sum_cycles = 0;
    for (int i = seq_length; i >= 1; i--) {
        original_seq[i] = cycle_counts[i-1] * i - sum_cycles;
        sum_cycles += cycle_counts[i-1];
    }
    
    cout << seq_length << endl;
    for (int i = 1; i <= seq_length; i++) {
        cout << original_seq[i] << " ";
    }
    cout << endl;
    return 0;
}

P1758 [NOI2009] Pipe Balls

DP Transformation:

• To compute the sum of squares of the number of ways to collect balls from the pipe, we can model it as counting the number of pairs of identical sequences collected from two identical pipes. This reduces to a dynamic programming problem where dp[i][j] represents the number of ways to collect i balls from the first pipe and j balls from the second pipe such that the sequences are identical.

P8955 「VUSC」Card Tricks

Segment Tree + Scan Line Technique:

• Leverage the monotonicity of the OR operation (once a bit is set, it remains set). Use a segment tree to maintain the OR values over the time axis. For each operation, apply the OR value at the start time and reset (with 0) at the end time +1. For each card, binary search to find the earliest time when its OR value exceeds P.

Double Happiness

Number Theory:

• Fermat's Theorem on Sums of Two Squares: An odd prime p can be expressed as the sum of two squares if and only if p ≡ 1 mod 4. Additionally, 2 can be written as 1²+1². Composite numbers can be expressed as such if all their prime factors congruent to 3 mod 4 have even exponents.

Coloring Problems Series

Problem 1: Grid Row/Column Coloring:

• Given a grid, apply row and column coloring operations that overwrite existing colors. To compute the final color counts efficiently, process operations in reverse order. Mark rows and columns that have already been colored, and count the remaining uncolored cells for each operation.
• Example: ABC346E Paint

Problem 2: 1D Interval Coloring:

• For large n (1e7), use a union-find data structure or linked list to track uncolored intervals. Process operations in reverse, marking intervals as colored and skipping over already colored segments.
• Example: P2391 Snow Covered Fields

Problem 3: Mixed Coloring Modes:

• Combine two coloring modes: overwrite all cells, or stop at already colored cells. Process overwrite operations in reverse and non-overwrite operations in forward order, using linked lists to track uncolored cells.
• Example: P9715 「QFOI R1」Head

Code for Problem 3:

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 2e6 + 10;

struct Operation {
    int op, l, r, c, t;
};

struct LinkedList {
    int sum;
    bool vis[MAX_N];
    int nxt[MAX_N];
    
    void init(int size) {
        sum = 0;
        for (int i = 1; i <= size; i++) {
            vis[i] = false;
            nxt[i] = i + 1;
        }
        nxt[size] = 0;
    }
    
    void mark(int l, int r) {
        int prev = 0;
        for (int i = l; i != 0 && i <= r; ) {
            if (!vis[i]) {
                vis[i] = true;
                sum++;
            }
            int next_i = nxt[i];
            nxt[prev] = nxt[r];
            prev = i;
            i = next_i;
        }
    }
    
    int query(int l, int r) {
        int cnt = 0;
        for (int i = l; i != 0 && i <= r; i = nxt[i]) {
            if (vis[i]) cnt++;
        }
        return cnt;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    vector<Operation> ops(q);
    for (int i = 0; i < q; i++) {
        cin >> ops[i].op >> ops[i].l >> ops[i].r >> ops[i].c >> ops[i].t;
    }
    
    LinkedList tx, ty;
    tx.init(n);
    ty.init(m);
    vector<long long> ans(k + 1, 0);
    
    auto process = [&](const Operation& op) {
        if (op.op == 1) {
            int colored = tx.query(op.l, op.r);
            long long uncolored = (op.r - op.l + 1) - colored;
            ans[op.c] += uncolored * (m - ty.sum);
            tx.mark(op.l, op.r);
        } else {
            int colored = ty.query(op.l, op.r);
            long long uncolored = (op.r - op.l + 1) - colored;
            ans[op.c] += uncolored * (n - tx.sum);
            ty.mark(op.l, op.r);
        }
    };
    
    // Process overwrite operations in reverse
    for (int i = q - 1; i >= 0; i--) {
        if (ops[i].t) process(ops[i]);
    }
    
    // Process non-overwrite operations forward
    for (int i = 0; i < q; i++) {
        if (!ops[i].t) process(ops[i]);
    }
    
    for (int i = 1; i <= k; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    
    return 0;
}

P1315 [NOIP2011] Sightseeing Bus

Greedy Optimization:

• First, compute the initial departure times for each station when k=0. For each station, the departure time is the maximum between the arrival time of the bus and the latest arrival time of passengers at that station.
• For k>0, each acceleration reduces the travel time between two stations, which benefits all subsequent passengers until a station where passengers are waiting for the bus. At each step, choose the segment where acceleration will save the most total passenger time, and apply the acceleration until k is exhausted.

P4375 [USACO18OPEN] Out of Sorts G

Fenwick Tree for Counting:

• For the simplified problem (single bubble sort pass), the number of steps needed to sort is the maximum number of elements greater than a given element to its left.
• For the two-pass problem (forward and backward bubble sort), the required steps for each element is the maximum of the number of greater elements to the left and smaller elements to the right. Use coordinate compression and Fenwick Trees to compute these counts efficiently.

P10136 [USACO24JAN] Cowlendar S

(Additional problem to be upddated with detailed analysis)