Dota2 Senate
Dota2 Senate: senators from parties R and D ban each other in rounds; each senator, in order, bans the next opposing senator who has not yet been banned. Predict which party wins.
- n == senate.length
- 1 <= n <= 10⁴
- senate[i] is either 'R' or 'D'.
Intuition
A senator's only sensible move is to ban the next opponent who would otherwise act — banning anyone further away lets a nearer enemy speak first. Two queues of indices capture that: the smaller index acts, bans the other, and rejoins the back of the line for the next round by adding n to its index.
Round-robin turn taking with elimination is a queue problem, and 'act in order, repeatedly' is the tell. The + n re-enqueue is the reusable trick for modelling wrap-around rounds without an explicit outer loop — the same device appears in Time Needed to Buy Tickets and other circular-turn simulations.
Approach
Before reading on: if you were a senator, which opponent would you ban and why is any other choice worse? Then work out how a surviving senator rejoins the queue for the next round. Aim for O(n).
Why banning the nearest opponent is optimal
Every senator wants their own party to keep as many turns as possible. The opponent who does the most damage soonest is the one who acts next, so eliminating them is never worse than eliminating a later one — an exchange argument identical in spirit to other greedy scheduling proofs. This means no search or simulation of choices is needed; the move is forced.
Two queues of indices
Push the indices of R senators into one queue and D senators into the other, both in original order. Repeatedly pop the front of each: the smaller index belongs to the senator who acts first in this round, so they ban the other — that index is simply discarded. The winner is not finished, though: they will act again in the next round, so re-enqueue them with index + n, which places them correctly after everyone still pending in the current round.
Why +n keeps the order correct
Adding n models wrapping around into the next round while preserving relative order, because all surviving senators of the current round get the same offset. Comparing raw indices then always identifies who speaks next globally. The loop ends when one queue empties, and the non-empty queue names the winning party. Each iteration removes exactly one senator, so the process is O(n) with O(n) space.
Solution & live demo
Common pitfalls
Simulating the string with repeated scans
while True:
for i, s in enumerate(senate):
# find and mark the next opponent# two queues of indices, compare fronts
Each round rescans the whole string, giving O(n²) on 10⁴ senators. The queues make each elimination O(1).
Forgetting to re-enqueue the winner
if r < d:
pass # d is banned, r just discardedif r < d:
radiant.append(r + n)A senator who bans someone is not spent — they act again next round. Dropping them makes both queues drain together and the loop ends with the wrong survivor.
Re-enqueueing without the +n offset
radiant.append(r)
radiant.append(r + n)
Without the offset the senator's index still looks like a current-round position, so they may act twice in one round. Adding n places them after everyone still pending, preserving global order.
Edge cases
The opposing queue is empty from the start, so that party wins immediately.
R acts first and bans D, so Radiant wins.
The two D senators act first each round and ban R faster than R can retaliate, so Dire wins even while outnumbered.
One queue is empty and the lone senator's party wins.
Whoever acts first in the first round gains the advantage and wins.