Dota2 Senate

medium queue greedy

Problem

In the world of Dota2, there are two parties: the Radiant and the Dire. The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game.

Inputsenate = "RDD"

Output"D"

R bans D[1]; D[2] then bans R[0]; D wins.

senate (R/D string)

from collections import deque
def predict_party_victory(s):
    r, d = deque(), deque()
    n = len(s)
    for i, c in enumerate(s):
        (r if c == 'R' else d).append(i)
    while r and d:
        ri, di = r.popleft(), d.popleft()
        if ri < di: r.append(ri + n)
        else: d.append(di + n)
    return "R" if r else "D"

function predictPartyVictory(s) {
  const r = [], d = [], n = s.length;
  for (let i = 0; i < n; i++) (s[i] === 'R' ? r : d).push(i);
  while (r.length && d.length) {
    const ri = r.shift(), di = d.shift();
    if (ri < di) r.push(ri + n); else d.push(di + n);
  }
  return r.length ? "R" : "D";
}

class Solution {
    public String predictPartyVictory(String s) {
        Deque<Integer> r = new ArrayDeque<>(), d = new ArrayDeque<>();
        int n = s.length();
        for (int i = 0; i < n; i++) (s.charAt(i) == 'R' ? r : d).offer(i);
        while (!r.isEmpty() && !d.isEmpty()) {
            int ri = r.poll(), di = d.poll();
            if (ri < di) r.offer(ri + n); else d.offer(di + n);
        }
        return !r.isEmpty() ? "R" : "D";
    }
}

string predictPartyVictory(string s) {
    queue<int> r, d;
    int n = s.size();
    for (int i = 0; i < n; i++) (s[i] == 'R' ? r : d).push(i);
    while (!r.empty() && !d.empty()) {
        int ri = r.front(); r.pop();
        int di = d.front(); d.pop();
        if (ri < di) r.push(ri + n); else d.push(di + n);
    }
    return !r.empty() ? "R" : "D";
}

Explanation

Senators vote in round-robin order, and the smart greedy move is that a senator should always ban the next opponent who would otherwise act. We model this cleanly with two queues holding the turn positions of each party.

First we scan the string and push each senator's index into queue r or queue d depending on whether the character is 'R' or 'D'. The queues stay in order, so the front of each is the soonest that party will act.

While both queues are non-empty, we pop the fronts ri and di. Whoever has the smaller index acts first and bans the other; the winner survives this round and gets to go again later, which we represent by pushing them back with + n (their position in the next cycle). The loser is simply not re-added.

Example: senate = "RDD". R(0) and D(1) face off — R is earlier, so R bans D(1) and rejoins at index 3. Now R(3) vs D(2) — D is earlier, so D bans R, and only D senators remain, giving "D".

Each senator is processed a bounded number of times, so this runs in O(n) amortised time with O(n) space.

Time: O(n) amortised Space: O(n)