Simulate Alternating Stick Collection for a Nest

Problem Statement

Two birds, Bird A and Bird B, are collaborating to build a nest using a row of sticks represented by an array of positive integers sticks, where sticks[i] is the length of the i-th stick.

The birds take turns picking sticks, starting with Bird A. In each step, the active bird can only choose from either the leftmost or the rightmost available stick in the remaining row.

To ensure structural integrity, every stick added to the nest must be strictly greater in length than the stick placed immediately before it. The very first stick placed has no restriction.

On each turn, the active bird follows these specific selection rules:

1. Identify which of the two current ends (left and right) are strictly greater than the length of the last stick placed in the nest.
2. If both ends are valid:
   • Bird A prefers the smaller stick to conserve longer sticks for later. If both ends are equal, Bird A chooses the left stick.
   • Bird B prefers the larger stick to maximize immediate support. If both ends are equal, Bird B chooses the right stick.
3. If only one end is valid, the bird must choose that valid stick regardless of bird identity.
4. If neither end is valid (or no sticks remain), nest construction stops immediately, and the simulation ends.

Simulate this process and return a tuple (count_a, count_b, nest) where:

• count_a: the total number of sticks collected by Bird A.
• count_b: the total number of sticks collected by Bird B.
• nest: the list of stick lengths in the order they were placed into the nest.

Function Signature

def simulate_nest_collection(sticks: list[int]) -> tuple[int, int, list[int]]:
    pass

Input & Output Format

• Input: A list of integers sticks representing the initial line of stick lengths.
• Output: A tuple of (int, int, list[int]) representing (count_a, count_b, nest).

Constraints

• 1 <= len(sticks) <= 2 * 10^5
• 1 <= sticks[i] <= 10^9
• Expected time complexity: O(n)
• Expected auxiliary space complexity: O(n) to store the output nest

Examples

Example 1

sticks = [3, 1, 5, 2, 4]
# Output: (1, 1, [3, 4])

Explanation:

• Initial: last_stick = 0.
• Turn 1 (Bird A): Ends are 3 (left) and 4 (right). Both are > 0. Bird A chooses the smaller one (3). Remaining sticks: [1, 5, 2, 4]. Nest: [3].
• Turn 2 (Bird B): Ends are 1 (left) and 4 (right). Only 4 > 3 is valid. Bird B picks 4. Remaining sticks: [1, 5, 2]. Nest: [3, 4].
• Turn 3 (Bird A): Ends are 1 (left) and 2 (right). Neither is > 4. Construction terminates.
• Bird A collected 1 stick, Bird B collected 1 stick. Nest is [3, 4].

Example 2

sticks = [2, 6, 3, 5, 4]
# Output: (1, 1, [2, 6])

Explanation:

• Turn 1 (Bird A): Ends are 2 and 4. Both > 0. Bird A picks smaller (2 from left). Remaining: [6, 3, 5, 4]. Nest: [2].
• Turn 2 (Bird B): Ends are 6 and 4. Both > 2. Bird B picks larger (6 from left). Remaining: [3, 5, 4]. Nest: [2, 6].
• Turn 3 (Bird A): Ends are 3 and 4. Neither > 6. Construction terminates.

Example 3

sticks = [5, 2, 5]
# Output: (1, 0, [5])

Explanation:

• Turn 1 (Bird A): Ends are 5 and 5. Both equal. Tie-breaker for Bird A is left. Bird A picks 5. Remaining: [2, 5]. Nest: [5].
• Turn 2 (Bird B): Ends are 2 and 5. Neither is strictly greater than 5. Construction terminates.