Chapter 5: Simulation & Brute Force

Simplicity wins; an unpolished blade can still be sharp.

When the input size is small or the rules are highly specific, do not overthink dynamic programming or graphs. Follow the problem statement literally, or try every possibility.

5.1 Simulation: The Art of Translation

Simulation means translating the problem statement into code step by step.

These problems rarely require fancy theory; the challenges lie in:

1. Complex rules: board games, calendar math, falling blocks.
2. Hidden pitfalls: brutal edge cases such as February 29 or carry operations.

5.1.1 Three Commandments of Simulation

1. Don’t rush to code: simulate the process on paper, and ensure you understand every rule.
2. Modularize: don’t stuff everything into main.
   • Need to compute leap years? Write bool isLeap(int year).
   • Distance calculation? Write double dist(Point a, Point b).
   • This keeps debugging manageable.
3. Stay calm: simulation solutions easily exceed 100 lines. One mistake hurts, so be patient.

5.1.2 Classic Case: Date Difference

Computing the number of days between two dates is a canonical simulation problem. Don’t manually handle every if-else for each month—it’s easy to slip up.

Trick: pick a reference day (e.g., January 1, year 0), compute the day count for each date relative to it, then subtract.

5.2 Brute Force Enumeration: The Computer’s Superpower

Enumeration or brute force means you try all possibilities because computers can do it fast. The rule from Chapter 4 still applies: as long as the total operations stay under 10^8, brute force is valid.

5.2.1 Loop Enumeration

Simplest case.

Problem: Find numbers between 1 and N satisfying a condition.

Solution: for (int i = 1; i <= n; i++) if (check(i)) ...

5.2.2 Permutation Enumeration (N ≤ 10)

Problem: You are given the numbers 1 through N. Which permutation satisfies the constraints?

Complexity: 10! = 3,628,800 → safe.

Tool: next_permutation (see Chapter 3).

vector<int> p = {1, 2, 3, 4};
do {
    // check if p meets the condition
} while (next_permutation(p.begin(), p.end()));

5.2.3 Subset Enumeration (N ≤ 20)

Problem: Given N items, each can be chosen or not. Which subset is optimal?

Complexity: 2^{20} ≈ 10^6 → safe.

Technique: bitmasking.

Use an integer s to represent a subset: the i-th bit of s indicates whether item i is chosen.

for (int s = 0; s < (1 << n); s++) {
    vector<int> subset;
    for (int i = 0; i < n; i++) {
        if (s & (1 << i)) {
            subset.push_back(items[i]);
        }
    }
    // process subset...
}

5.3 Pruning: Make Brute Force Faster

Even brute force needs intelligence. Pruning means abandoning a search branch as soon as you know it cannot produce a valid or optimal solution.

Case Study: Subset Sum

Problem: Choose K numbers out of N such that their sum equals T.

Brute-force DFS tries including or excluding each number.

Pruning strategies:

1. Feasibility pruning: If the current sum already exceeds T (assuming all numbers are non-negative), even taking the smallest remaining values won’t help—return early.
2. Optimality pruning: If you’re minimizing cost and the current cost already exceeds the best known answer min_cost, stop exploring.

void dfs(int index, int current_sum) {
    if (current_sum > target) return;
 
    if (index == n) {
        if (current_sum == target) ans = true;
        return;
    }
 
    dfs(index + 1, current_sum + nums[index]);
    dfs(index + 1, current_sum);
}

5.4 When Brute Force Fails

Refer back to the table in Chapter 4.

• N = 1000 and you try to enumerate permutations? 1000! is astronomical → dead end.
• N = 10^5 and you use O(N^2) double loops? → TLE.

Strategy:

1. Check N.
2. If N is small, brute force (simulation, DFS, bitmask) works.
3. If N is large, brute force can still be used for stress testing your advanced solution.

🧠 Chapter Summary & Practice

Don’t look down on brute force just because you learned advanced algorithms. Most Bronze-level problems are pure simulation or brute force.

Exercise suggestions:

1. P1157 Combination Output (Luogu): practice DFS or bitmask enumeration.
2. P1003 [NOIP2011 Advanced] Carpet Laying: classic simulation. Don’t simulate the carpet with a 2D array when N is large—find a clever way to infer coordinates.

Mastering brute force gives you a safety net. To handle N = 10^5, you still need faster tools. Next chapter we’ll learn how sorting and binary search transform O(N) tasks into O(log N) achievements.