545C. Woodcutters

Problem: Codeforces 545C
Tags: Greedy, DP
Difficulty: 1500

Problem Summary

Given n trees on a line, each at position x[i] with height h[i], fell each tree left (occupies [x[i]-h[i], x[i]]) or right (occupies [x[i], x[i]+h[i]]). A fallen tree must not overlap any occupied point. Maximize the number of trees felled.

Key Observations

1. The first tree can always fall left — there is nothing to its left.
2. The last tree can always fall right — there is nothing to its right.
3. For every tree in between, we greedily try to fell it left first, then right. If neither works, we leave it standing.

Greedy Strategy

Process trees left to right, tracking last_occupied — the rightmost point currently occupied.

• Initialize: Fell tree 0 to the left. Set last_occupied = x[0].
• For each middle tree i (1 to n-2):
  • Try left: If x[i] - h[i] > last_occupied, fell left. Update last_occupied = x[i].
  • Try right: Else if x[i] + h[i] < x[i+1], fell right. Update last_occupied = x[i] + h[i].
  • Otherwise: Leave standing. Update last_occupied = x[i].
• Last tree is always counted.

Why Left First?

Falling left is always at least as good as falling right — it keeps the rightmost occupied point as small as possible (x[i] vs x[i]+h[i]), giving future trees more room to fall.

Complexity

• Time: O(n)
• Space: O(n)

Correct Solution

void solve() {
    ll n;
    cin >> n;
    vector<ll> x(n), h(n);
    rep(i, 0, n){
        cin >> x[i] >> h[i];
    }

    if(n == 1){
        cout << 1 << "\n";
        return;
    }

    ll ans = 2; // first tree always falls left, last tree always falls right
    ll last_occupied = x[0]; // rightmost occupied point after processing tree 0

    rep(i, 1, n - 1){
        if(x[i] - h[i] > last_occupied){
            ans++;
            last_occupied = x[i];
        }
        else if(x[i] + h[i] < x[i+1]){
            ans++;
            last_occupied = x[i] + h[i];
        }
        else {
            last_occupied = x[i];
        }
    }
    cout << ans << "\n";
}

Wrong Approach (Initial Attempt)

void solve() {
    ll n;
    cin >> n;
    vector<ll> x(n), h(n);
    std::set<ll> index_occupied;
    rep(i, 0, n){
        cin >> x[i] >> h[i];
        index_occupied.insert(x[i]);
    }

    ll ans = 2;
    index_occupied.insert(x[0]-h[0]);
    index_occupied.insert(x[n-1]+h[n-1]);

    rep(i, 1, n - 1){
        if(x[i] - h[i] > x[i-1] && !index_occupied.count(x[i]-h[i])){
            ans++;
            index_occupied.insert(x[i]-h[i]);
            continue;
        }

        if(x[i] + h[i] < x[i+1] && !index_occupied.count(x[i]+h[i])){
            ans++;
            index_occupied.insert(x[i]+h[i]);
        }
    }
    cout << ans << "\n";
}

Bug #1 — Tracking Occupied Space with a Set of Points

A felled tree occupies an entire segment, not a single point. For example, if tree at $x = 3$ with $h = 5$ falls right, it occupies $[3, 8]$. Every point in that interval is blocked. But the wrong code only inserts 8 into the set — it never knows that points like 6 or 7 are also occupied.

The correct solution tracks last_occupied — the rightmost coordinate of any occupied region so far. Since we process trees left-to-right, this single number perfectly captures the boundary:

• Fall left? → Check x[i] - h[i] > last_occupied
• Fall right? → Check x[i] + h[i] < x[i+1]

Bug #2 — Checking Against x[i-1] Instead of Actual Boundary

if(x[i] - h[i] > x[i-1] && !index_occupied.count(x[i]-h[i]))

If tree i-1 was felled to the right, its occupied segment extends to $x_{i-1} + h_{i-1}$, which can be far beyond $x_{i-1}$. Checking against x[i-1] ignores this.

Counterexample:

5
1 1
3 5
9 3
12 2
15 1

Wrong answer: 5 — Tree 2’s left-fall [6, 9] overlaps with tree 1’s right-fall [3, 8] at [6, 8]!
Correct answer: 4 — Tree 2 cannot be felled in any direction.

The wrong code checks 6 > x[1] = 3 ✓ and 6 ∉ set ✓, so it allows the fall. But the actual boundary from tree 1’s right-fall extends to 8, and 6 ≤ 8.

Bug #3 — Edge Case: n = 1

The wrong solution starts with ans = 2, assuming at least 2 trees. When n = 1, it outputs 2 instead of 1.

Key Takeaway

The greedy strategy (try left first, then right) is correct. The bug was in how occupied space was tracked. Trees occupy intervals, not points. Tracking just the rightmost occupied point (last_occupied) correctly represents the boundary.