write the simulate_day method so the worst_case time complexity is O(n + c log(n)) where N is the current number of islands with non-zero money, and C is the number of captains participating in the Davy Back Fight. However, in this mode, you aren't alone at sea! You're battling it out against other up-and-coming pirates to loot these islands before they do! The pirates that dwell in these seas are a bit uncharacteristically organised, and have decided to turn this looting into a game called the Davy Back Fight, so that they can determine who among them is the best pirate, and so deserves the best crew. A Davy Back Fight works the following way: At the start of each day, every pirate gets a fresh crew of the same size. All pirates then take turns selecting an island to loot, with a specified number of crew to send OR they could skip their turn and do nothing. After each pirate has selected their action, the day is over and the score of the day is counted. The score of a particular pirate crew on a given day is 2×c+m, where c is the remaining crew-mates and m is the money looted on that day. The pirate with the highest score wins the Davy Back Fight Two pirates can send crew to the same island. Every pirate in the Davy Back Fight surprisingly are perfect logicians, meaning they will always select the island and crew amount that will maximise their total score for the day. We want you to implement some code that simulates the Davy Back Fight. Your task is to implement Mode2Navigator with the following methods: __init__(self, n_pirates: int) -> None: Initialise the object, n_pirates is the number of pirates in the Davy Back Fight. add_islands(self, islands: list[Island]) -> None: Add islands to the seas. simulate_day(self, crew: int) -> list[tuple[Island|None, int]]: Simulate a day of the Davy Back Fight. crew is the size of the crew for every pirate captain, and you should return a list of tuples, each representing the choices made by the first, second, ... captain in the order. Each tuple should contain the Island that was plundered (if any), and how many crew-mates were sent onto the island (0 if no island was selected).

Here is the code:
 

from island import Island

import heapq

 

class Mode2Navigator:

"""

Student-TODO: short paragraph as per https://edstem.org/au/courses/12108/lessons/42810/slides/294117

"""

 

def __init__(self, n_pirates: int) -> None:

"""

Student-TODO: Best/Worst Case

"""

self.n_pirates = n_pirates

self.islands = []




 

def add_islands(self, islands: list[Island]):

"""

Student-TODO: Best/Worst Case

"""

self.islands.extend(islands)

 

def potential_score(self, island, crew):

m = min(island.money, island.money * crew / island.marines) if island.marines > 0 else island.money

c_left = crew - min(crew, island.marines)

return 2 * c_left + m



 

def simulate_day(self, crew: int):

"""

Student-TODO: Best/Worst Case

"""

decisions = []

 

for _ in range(self.n_pirates):

if not self.islands:

decisions.append((None, 0))

continue

 

# Sort islands based on potential score

sorted_islands = sorted(self.islands, key=lambda x: -self.potential_score(x, crew))

 

# Select the island with the best potential score

best_island = sorted_islands[0]

 

# Determine the crew to be sent

c_to_send = min(crew, best_island.marines)

 

# Add to the decisions

decisions.append((best_island, c_to_send))

 

# Update island's state

best_island.money -= min(best_island.money, best_island.money * c_to_send / best_island.marines)

best_island.marines -= c_to_send

 

# If island is emptied, remove it from the list

if best_island.marines == 0:

self.islands.remove(best_island)

 

return decisions