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.