Design a balloon stability tracker

Implement a class BalloonFestival to manage hot-air balloons and wind fields over time, and to report rewarded balloons at inspection times. Methods and rules:

Initialization

• init(yourBalloonNames: list[str]) -> None
  • Registers the unique names of balloons that belong to your team. Any balloon name not in this list but seen in later events is a competitor.
  • Assumptions: total number of method calls Q satisfies 1 ≤ Q < 2^20.

Operations

• BalloonAscended(timestamp: float, balloonName: str, altitude: float) -> bool

  • Records that balloonName is airborne at the given altitude. This call is used both for first ascent and for changing altitude while airborne.
  • On ascent, the balloon’s stability is set to stable by default.
  • Returns True on success; False for invalid input (unknown altitude bounds), or if balloonName is already airborne when ascending without changing altitude, or timestamp ordering is violated.

• BalloonDescended(timestamp: float, balloonName: str) -> bool

  • Records that balloonName has landed (is on the ground and not airborne).
  • Resets its stability to the default (stable) for the next ascent.
  • Returns True on success; False if the balloon is already on the ground or timestamp ordering is violated.

• SetWindSpeed(timestamp: float, altitude: float, windSpeed: float) -> bool

  • Sets or replaces the base wind speed anchor at the specified WindAltitude = altitude.
  • Returns True on success; False if inputs violate bounds or timestamp ordering.

• InspectBalloons(timestamp: float) -> list[str]

  • Returns the lexicographically sorted names of your team’s balloons that are airborne and currently stable, and whose current altitude is greater than or equal to the maximum altitude among all currently stable competitor balloons. If there are no currently stable competitor balloons at this timestamp, return [].

Physics and stability rules

• Wind anchors: each SetWindSpeed defines a base wind component at a WindAltitude with base magnitude WindSpeedAtAltitude.
• Aggregate wind at an arbitrary altitude h is the sum over all anchors: WindSpeed(h) = Σ over anchors [ s / (1 + ((h - A) / 100)^

2. ], where each anchor has altitude A and base speed s.

• Stability threshold: a balloon becomes immediately unstable whenever the instantaneous WindSpeed at its current altitude exceeds 15 m/s (> 15). It can regain stability only if it remains continuously at altitudes where WindSpeed ≤ 15 m/s for at least 300 seconds (inclusive) since the start of that safe period.
• On BalloonAscended, the balloon starts as stable by default, subject to immediate re-evaluation against the wind threshold at that timestamp.
• On BalloonDescended, the balloon is considered not airborne and ignored in inspections; stability resets for the next ascent.

Constraints and assumptions

• Altitude bounds: 0 < altitude < 2^15.
• Wind speed bounds: 0 ≤ windSpeed < 2^5.
• Timestamps are floats and are nondecreasing across all calls.
• Multiple wind anchors can coexist; their contributions add cumulatively.

Requirements

• Design data structures to support up to Q < 2^20 operations efficiently. Aim to handle each method in near O(log N) time, where N is the number of active balloons or wind anchors.
• Precisely track stability state transitions over time for each balloon, including when changing altitude while airborne.
• Define edge-case behavior (e.g., ascending an unknown balloon name—treat as competitor; re-ascending without descent; updating an existing wind anchor at the same altitude).
• Provide the algorithm, data structures, and time/space complexity for each method.

Design a Balloon Stability Tracker

You are building a stability tracker for a hot-air balloon festival. Over time, balloons change altitude, wind-field anchors are updated, and inspectors request a list of your team's rewarded balloons. Implement the function solution(yourBalloonNames, operations) that simulates a stream of operations in order and returns the list of results they produce.

---

Function contract

def solution(yourBalloonNames, operations):
    ...

• yourBalloonNames — a list of unique strings naming the balloons that belong to your team.
• operations — a list of operations, each a tuple whose first element is the operation name (see below). They are processed strictly in the given order.
• Return value — a list built by appending one result per operation that produces output:
  • BalloonAscended, BalloonDescended, SetWindSpeed → append the returned bool.
  • InspectBalloons → append the returned list of strings.

Every operation appends exactly one entry, so the output list has the same length as operations.

Balloon ownership

• Your team balloons: the names in yourBalloonNames.
• Competitor balloons: any other name that first appears in a later operation. A balloon's state is created the first time it ascends.

---

Timestamps

Every operation carries a timestamp (float). Each operation's timestamp must be ≥ the timestamp of the most recent operation that was accepted — an operation whose timestamp is less than that last-accepted timestamp is an ordering violation. Equal timestamps are allowed.

A rejected (out-of-order) operation has no effect and does not become the new baseline; the next operation is still compared against the most recent accepted timestamp. On an ordering violation, the operation returns False (or [] for InspectBalloons).

Each accepted operation (including InspectBalloons) first advances time to its timestamp, applying any pending stability recoveries (see Stability rules) before the operation itself runs.

---

Operations

("BalloonAscended", timestamp, balloonName, altitude) → bool

Records that balloonName is airborne at altitude. This is used for both the first ascent and for changing altitude while already airborne.

On a successful (non-no-op) ascent or altitude change:

• The balloon becomes airborne at the new altitude.
• Its stability is reset to stable, then immediately re-evaluated against the wind at that altitude and timestamp: if the wind there exceeds the threshold it flips to unstable right away; otherwise it stays stable.

Returns False (no state change) if any of these hold:

• the timestamp ordering is violated, or
• altitude is out of bounds, or
• the balloon is already airborne and the new altitude equals its current altitude (a no-op ascent).

Otherwise returns True.

("BalloonDescended", timestamp, balloonName) → bool

Records that balloonName has landed.

• The balloon becomes not-airborne and is ignored by inspections.
• Its stability resets to stable for the next ascent.

Returns False (no state change) if:

• the timestamp ordering is violated, or
• the balloon is already on the ground (not currently airborne).

Otherwise returns True.

("SetWindSpeed", timestamp, altitude, windSpeed) → bool

Sets or replaces a wind anchor at altitude with base magnitude windSpeed.

• Anchors at multiple distinct altitudes may coexist; their contributions add cumulatively (see Wind physics).
• Setting an anchor at an altitude that already has one overwrites its base speed.
• After the change, every airborne balloon is re-evaluated for stability at the new wind field.

Returns False (no state change) if:

• the timestamp ordering is violated, or
• altitude is out of bounds, or
• windSpeed is out of bounds.

Otherwise returns True.

("InspectBalloons", timestamp) → list[str]

Returns the lexicographically sorted names of your team's balloons that are all of:

• airborne, and
• currently stable, and
• at altitude ≥ the maximum altitude among all currently stable competitor balloons.

Return [] if:

• the timestamp ordering is violated, or
• there are no currently stable competitor balloons at that timestamp.

---

Wind physics

Let each wind anchor have altitude A and base speed s. The aggregate wind speed at altitude h is the sum over all current anchors:

WindSpeed(h) = Σ  s / ( 1 + ((h - A) / 100)^2 )

---

Stability rules

Let THRESHOLD = 15 and RECOVERY = 300 seconds. Each balloon is either stable or unstable.

• A stable balloon becomes unstable the moment WindSpeed(currentAltitude) > THRESHOLD.
• An unstable balloon can regain stability only after it has stayed continuously at altitudes where WindSpeed ≤ THRESHOLD for at least RECOVERY seconds (inclusive), measured from the start of that uninterrupted safe period. Any interruption — the wind rising above the threshold again, an altitude change, or a descent — restarts the clock. The recovery clock applies only to balloons that are currently unstable; a stable balloon at a safe altitude has no clock running and simply remains stable.
• On BalloonAscended, stability is reset to stable, then immediately re-evaluated against the current wind. If the new altitude is unsafe (WindSpeed > THRESHOLD) the balloon becomes unstable at once and a fresh recovery period begins from that timestamp; if the altitude is safe, the balloon simply stays stable (no recovery clock).
• On BalloonDescended, the balloon is not airborne and its stability resets to stable for the next ascent.
• When SetWindSpeed changes the wind field, each airborne balloon flips to unstable immediately if its altitude is now unsafe; if it is already unstable, its recovery period begins / continues when its altitude is now safe, or its clock is cleared when its altitude is unsafe.

---

Constraints

• 1 ≤ len(operations) < 2^20.
• 0 < altitude < 2^15 (for both balloon altitude and wind-anchor altitude).
• 0 ≤ windSpeed < 2^5.
• Timestamps are floats and must be nondecreasing across all accepted operations.
• yourBalloonNames contains unique strings.

Examples

Example 1

Input: (["A","B"], [("SetWindSpeed",0.0,1000.0,10.0),("BalloonAscended",0.0,"A",1000.0),("BalloonAscended",0.0,"X",1000.0),("InspectBalloons",0.0),("SetWindSpeed",10.0,1000.0,20.0),("InspectBalloons",10.0),("SetWindSpeed",20.0,1000.0,10.0),("InspectBalloons",319.0),("InspectBalloons",320.0)])
Output: [True, True, True, ["A"], True, [], True, [], ["A"]]

Explanation: At t=0 both A (team) and X (competitor) are stable at altitude 1000, so A is rewarded. At t=10 wind becomes unsafe (>15), making both unstable, so no stable competitors => []. After wind becomes safe again at t=20, stability is regained only after 300s of continuous safe wind, so at t=319 still unstable; at t=320 both regain stability and A is rewarded again.

Example 2

Input: (["T"], [("SetWindSpeed",0.0,1000.0,16.0),("BalloonAscended",0.0,"T",1000.0),("SetWindSpeed",1.0,1000.0,0.0),("InspectBalloons",301.0),("BalloonAscended",301.0,"C",1000.0),("InspectBalloons",301.0),("BalloonAscended",302.0,"C",1200.0),("InspectBalloons",302.0)])
Output: [True, True, True, [], True, ["T"], True, []]

Explanation: T starts unstable (wind 16). Wind becomes safe at t=1, so T regains stability at t=301, but with no stable competitors inspection returns []. After competitor C ascends stable at t=301, T is rewarded. When C moves to altitude 1200, competitor max altitude becomes 1200 so T (at 1000) is no longer rewarded.

Hints

1. Track each balloon as a small state machine: airborne/ground, stable/unstable, and (if unstable) when its current safe period started.
2. To avoid scanning all unstable balloons every time, push (safe_start + 300) into a min-heap; when time advances, promote any balloons whose deadline has passed (and are still safe).

Approach

This is a stateful event simulation, not a single algorithm. Operations arrive timestamp-ordered, and each one mutates shared state, so correctness hinges on bookkeeping rather than a clever trick.

Per-balloon State tracks airborne, altitude, stable, safe_start (when its current safe window began), and two version counters used for lazy heap invalidation.

Wind is a dict anchors[altitude] -> base speed. wind_at(h) sums s / (1 + ((h-A)/100)^2) over all anchors, memoized by a global wind_version that bumps (clearing the cache) whenever an anchor changes.

Two lazy-deletion heaps avoid scanning everything:

• recovery_heap holds (safe_start + 300, name, rec_ver). advance_time(now) pops any due entry and, if the balloon is still in the same continuous safe period (rec_ver matches) and wind is still ≤ 15, promotes it back to stable. This implements the "continuously safe for ≥300s" rule — any altitude change or wind spike bumps rec_ver, silently invalidating stale heap entries.
• comp_heap is a max-heap (by -altitude) of stable competitor balloons. get_comp_max_altitude discards stale tops (wrong version / no longer airborne·stable / altitude mismatch).

Per operation: ascent resets stability to stable then immediately re-checks wind; descent grounds the balloon; SetWindSpeed re-evaluates every airborne balloon grouped by altitude, flipping to unstable instantly or opening a safe period. InspectBalloons returns your team's airborne, stable balloons at altitude ≥ the max stable-competitor altitude (or [] if none), sorted lexicographically. Out-of-order timestamps and out-of-bounds values short-circuit to False/[]. Correctness comes from versioning: state is the source of truth and heap entries are validated against it on pop.

• Space complexity: O(A + B + H), where A = wind anchors, B = balloon states + altitude buckets, and H = total live (lazily-deleted) entries across the recovery and competitor heaps; H is bounded by the number of state transitions and reclaimed on pop.