Greedy orderings and game states.

A greedy rule needs more than an appealing local choice. It needs an argument that accepting the choice cannot destroy every optimal solution. Game-state problems take a different route: identify losing states, then combine independent components with XOR.

Prove the greedy choice

Use one of three arguments before implementing:

• Exchange. Take an optimal solution that differs from the greedy choice and swap its first differing choice with the greedy one without making the result worse.
• Stays ahead. Show that after each step, the greedy partial solution has at least as much remaining capacity, reach, value, or progress as any competing partial solution.
• Cut or structural property. Show that a locally lightest edge or independent-set choice is safe for every solution crossing the same boundary.

If the choice consumes a resource in a way that cannot be exchanged or ordered monotonically, retain multiple states with dynamic programming. Coin systems are a standard warning: choosing the largest coin first is optimal for some denominations and wrong for others.

Interval scheduling by end time

To retain the maximum number of non-overlapping intervals, choose the available interval that ends earliest. If an optimal solution first chooses a later-ending interval, replace it with the greedy interval. Every interval that fit after the original still fits after an interval ending no later, so the number selected cannot decrease.

erase_overlapping.cppint erase_overlapping(
    std::vector<std::pair<int, int>> intervals
) {
    std::sort(intervals.begin(), intervals.end(),
        [](const auto& left, const auto& right) {
            return left.second < right.second;
        });

    int removed = 0;
    int previous_end = 0;
    bool have_previous = false;
    for (const auto& [start, end] : intervals) {
        if (have_previous && start < previous_end) ++removed;
        else {
            have_previous = true;
            previous_end = end;
        }
    }
    return removed;
}

Be explicit about whether touching endpoints overlap. The code treats [1,2] followed by [2,3] as compatible. Closed intervals representing occupied integer points may require a different condition.

Deadline scheduling with a regret heap

Process jobs in deadline order and tentatively accept each duration. When total time exceeds the current deadline, remove the longest accepted duration. That replacement preserves the number of accepted jobs while minimizing their total time, leaving at least as much room for every future deadline.

schedule_course_count.cppint schedule_course_count(
    std::vector<std::pair<int, int>> courses // {duration, deadline}
) {
    std::sort(courses.begin(), courses.end(),
        [](const auto& left, const auto& right) {
            return left.second < right.second;
        });

    std::priority_queue<int> durations;
    int elapsed = 0;
    for (const auto& [duration, deadline] : courses) {
        elapsed += duration;
        durations.push(duration);
        if (elapsed > deadline) {
            elapsed -= durations.top();
            durations.pop();
        }
    }
    return static_cast<int>(durations.size());
}

This pattern appears whenever choices can be tentatively accepted and a later constraint violation can be repaired by discarding the most resource-intensive accepted choice. The heap stores regret candidates, not future tasks.

The comparator is the algorithm

Largest Number cannot sort numeric strings lexicographically: "3" must precede "30" because "330" > "303". Compare the two possible concatenation orders directly.

largest_concatenated_number.cppstd::string largest_concatenated_number(
    std::span<const int> values
) {
    std::vector<std::string> parts;
    for (const int value : values)
        parts.push_back(std::to_string(value));

    std::sort(parts.begin(), parts.end(),
        [](const auto& left, const auto& right) {
            return left + right > right + left;
        });
    if (parts.empty() || parts.front() == "0") return "0";
    return std::accumulate(parts.begin(), parts.end(), std::string{});
}

A std::sort comparator must define a strict weak ordering: it must return false for equal values, remain asymmetric, and induce transitive equivalence classes. Using <=, random tie-breaking, or mutable external state gives undefined behavior because the sorting algorithm assumes that contract.

Adjacent swaps and inversion counting

One adjacent swap changes the inversion count by exactly one. Therefore the minimum number of adjacent swaps needed to sort equals the number of inversions. During merge sort, when a right-half value precedes the current left-half value, it forms an inversion with every unmerged value remaining in the left half.

inversion_merge.cppwhile (left < middle || right < end) {
    if (right == end ||
        (left < middle && values[left] <= values[right])) {
        scratch[output++] = values[left++];
    } else {
        scratch[output++] = values[right++];
        inversions += static_cast<std::int64_t>(middle - left);
    }
}

The full algorithm recursively counts the two halves, counts cross-pairs during the merge, and copies the sorted range back. A Fenwick tree over compressed values gives the same O(n log n) bound and extends naturally to streaming frequency queries.

Arbitrary swaps and permutation cycles

Arbitrary swaps are a different problem. After sorting {value, original_index} pairs, the mapping from sorted positions to original positions is a permutation. A cycle of length L needs exactly L - 1 swaps.

minimum_arbitrary_swaps.cppint minimum_arbitrary_swaps(std::span<const int> distinct_values) {
    const std::size_t n = distinct_values.size();
    std::vector<std::pair<int, std::size_t>> ordered(n);
    for (std::size_t i = 0; i < n; ++i)
        ordered[i] = {distinct_values[i], i};
    std::sort(ordered.begin(), ordered.end());

    std::vector<bool> visited(n, false);
    int swaps = 0;
    for (std::size_t start = 0; start < n; ++start) {
        if (visited[start] || ordered[start].second == start) continue;
        std::size_t length = 0;
        for (std::size_t node = start; !visited[node];
             node = ordered[node].second) {
            visited[node] = true;
            ++length;
        }
        swaps += static_cast<int>(length - 1);
    }
    return swaps;
}

This version requires distinct values. With duplicates, several target permutations are possible and a naive stable assignment need not minimize swaps. Read “adjacent swaps” versus “swap any two” before choosing between inversions and cycles.

Nim

A normal Nim position is losing exactly when the XOR of pile sizes is zero. From a zero-XOR position, every move creates nonzero XOR. From a nonzero-XOR position, the highest set bit of the total XOR identifies a pile that can be reduced to make the XOR zero.

nim.cppbool nim_first_player_wins(std::span<const int> piles) {
    int combined = 0;
    for (const int pile : piles) combined ^= pile;
    return combined != 0;
}

Misère Nim changes only the all-ones case: if every pile has size one, the first player wins when the number of piles is even. When any pile is larger than one, the ordinary XOR rule applies.

Sprague–Grundy values

For an impartial normal-play game, define the Grundy value of a state as the minimum excluded nonnegative value among its successors. Terminal states have value zero. Independent components combine by XOR, exactly like Nim piles. The whole state is losing when the XOR is zero.

subtraction_grundy.cppstd::vector<int> subtraction_grundy(
    std::size_t maximum,
    std::span<const int> moves
) {
    std::vector<int> grundy(maximum + 1, 0);
    for (std::size_t state = 1; state <= maximum; ++state) {
        std::unordered_set<int> reachable;
        for (const int move : moves)
            if (move >= 0 && static_cast<std::size_t>(move) <= state)
                reachable.insert(
                    grundy[state - static_cast<std::size_t>(move)]
                );
        int mex = 0;
        while (reachable.contains(mex)) ++mex;
        grundy[state] = mex;
    }
    return grundy;
}

Computing small states often reveals a periodic sequence, but the period still needs justification before extrapolating to huge inputs. Sprague–Grundy applies only to impartial games where both players have the same moves and normal play makes the player with no move lose.

Constructive algorithms

A constructive problem asks for any object satisfying constraints. Work backward from the verifier: list exactly what it checks, choose a simple family of outputs, and prove that the construction satisfies each condition. Parity, sorted pairing, cycles, and repeated blocks are common building blocks.

• If adjacent relations matter, try alternating low/high values or arranging values by parity.
• If every vertex needs a fixed degree, start from a cycle or regular circulant graph.
• If the output is a permutation, use position mappings and cycles rather than repeated searching.
• If n is huge, compute small valid outputs, identify which boundary conditions repeat, then prove the block composition.
• Validate the construction with a separate checker in tests. Do not test only one printed example.

Final map