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 $0,$ they are disqualified $($removed from their district

and the game$).$

$$ When a district reaches $0$ 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

th $($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$,$ j $<=$ n and a Boolean

k$\_$wins, record the result of a game between the districts currently ranked k

th

and j

th 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

k

th district wins; otherwise, the j

th district wins. This operation should run in

O$($log n $+$ 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.

If I were to implement a min heap to store the district in order of rank, and stores the value of their total points, and each node in the min heap points to a max heap that contains the districts m players, would it satisfy the above conditions?