$4.$ Release the Kraken

Background. In class, we saw how to tell if the Bulls could still win the division. In this problem, we're going to see if the Seattle Kraken $\backslash (\{\}^\{1\}\backslash )$ can still win the President's Trophy. The President's Trophy is awarded to the hockey team that finishes the season with the best record. Unlike in basketball, where every game ends in a win or a loss and the team with the most wins is the champion, hockey uses "points" to decide on standings. A hockey game can end in three different ways $\backslash (\{\}^\{2\}\backslash )$ :

$-$ In regulation: the winner of the game gets $2$ points in the standings and the loser gets $0.$

$-$ In overtime: the winner of the game gets $2$ points in the standings, the loser gets $1$ point in the standings.

$-$ As a draw: both teams get $1$ point in the standings

Note that the number of points awarded per game can vary! Either $2$ or $3$ points total could be awarded.

The team with the most points in the standings wins the President's Trophy. Unlike in class, we want to see if the Kraken can win the trophy "outright" $-$ it is not enough to have as many points as all other teams, we want them to have strictly more points than all other teams.

Problem. Given:

$-$ A list of $\backslash ($ n $\backslash )$ teams $($including the Kraken$),$ and their current number of points

$-$ A list of $\backslash ($ k $\backslash )$ games remaining to be played $($where a game is a pair of two teams who will play each other$)$

You should return true if the Kraken can still finish the season with strictly more points than any other teams and false otherwise.

$($a$)$ Describe how to construct a graph you could use for a max$-$flow computation in solving this problem $($i$.$e$.$ describe what the nodes and edges will be$).$ Remember to give capacities and directions for edges, and choose your source and target!

$($b$)$ Describe the runtime of the algorithm and briefly justify your answer. Assume that you would use FordFulkerson to find the max$-$flow with its standard runtime.

Hint: Think about how many edges and vertices you have in your graph. Don't forget to account for the time to build the graph!

$($c$)$ Describe how you will interpret a flow in the graph as an answer to whether the Kraken can finish the season with strictly more points than any other teams.

$($d$)$ Explain $($in a few sentences$)$ why your interpretation of the flow means that the Kraken can accumulate the most points by the end of the season.

Hint: Since we're trying to see if there is any way for the Kraken to win, we want to assume the worst outcomes for all other teams. Think about whether there is any scenario where the Kraken would prefer their competition to get $3$ total points instead of just $2.$