Dota2 Senate
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
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.
Senate RRDDD. Two turn-order queues: Radiant [0,1], Dire [2,3,4] — whichever front ticket is earlier acts next.
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"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 += 1class 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";
}
}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++;
}
}
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED