Left-Right Decisions

Making Choices That Don't Haunt You

Some greedy problems aren't about sorting at all. You process elements in a fixed order (left to right) and at each step make a binary or trinary choice: go left, go right, or skip. The greedy rule is about which option to prefer.

The key insight: one direction is strictly safer because it uses space that can never matter for future decisions.

---

The Problem: CF545C — Woodcutters

\(N\) trees at positions \(x_1, x_2, \ldots, x_n\) (sorted, distinct). Each tree has height 1. A tree can fall: - Left: it occupies \([x_i - 1, x_i]\) - Right: it occupies \([x_i, x_i + 1]\)

Two fallen trees cannot overlap. Maximize the number of trees felled.

The Greedy Choice: Always prefer falling left. Left uses "dead space" behind you that no future tree cares about. Right uses "live space" that might block the next tree.

The constraint: you process trees from left to right. The "obstacles" are the previous tree's fallen state and the next tree's position.

---

Why "Prefer Left" Works

Consider tree at position \(x_i\). Two choices:

Fall left: occupies \([x_i - 1, x_i]\). This space is behind us — it can only interfere with the previous tree (which we've already handled) or the ground to the left (which no future tree cares about). It never blocks any tree to the right of \(x_i\).

Fall right: occupies \([x_i, x_i + 1]\). This might block the NEXT tree at \(x_{i+1}\). If \(x_{i+1} = x_i + 1\), falling right means the next tree can't fall left (position \(x_{i+1} - 1 = x_i\) is occupied).

Conclusion: Falling left uses "dead space" — space that is irrelevant for all future decisions. Falling right uses "live space" — it might constrain the next tree. So whenever both options are available, prefer left.

Stays-ahead argument: After processing each tree \(i\), define greedy's "last occupied position" \(P\). If we fall left, \(P = x_i - 1\). If right, \(P = x_i + 1\). If we skip, \(P = x_i\) (the tree still stands at its position).

The greedy's last occupied position is always \(\leq\) any other strategy's last occupied position. This is because: 1. We prefer left (smaller position increment), and 2. We only fall right when falling left is blocked.

A smaller "last occupied position" means more room for the next tree to fall left — so greedy never forecloses an option that another strategy would have kept open.

---

Tracing the Algorithm

Spread-out trees: positions 2, 5, 7, 10, 13, 15.

\(i\)	\(x_i\)	previousOccupied	\(x_i - 1 >\) prev?	Fall left?	\(x_i + 1 < x_{i+1}\)?	Fall right?	felledCount	previousOccupied after
0	2	\(-\infty\)	\(1 > -\infty\) ✓	✓	—	—	1	1
1	5	1	\(4 > 1\) ✓	✓	—	—	2	4
2	7	4	\(6 > 4\) ✓	✓	—	—	3	6
3	10	6	\(9 > 6\) ✓	✓	—	—	4	9
4	13	9	\(12 > 9\) ✓	✓	—	—	5	12
5	15	12	\(14 > 12\) ✓	✓	—	—	6	14

All 6 felled. Trees are spread far enough that falling left always works.

Consecutive trees: positions 1, 2, 3, 4, 5.

\(i\)	\(x_i\)	previousOccupied	\(x_i - 1 >\) prev?	Fall left?	felledCount	previousOccupied
0	1	\(-\infty\)	\(0 > -\infty\) ✓	✓	1	0
1	2	0	\(1 > 0\) ✓	✓	2	1
2	3	1	\(2 > 1\) ✓	✓	3	2
3	4	2	\(3 > 2\) ✓	✓	4	3
4	5	3	\(4 > 3\) ✓	✓	5	4

All 5 felled! When positions are consecutive integers, every tree can fall left because falling left only occupies \(x_i - 1\), which the previous tree already vacated when it fell left.

The case where a tree must fall RIGHT: positions 10, 11 with previousOccupied starting at 10 (from an earlier tree that fell right to 10).

\(i\)	\(x_i\)	previousOccupied	\(x_i - 1 >\) prev?	Fall left?	Last or \(x_i + 1 < x_{i+1}\)?	Fall right?	Action
0	10	10	\(9 > 10\) ✗	✗	\(11 < 11\) ✗	✗	Skip (prev=10)
1	11	10	\(10 > 10\) ✗	✗	Last tree ✓	✓	Fall right (prev=12)

Tree at 10 can't fall either way — left is blocked by the previous occupant, right is blocked by tree at 11. Tree at 11 can fall right because it's the last tree. Result: 1 felled.

---

Example 2: CF1283E — New Year Parties

Problem: \(N\) friends at positions \(x_1, \ldots, x_n\). Each can move to \(x_i - 1\), \(x_i\), or \(x_i + 1\). Find: - (a) Minimum number of distinct houses occupied - (b) Maximum number of distinct houses occupied

Minimum (merge as much as possible):

Sort by position. Process left to right. Each group leader at position \(x_i\) moves to house \(x_i + 1\). Any subsequent friend at position \(\leq x_i + 2\) can reach that same house (by moving at most 1 step). Absorb them all into the group. Start a new group at the next unabsorbed friend.

Trace: Friends at 1, 2, 4, 7, 8, 9.

Group	Leader	Target house	Absorb condition	Friends absorbed	Next
1	\(x_0 = 1\)	\(1 + 1 = 2\)	\(x_j \leq 2 + 1 = 3\)	1, 2	\(x_2 = 4\)
2	\(x_2 = 4\)	\(4 + 1 = 5\)	\(x_j \leq 5 + 1 = 6\)	4	\(x_3 = 7\)
3	\(x_3 = 7\)	\(7 + 1 = 8\)	\(x_j \leq 8 + 1 = 9\)	7, 8, 9	done

3 groups minimum.

Maximum (spread as far as possible):

Sort by position. Each friend tries to move to \(x_i - 1\) first (occupy leftward space). If that house is taken, stay at \(x_i\). If that's also taken, move to \(x_i + 1\).

Trace: Friends at 1, 2, 4, 7, 8, 9.

Friend	\(x_i\)	Try \(x_i - 1\)	Taken?	Try \(x_i\)	Try \(x_i + 1\)	Placed at	Occupied set
0	1	0	No	—	—	0	{0}
1	2	1	No	—	—	1	{0,1}
2	4	3	No	—	—	3	{0,1,3}
3	7	6	No	—	—	6	{0,1,3,6}
4	8	7	No	—	—	7	{0,1,3,6,7}
5	9	8	No	—	—	8	{0,1,3,6,7,8}

6 distinct houses (all friends in different places). Maximum \(= N\).

This isn't always \(N\) — if two friends are at the same position, they're forced to share or go \(\pm 1\). The maximum is usually close to \(N\).

---

The "Left Never Hurts" Principle

Both problems share a deep property: moving left consumes space that no future element (to the right) cares about. This asymmetry is what makes the left-preference greedy safe.

In Woodcutters: fallen-left occupies positions \(\leq\) current tree — irrelevant for all trees to the right. In New Year Parties (minimum): group leader moves right — but the followers move left, consuming space behind the leader.

When you see a left-right decision in a sorted sequence, ask: "does left consume future-relevant space?" If no, prefer left.

---

The Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numTrees;
    cin >> numTrees;

    vector<int> treePositions(numTrees);
    for (int i = 0; i < numTrees; i++) {
        cin >> treePositions[i];
    }

    int felledCount = 0;
    int previousOccupied = -2e9;

    for (int i = 0; i < numTrees; i++) {
        if (treePositions[i] - 1 > previousOccupied) {
            felledCount++;
            previousOccupied = treePositions[i] - 1;
        } else if (i == numTrees - 1 || treePositions[i] + 1 < treePositions[i + 1]) {
            felledCount++;
            previousOccupied = treePositions[i] + 1;
        } else {
            previousOccupied = treePositions[i];
        }
    }

    cout << felledCount << "\n";
    return 0;
}

Three things to notice: - The else branch sets previousOccupied = treePositions[i] — an unfelled tree still occupies its position as an obstacle. - The right-fall check has two conditions OR'd: last tree (always safe to fall right) or next tree is far enough (\(x_i + 1 < x_{i+1}\)). - previousOccupied starts at \(-2 \times 10^9\) so the first tree can always fall left.

---

Try It

Fill in the for loop body.

Input:
5
1 2 5 7 10
Output: 5

Trace all 5 trees. Which ones fall left, which right, which skip?

Input:
3
1 2 3
Output: 3

Trace: - \(x=1\): fall left to 0. felledCount=1, previousOccupied=0. - \(x=2\): fall left to 1. \(1 > 0\) ✓. felledCount=2, previousOccupied=1. - \(x=3\): fall left to 2. \(2 > 1\) ✓. felledCount=3, previousOccupied=2.

All 3. ✓

Input:
3
5 6 7
Output: 3

Same pattern — all fall left.

Challenge: Construct an input where at least one tree must fall RIGHT to achieve the maximum count. When exactly is falling right necessary? (Hint: think about what happens when a tree can't fall left because the previous tree fell right.)

Problems

Problem	Link	Difficulty
CF545C — Woodcutters	codeforces.com/problemset/problem/545/C	1500
CF1283E — New Year Parties	codeforces.com/problemset/problem/1283/E	1800
LC 435 — Non-overlapping Intervals	leetcode.com/problems/non-overlapping-intervals	Medium
LC 452 — Minimum Arrows to Burst Balloons	leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons	Medium
LC 253 — Meeting Rooms II	leetcode.com/problems/meeting-rooms-ii	Medium
CSES 1629 — Movie Festival	cses.fi/problemset/task/1629	Medium