Approach #1: Simulation [Accepted]

Intuition

A senator performing a ban doesn't need to use it on another senator immediately. We can wait to see when another team's senator will vote, then use that ban retroactively.

Algorithm

Put the senators in an integer queue: 1 for 'Radiant' and 0 for 'Dire'.

Now process the queue: if there is a floating ban for that senator, exercise it and continue. Otherwise, add a floating ban against the other team, and enqueue this senator again.

Complexity Analysis

  • Time Complexity: where is the size of the senate. Every vote removes one senator from the other team.

  • Space Complexity: , the space used by our queue.


Analysis written by: @awice.