Head of the chute

Two sawyers work one log chute turn about, pulling one, two or three logs off the head. Some logs are rot and cost money to take; nobody may pass.

The problem

Logs leave a sawmill chute only from the head, so what is left is always a tail of the original row. Two sawyers are paid piecework: each is credited the grade value of every log they pull. A sound log is worth a positive amount; a rotten one is negative, because whoever pulls it pays to chip it.

The sawyers alternate, the first sawyer starting. A turn pulls the next one, two or three logs — never zero, never past the end. Both see the whole row and both play perfectly for the larger credit.

Input. logs — the grade value of each log, head of the chute first. Values may be negative.

Output. "first", "second" or "tie": which sawyer ends with the larger credit; "tie" if the totals match.

Example.

logs = [5, -3, 8, 2]   ->  "first"

Three logs, 5 − 3 + 8 = 10, leaving the 2. Pulling only the 5 looks cleaner, but the second sawyer then takes −3, 8 and 2 for 7.

A second example, where the rot at the head decides it:

logs = [-8, 2, 2, 2, 3]   ->  "second"

The −8 cannot be avoided. Best is three logs for −4; the second sawyer then clears 2 and 3 for 5.

A third, with nothing in it for going first:

logs = [2, 3, 4, 9]   ->  "tie"

Three logs for 9, then the 9. Pull fewer and the second sawyer takes the 9 with company.

Constraints.

• 0 <= len(logs) <= 10^4
• -10^4 <= logs[i] <= 10^4
• An empty chute is a tie.

Hints

Approach

Brute force

Play out every legal sequence of pulls: three choices a turn, roughly 3^(n/2) games, past 10⁹ at 40 logs.

The insight

Score a position as the lead the sawyer to move can force, not as two totals: lead[i] = max over t in 1..3 of (logs[i..i+t-1] summed) − lead[i+t].

The game is zero-sum: credit the opponent gains is credit you give up, so "my total minus theirs" is the only figure worth tracking, and whoever stands at index i maximises the same lead[i]. After a pull of t logs the opponent stands at i + t and forces lead[i+t] back out of what you banked. Negative values need no special case: a pull is compulsory, not necessarily worth having. The sign of lead[0] is the answer.

Algorithm

1. Let n = len(logs) and set lead[n] = 0 — an empty chute is a draw.
2. For i from n − 1 down to 0, accumulate the pull total for t = 1, 2, 3 while i + t <= n, and set lead[i] to the largest total − lead[i+t].
3. Return "first" if lead[0] > 0, "second" if below 0, else "tie".

Complexity

Time O(n) — each index tries at most three pulls. Space O(n) for lead; three rolling values would do, since lead[i] reads only i+1..i+3.

Solution

"""Head of the chute — game DP over the suffix, on the margin the sawyer to move can force."""


def solve(logs):
    n = len(logs)
    # lead[i] = the most the sawyer whose turn it is can finish ahead by, when
    # logs i.. are still in the chute and both sawyers play their best.
    # invariant: lead[i] depends only on lead[i+1..i+3], so filling from the
    # tail means every value on the right is final before it is read.
    lead = [0] * (n + 4)                  # lead[n] = 0: an empty chute is a draw
    for i in range(n - 1, -1, -1):
        taken = 0
        best = None
        for t in range(1, 4):
            if i + t > n:
                break                     # cannot pull past the tail
            taken += logs[i + t - 1]      # value of the pull logs[i:i+t]
            margin = taken - lead[i + t]  # what the other sawyer forces back
            if best is None or margin > best:
                best = margin
        lead[i] = best
    if lead[0] > 0:
        return "first"
    if lead[0] < 0:
        return "second"
    return "tie"

TESTS = [
    (([5, -3, 8, 2],), "first"),
    (([2, 3, 4, 9],), "tie"),
    (([-8, 2, 2, 2, 3],), "second"),
    (([],), "tie"),
    (([7],), "first"),
    (([-4],), "second"),
    (([-4, 3],), "second"),
    (([1, 1, 1],), "first"),
    (([2, 2, 2, 2],), "first"),
    (([0, 0, 0, 0, 0],), "tie"),
    (([-2, -5, -1, -9, -3, -4],), "tie"),
    (([3, -6, 4, -1, 2, 5, -8, 7, 1],), "first"),
]

Pitfalls

• Storing the first sawyer's total instead of the lead. total − lead[i+t] subtracts margins; feed it totals and [5, -3, 8, 2] reports a credit of 8 instead of 10.
• Letting a pull run past the tail. At i = n − 2, t = 3 reads past the row; stop the inner loop when i + t > n.
• Clamping lead[i] at 0 because the logs are negative. A sawyer may not pass: [-4] is a loss for the first sawyer, and clamping reports "tie".

Variants

• Two crews, one siding — the same head-only game, but the allowed pull grows with play, so the state needs a second index.
• Splitting the ripening shelf — the margin trick on a row taken from both ends, so the suffix becomes an interval.