Dota2 Senate

Problem Description

In the world of Dota2, there are two senate factions: the Radiant and the Dire.

The Dota2 senate consists of senators who want to make a design change. Each senator can vote in a turn-based round. On each senator’s turn, they can:

• Ban one senator’s right: A senator can make another senator lose all voting rights in this and all subsequent rounds.
• Declare victory: If a senator finds that the senators who have voting rights are all from the same faction, they can declare the victory and decide on the change.

Given a string senate representing each senator’s faction, return "Radiant" or "Bob" (wait, "Dire") depending on which faction wins.

Examples

Constraints

• n == senate.length
• 1 ≤ n ≤ 10⁴
• senate[i] is either 'R' or 'D'.

Optimal Strategy: Ban the Next Opponent

A senator’s optimal move is always to ban the very next opponent who has not yet voted in the current round. This prevents that opponent from acting later in this round.

To simulate this efficiently:

1. Initialize two queues, radiant and dire, storing the original index positions of each faction’s senators.
2. In each step, compare the front of both queues:
   • The senator with the smaller index rIdx acts first. They ban the opponent at dIdx.
   • The acting senator goes back to the end of their queue to act in the next round at index rIdx + n.
   • The banned senator is popped and does not rejoin.
3. Repeat until one queue is empty. Return the faction of the remaining queue.

Solution: Two Queues Simulation

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.offer(i);
            } else {
                dire.offer(i);
            }
        }

        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int rIdx = radiant.poll();
            int dIdx = dire.poll();

            // smaller index senator bans the larger index senator
            if (rIdx < dIdx) {
                radiant.offer(rIdx + n); // moves to next round
            } else {
                dire.offer(dIdx + n);
            }
        }

        return radiant.isEmpty() ? "Dire" : "Radiant";
    }
}

from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        radiant = deque()
        dire = deque()

        for i, char in enumerate(senate):
            if char == 'R':
                radiant.append(i)
            else:
                dire.append(i)

        while radiant and dire:
            r_idx = radiant.popleft()
            d_idx = dire.popleft()

            # smaller index senator bans the other
            if r_idx < d_idx:
                radiant.append(r_idx + n)
            else:
                dire.append(d_idx + n)

        return "Radiant" if radiant else "Dire"

#include <string>
#include <queue>

class Solution {
public:
    std::string predictPartyVictory(std::string senate) {
        int n = senate.length();
        std::queue<int> radiant;
        std::queue<int> 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 rIdx = radiant.front(); radiant.pop();
            int dIdx = dire.front(); dire.pop();

            if (rIdx < dIdx) {
                radiant.push(rIdx + n);
            } else {
                dire.push(dIdx + n);
            }
        }

        return radiant.empty() ? "Dire" : "Radiant";
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the number of senators. Each round at least one senator is banned, and queue operations are O(1).
• Space Complexity: O(N) to store senator indices in the queues.

← All Problems