Design room progression with leaderboard

Design a data structure to simulate a sequence of rooms where players solve tasks and can move only to the next room once finished. Support the following operations with high throughput: addPlayer(id); recordTask(playerId, roomId, points); moveToNextRoom(playerId); getPlayerState(playerId) -> {room, score}; and topK(k) -> the k players with highest total scores across all rooms at query time. Implement efficient updates to the leaderboard and explain how you will prevent duplicate entries when using a heap (e.g., lazy deletion, versioning, or indexed heaps). Analyze the time and space complexity of each operation and justify your design choices.

Design Room Progression with Leaderboard

Design a data structure that simulates a sequence of rooms where players solve tasks and may move only to the next room once they finish the current one. You will process a list of operations and return the outputs of the query operations in order.

Implement a function solution(operations) that processes the following operation tuples:

• ('addPlayer', id) — register a new player. Each player starts in room 0 with a total score of 0. Adding an existing id is a no-op (idempotent).
• ('recordTask', playerId, roomId, points) — award points to the player only if roomId equals the player's current room (you cannot score in a room you have already left or not yet reached). The points add to the player's running total across all rooms.
• ('moveToNextRoom', playerId) — advance the player to the next room (increment their room index by 1).
• ('getPlayerState', playerId) — append {'room': r, 'score': s} to the result list. If the player does not exist, append None.
• ('topK', k) — append a list of the k player ids with the highest total scores at query time, highest first. Break ties by smaller id. If fewer than k players exist, return all of them.

Return the list of outputs produced by getPlayerState and topK, in the order they were called.

Leaderboard requirement: keep topK efficient as scores update. Because a binary heap cannot update a key in place, a naive re-push leaves duplicate (stale) entries for the same player. Prevent duplicates using lazy deletion with version stamps: every score change bumps the player's version and pushes a fresh (-score, id, version) entry; at query time pop entries whose version no longer matches the player's current version and discard them.

Example: addPlayer 1, addPlayer 2, recordTask 1 0 50, recordTask 2 0 30, getPlayerState 1, topK 2 returns [{'room': 0, 'score': 50}, [1, 2]].

Constraints

• Player ids and room ids are non-negative integers.
• recordTask only counts when roomId equals the player's current room.
• topK breaks score ties by smaller player id and returns all players when k exceeds the player count.
• Operations referencing unknown players are ignored (getPlayerState returns None).
• 1 <= number of operations <= 10^5

Hints

1. Track three maps keyed by player id: current room, total score, and a version counter.
2. For recordTask, guard on roomId == current room before adding points — a player can only score in the room they currently occupy.
3. A binary heap can't decrease-key in place. Re-push a fresh (-score, id, version) entry on every score change and skip any popped entry whose version no longer matches the player's current version (lazy deletion).
4. During topK, pop valid entries into a buffer (dedup with a 'seen' set) until you have k, then push the valid entries back so the heap is preserved. Ordering by (-score, id) gives highest-score-first with smaller-id tie-breaking.