Problem 3.

Computer scientists have decided to play the Hunger Games, but were unhappy about the small number of players per district and the rules being too simple. So they came up with a new version of the game, and asked you to come up with an efficient data structure to handle the Games.

Rules: There are n districts, numbered 1 to n. Each district has its own number of players: initially, each district has m > 0 players. Each player has a score (non-negative integer), initially set to 1. Each district also has an integer score, initially set to 0.

• When two districts play against each other, their best players compete (one from each district). The winning player and their district both have their score incremented; the losing player and their district both have their score decremented.

• When a player reaches score o, they are disqualified (removed from their district and the game).

• When a district reaches o players, it is disqualified (removed from the game).

• The last district in play wins.

Your task: Your data structure should use O(nm) space, and implement the following operations:

• GETKTHDISTRICT(k): Given a positive integer k, return a pointer to the district currently ranked k" (i.e., the district with the highest score is ranked first), or null if k > n. Ties are broken by district number, so if district 10 and district 98 have the same score, district 98 is considered "better" because 98 > 10. This operation should run in O(log n) time.

COMPETE(k, j, k_wins): Given two positive integers 1 ≤ k, i ≤ n and a Boolean k_wins, record the result of a game between the districts currently ranked kth and jth and update the data structure according to the rules (or do nothing if k = j or if either k or j is not between 1 and n). If k_wins is True, then the kth district wins; otherwise, the jth district wins. This operation should run in O(logn + log m) time.

• GETSTRONGEST(): Returns a pointer to the district whose best player has the largest score. This operation should run in O(n) time.

Note that the number of (currently playing) districts n can change during the Hunger Games, as districts get eliminated.

a) Describe your data structure implementation in plain English.

b) Prove the correctness of your data structure (pay special attention to the rules of the game!).

c) Analyze the time and space complexity of your data structure.