Problem 407504 · hard · Phase 04 Non-Linear Data Structures

The Top-Third Bonus Pool

heaps · two heaps · lazy deletion · classes · order statistics

A sales team pays a weekly bonus pool equal to the combined score of its top third. Write a class BonusBoard:

  • BonusBoard() starts with nobody on the board.
  • score(name, points) puts name on the board with score points. If name is already on the board, its old score is replaced.
  • leave(name) takes name off the board. If name is not on the board, nothing happens.
  • pool() returns the sum of the ceil(N / 3) highest scores, where N is the number of people on the board (so 0 for an empty board). Equal scores make no difference to the sum.

score and leave return None.

Examples

Input:  ops  = ["BonusBoard", "score", "score", "score", "pool", "score", "pool",
                "leave", "pool", "score", "pool"]
        args = [[], ["ann", 50], ["bo", 20], ["cy", 40], [], ["di", 45], [],
                ["ann"], [], ["bo", 70], []]
Output: [None, None, None, None, 50, None, 95, None, 45, None, 70]
Explanation: 3 people: the top 1 is 50. 4 people: the top 2 are 50 + 45.
             ann leaves: 3 people, top 1 is 45. bo rises to 70 and takes the top spot.

Constraints

  • At most 2 * 10**5 calls in total.
  • Names are non-empty strings; -10**9 <= points <= 10**9.
  • Sorting the scores for each pool call is too slow for the largest tests.

Goals

  • Split a changing collection into a top group and the rest with two heaps
  • Support score changes and departures with version stamps and lazy deletion
  • Keep the top group's size tied to a fraction of the live count
Starting Python…