Overview of Core Algorithmic Strategies

1. Brute Force Anumeration

Brute force involves systematicallly checking all possible candidates to find valid solutions. While straightforward, its time complexity is often O(n²) or higher, so input constraints must be carefully considered.

Example Problem: Counting Valid Triangles
Given N sticks with lengths D₁, D₂, ..., Dₙ, count the number of distinct triplets that can form a triangle (i.e., satisfy the triangle inequality).

Optimized Approach:
Sort the array first. For each pair (i, j) where i < j, only consider k > j. Early termination is possible: if D[i] + D[j] ≤ D[j+1], no larger k will work due to sorting.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> sticks(n);
    for (int i = 0; i < n; ++i) cin >> sticks[i];
    sort(sticks.begin(), sticks.end());

    long long count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (sticks[i] + sticks[j] <= sticks[j + 1]) continue;
            for (int k = j + 1; k < n; ++k) {
                if (sticks[i] + sticks[j] > sticks[k]) {
                    count++;
                } else {
                    break; // Further k won't satisfy due to sorted order
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}

2. Simulation

Simulation requires implementing the exact logic described in the problem statement. These problems often involve managing states and events over time.

Example Problem: Public Transport Fare Calculation
After taking a subway (cost p), a user receives a 45-minute voucher usable on buses with fare ≤ p. Vouchers are used in FIFO order. Compute total expenditure given a chronological list of rides.

Key Insight:
Maintain a queue of active vouchers. For each bus ride, scan from the earliest voucher onward to find the first valid one. Expired vouchers can be skipped using a sliding window pointer.

#include <bits/stdc++.h>
using namespace std;

struct Voucher {
    int price;
    int timestamp;
    bool used;
};

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<Voucher> vouchers;
    long long totalCost = 0;
    int earliestValid = 0;

    for (int i = 0; i < n; ++i) {
        int type, price, time;
        cin >> type >> price >> time;

        if (type == 0) { // Subway
            totalCost += price;
            vouchers.push_back({price, time, false});
        } else { // Bus
            bool usedVoucher = false;
            for (int j = earliestValid; j < vouchers.size(); ++j) {
                if (time - vouchers[j].timestamp > 45) {
                    earliestValid = j + 1;
                    continue;
                }
                if (!vouchers[j].used && vouchers[j].price >= price) {
                    vouchers[j].used = true;
                    usedVoucher = true;
                    break;
                }
            }
            if (!usedVoucher) totalCost += price;
        }
    }
    cout << totalCost << endl;
    return 0;
}

3. Prefix Sum and Difference Array

Prefix Sum: Precompute cumulative sums to answer range sum queries in O(1).
Difference Array: Apply range updates (add/subtract a value over an interval) in O(1), then reconstruct the final array via prefix sum.

These techniques are inverses: applying a difference array followed by a prefix sum recovers the original transformation.