Dota2 Senate

MEDIUM✓ CHIP-TIMEDLC #649 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Senators sit in a fixed circle and vote in turn order: on a senator's turn, if a rival party still has anyone standing, they ban the nearest rival ahead of them. Play loops around until one party has no senators left — name the winner.

Senators from two parties — R and D — sit around a circle in a fixed order and take turns going around it, looping back to the start as many times as needed. Each character of the input string is one senator's party.

On a senator's turn, if the opposing party still has at least one senator left standing, that senator bans the nearest still-standing rival that comes after them in turn order — banned senators skip every future turn.

Play keeps looping around the circle until one party has no senators left standing at all. The task is naming which party ends up winning.

the string holds only the two characters 'R' and 'D'
both parties are guaranteed to have at least one senator at the start
turn order loops the circle repeatedly until one party is wiped out
the answer is one of the two party names, whichever survives

EX 01

senate = "RRDDD"

→ "Radiant"

R starts with a head count deficit but wins the queue race

EX 02

senate = "DDRRR"

→ "Dire"

D starts behind but outlasts R

EX 03

senate = "DR"

→ "Dire"

minimum size, D acts first

The hintstake only what you need

HINT 1 THE NUDGE

The senator whose turn is 'next' overall is always the one whose last action is farthest in the past. Simulating string-position order across repeated sweeps of the circle is really just asking: who acted least recently?

HINT 2 THE STRUCTURE

Two separate turn-orders — one for R, one for D — capture exactly that. Compare the next R's turn number to the next D's turn number; whichever is EARLIER survives this duel and bans the other.

HINT 3 ONE STEP FROM THE ANSWER

Use two queues of original indices. Pop the front of each; the smaller index acts first and bans the other, then re-enters its own queue at index + n — its next turn, one full lap later. Whichever queue empties first loses.

Coach's boardthe pattern, step by step

THE TURN QUEUEPATTERN · GREEDY — TWO QUEUESsenate = "RRDDD"

QUEUES — R / D (turn tickets)

R queue → [0, 1]

D queue → [2, 3, 4]

STEP 1

Senate RRDDD. Two turn-order queues: Radiant [0,1], Dire [2,3,4] — whichever front ticket is earlier acts next.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/dota2-senate.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        radiant = collections.deque(i for i, c in enumerate(senate) if c == "R")
        dire = collections.deque(i for i, c in enumerate(senate) if c == "D")
        while radiant and dire:
            r, d = radiant.popleft(), dire.popleft()
            if r < d:
                radiant.append(r + n)
            else:
                dire.append(d + n)
        return "Radiant" if radiant else "Dire"

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 12 LN

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        alive = list(senate)
        n = len(alive)
        while True:
            r_count = alive.count("R")
            d_count = alive.count("D")
            if r_count == 0:
                return "Dire"
            if d_count == 0:
                return "Radiant"
            i = 0
            while i < n:
                if alive[i] == "#":
                    i += 1
                    continue
                c = alive[i]
                j = (i + 1) % n
                steps = 0
                found = False
                while steps < n:
                    if alive[j] != "#" and alive[j] != c:
                        found = True
                        break
                    j = (j + 1) % n
                    steps += 1
                if found:
                    alive[j] = "#"  # ban the nearest standing rival ahead
                i += 1

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 29 LN

class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        Deque<Integer> radiant = new ArrayDeque<>();
        Deque<Integer> dire = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (senate.charAt(i) == 'R') {
                radiant.add(i);
            } else {
                dire.add(i);
            }
        }
        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int r = radiant.poll();
            int d = dire.poll();
            if (r < d) {
                radiant.add(r + n);
            } else {
                dire.add(d + n);
            }
        }
        return radiant.isEmpty() ? "Dire" : "Radiant";
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 24 LN

class Solution {
    public String predictPartyVictory(String senate) {
        char[] alive = senate.toCharArray();
        int n = alive.length;
        while (true) {
            int rCount = 0, dCount = 0;
            for (char c : alive) {
                if (c == 'R') {
                    rCount++;
                } else if (c == 'D') {
                    dCount++;
                }
            }
            if (rCount == 0) {
                return "Dire";
            }
            if (dCount == 0) {
                return "Radiant";
            }
            int i = 0;
            while (i < n) {
                if (alive[i] == '#') {
                    i++;
                    continue;
                }
                char c = alive[i];
                int j = (i + 1) % n;
                int steps = 0;
                boolean found = false;
                while (steps < n) {
                    if (alive[j] != '#' && alive[j] != c) {
                        found = true;
                        break;
                    }
                    j = (j + 1) % n;
                    steps++;
                }
                if (found) {
                    alive[j] = '#'; // ban the nearest standing rival ahead
                }
                i++;
            }
        }
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 45 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED