Dota2 Senate

Problem

Two parties, Radiant ('R') and Dire ('D'), sit in a senate. You are given a string senate where each character is the party of one senator, listed in the order they will act. Voting happens in round-robin order, cycling through the survivors again and again.

When it is a senator’s turn, they may exercise one right: ban any one senator from the other party, removing that senator from all future rounds. (A rational senator always uses this right — passing never helps.) The process repeats, skipping banned senators, until every remaining senator belongs to one party. Return the winning party: "Radiant" or "Dire".

Because each senator plays optimally for their own party, the question is really: given the seating order, which party can guarantee the win?

Examples

• senate = "RD" → "Radiant" — R acts first and bans D; only R remains.
• senate = "RDD" → "Dire" — R bans one D. The remaining D (who has not acted yet this round) then bans R. Only D’s remain.
• senate = "RRDDD" → "Radiant" — the two R’s act first each lap and eliminate D’s faster than the three D’s can retaliate, even though Dire has more senators.

Constraints

• 1 <= len(senate) <= 10^4
• senate contains only 'R' and 'D', and both letters appear at least once.

An O(n) or O(n log n) solution is expected; the number of ban rounds can be large, so naive re-scanning is too slow.

Think about it first

TL;DR

Two index queues; each round the earlier senator bans the other party’s front senator and re-queues at index + n — O(n) time, O(n) space.

Approach 1 — Brute force: simulate the seating list literally

Keep a list of surviving senators. Walk it in order; each acting senator scans forward (wrapping around) for the nearest opponent and marks them banned. Repeat laps until only one party remains.

from collections import deque
from typing import List

def predictPartyVictory(senate: str) -> str:
    alive = list(senate)
    while 'R' in alive and 'D' in alive:
        n = len(alive)
        banned = [False] * n
        for i in range(n):
            if banned[i]:
                continue
            # ban the nearest opponent ahead, wrapping around
            for step in range(1, n):
                j = (i + step) % n
                if not banned[j] and alive[j] != alive[i]:
                    banned[j] = True
                    break
        alive = [c for i, c in enumerate(alive) if not banned[i]]
    return "Radiant" if 'R' in alive else "Dire"

Complexity: each lap is O(n^2) (every senator may scan the whole list), and a lap removes at most half the senators, so O(log n) laps → O(n^2 log n). At n = 10^4 the inner quadratic scan is too slow.

Approach 2 — Greedy with two queues

Greedy-choice property. When a senator acts, the best target is the nearest upcoming opponent, the opposing senator who would act soonest. Suppose instead they ban a later opponent Y and spare the nearest opponent X. Then X acts on schedule and bans one of their allies before Y would have mattered, which weakens their side and leaves the most imminent threat alive. Banning the soonest-acting opponent delays the enemy’s next move as far as possible, so it is a safe greedy move at every step.

Keep two queues holding the turn indices of each party’s living senators. The senator with the smaller index acts first and bans the opponent at the front of the other queue (that opponent is the nearest future one, since the queues stay sorted by turn order). The survivor rejoins its queue for the next lap at index i + n, which keeps all indices comparable across laps.

from collections import deque

def predictPartyVictory(senate: str) -> str:
    n = len(senate)
    radiant = deque(i for i, c in enumerate(senate) if c == 'R')
    dire = deque(i for i, c in enumerate(senate) if c == 'D')
    while radiant and dire:
        r, d = radiant.popleft(), dire.popleft()
        if r < d:               # R acts first, bans this D
            radiant.append(r + n)
        else:                   # D acts first, bans this R
            dire.append(d + n)
    return "Radiant" if radiant else "Dire"

Each iteration of the loop resolves one showdown between the two queue fronts:

flowchart TD
    A[Both queues non-empty?] -->|No| E[The non-empty party wins]
    A -->|Yes| B[Pop front index r from Radiant and d from Dire]
    B --> C{r < d?}
    C -->|Yes| D[R acts first: ban this D, re-queue r + n in Radiant]
    C -->|No| F[D acts first: ban this R, re-queue d + n in Dire]
    D --> A
    F --> A

Walkthrough on senate = "RRDDD" (indices 0..4, n = 5):

1. radiant = [0,1], dire = [2,3,4].
2. Pop r=0, d=2: 0 < 2, so R acts first and bans D#2. R re-queues 0+5=5 → radiant=[1,5], dire=[3,4].
3. Pop r=1, d=3: 1 < 3, R bans D#3. radiant=[5,6], dire=[4].
4. Pop r=5, d=4: 4 < 5, D acts first and bans R#5. dire=[9], radiant=[6].
5. Pop r=6, d=9: 6 < 9, R bans D#9. radiant=[11], dire=[] → “Radiant”.

Even though Dire outnumbers Radiant 3 to 2, the two R’s sit earlier in the order, so they act first each lap and out-trade the D’s. Majority does not decide the outcome; position does.

Sanity check senate = "RD": radiant=[0], dire=[1]. Pop r=0,d=1: 0<1 → R bans D, radiant=[2], dire=[] → “Radiant”.

Complexity: each iteration bans exactly one senator, so the loop runs at most n - 1 times, each iteration O(1). Time O(n), space O(n) for the two queues.

Common pitfalls

• Banning the global first opponent instead of the nearest one after the acting senator — the queues already encode “nearest upcoming,” so trust the front-vs-front comparison rather than re-searching.
• Forgetting to re-queue the survivor at i + n; without the offset, laps stop interleaving and the loop misbehaves.
• Assuming the majority party always wins. Position matters: leading senators of a smaller-but-earlier bloc can eliminate the majority’s front-runners each lap.

Pattern takeaway

Greedy on an ordered process: when every actor moves in a fixed sequence and each move eliminates a competitor, the optimal target is almost always the nearest future competitor — killing the soonest threat dominates saving it. Encode “turn order” as indices in a queue and let the smaller index win each showdown.