Problem Description

The Dota2 Senate problem presents a simulation scenario involving two parties: Radiant (R) and Dire (D). The senate is represented as a string senate, where each character is either 'R' or 'D', indicating the party of the senator at that position.

The process follows these rules:

• Each round, senators take turns in the order given by the string.
• When a senator's turn comes, if they are still active (not banned), they can ban any other senator from the opposing party who is still active. Banned senators lose all future turns.
• The rounds continue in a circular manner until all senators from one party have been banned.
• The party with remaining senators is declared the winner: return "Radiant" or "Dire".

• There will always be at least one senator from each party at the start.
• Each senator acts only once per round, and cannot act if banned.
• There is exactly one valid outcome.

Thought Process

At first glance, this problem appears to require simulating the banning process as described. A brute-force approach would be to keep track of active senators and, for each, ban an opponent in each round. However, this could become inefficient as the number of senators increases, due to repeated scanning and removal.

To optimize, we notice that the banning process is essentially a queueing system: senators act in order, and after acting, they rejoin the end of the queue if they are not banned. If we can efficiently track which senator is next from each party, and always ensure the earliest one acts first, the simulation becomes much more efficient.

The key realization is that we don't need to keep the entire senate string, but rather the indices of the remaining senators from each party. We can use two queues—one for Radiant, one for Dire—to represent their turns. Each time a senator acts, they "ban" the first senator from the other party whose turn comes after theirs, and then rejoin the end of the queue (with their index incremented by the length of the senate, to simulate wrapping around).

Solution Approach

The optimized approach uses two queues to track the positions of active senators from each party:

• Step 1: Initialize two queues, one for Radiant (R) and one for Dire (D), storing the indices of the senators.
• Step 2: While both queues are non-empty, compare the front indices:
  • The senator with the smaller index acts first (since the round is in order).
  • This senator bans the opponent at the front of the other queue (removing them).
  • The acting senator is placed back at the end of their queue, with their index increased by the total length of the senate (to simulate the circular rounds).
• Step 3: Repeat until one queue is empty. The party with remaining senators is the winner.

This method ensures each senator acts in order, and efficiently simulates the banning process without repeatedly scanning the senate string.

Example Walkthrough

Let's consider the input senate = "RDD":

• Initialize: Radiant queue = [0], Dire queue = [1, 2]
• Round 1:
  - Radiant at index 0 vs Dire at index 1
  - Radiant (index 0) acts first (0 < 1), bans Dire at index 1
  - Radiant re-enters queue at index 0 + 3 = 3
  - Queues now: Radiant = [3], Dire = [2]
• Round 2:
  - Radiant at index 3 vs Dire at index 2
  - Dire (2 < 3) acts first, bans Radiant at index 3
  - Dire re-enters queue at index 2 + 3 = 5
  - Queues: Radiant = [], Dire = [5]
• Now, Radiant queue is empty. Dire wins.

Time and Space Complexity

Brute-force approach: For each round, you may need to scan the entire senate list to find the next active senator, leading to O(n²) time in the worst case.

Optimized queue-based approach:

• Each senator is enqueued and dequeued at most once per round.
• Each senator can only be banned once, so the total number of operations is proportional to the number of senators.
• Thus, time complexity is O(n), where n is the length of the senate string.
• Space complexity is also O(n), due to the two queues used to track indices.

Summary

The Dota2 Senate problem is elegantly solved by modeling the process with two queues, tracking the order and position of each party's senators. This avoids unnecessary repeated scans and simulates the banning process efficiently. By always comparing the earliest available senator from each party, we maintain the correct turn order and ensure a linear-time solution.

Code Implementation

from collections import deque

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

#include <queue>
#include <string>
using namespace std;

class Solution {
public:
    string predictPartyVictory(string senate) {
        int n = senate.size();
        queue<int> radiant, dire;
        for (int i = 0; i < n; ++i) {
            if (senate[i] == 'R')
                radiant.push(i);
            else
                dire.push(i);
        }
        while (!radiant.empty() && !dire.empty()) {
            int r = radiant.front(); radiant.pop();
            int d = dire.front(); dire.pop();
            if (r < d)
                radiant.push(r + n);
            else
                dire.push(d + n);
        }
        return radiant.empty() ? "Dire" : "Radiant";
    }
};
      

import java.util.*;

class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        Queue<Integer> radiant = new LinkedList<>();
        Queue<Integer> dire = new LinkedList<>();
        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";
    }
}
      

var predictPartyVictory = function(senate) {
    const n = senate.length;
    const radiant = [];
    const dire = [];
    for (let i = 0; i < n; i++) {
        if (senate[i] === 'R') radiant.push(i);
        else dire.push(i);
    }
    while (radiant.length && dire.length) {
        const r = radiant.shift();
        const d = dire.shift();
        if (r < d) radiant.push(r + n);
        else dire.push(d + n);
    }
    return radiant.length ? "Radiant" : "Dire";
};