Dota2 Senate

Problem Statement

In the popular game Dota2, two parties, the Radiant and the Dire, are represented in the game's senate. Each senator, aligned with one of these parties, in a provided string representation where 'R' stands for Radiant and 'D' for Dire, participates in decision-making through a unique round-based voting procedure. During each round, senators can either ban another senator, removing them from all subsequent rounds, or declare victory if all remaining senators are from their party. The sequential execution of actions starts from the first senator down to the last in any given round, skipping those who have been banned in previous rounds. The goal is to determine which party will eventually be able to declare victory and impose a change in the game based on strategic bans and declarations made by the senators.

Examples

Example 1

Input:

senate = "RD"

Output:

"Radiant"

Explanation:

The first senator comes from Radiant and he can just ban the next senator's right in round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2

Input:

senate = "RDD"

Output:

"Dire"

Explanation:

The first senator comes from Radiant and he can just ban the next senator's right in round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in round 1.
And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

Constraints

• n == senate.length
• 1 <= n <= 104
• senate[i] is either 'R' or 'D'.

Approach and Intuition

The problem can be understood as a simulation of a round-based game where each player (senator) strategically eliminates an opponent (senator from the opposite party) in each round until only members of one party remain, thereby declaring victory. Here's a step-by-step explanation:

1. Start the simulation with the initial sequence of senators as given in the input string senate.
2. Each senator, depending on if they are Radiant ('R') or Dire ('D'), will choose to disable an opponent senator from the opposite party if possible:
   • If a senator is 'R', they will aim to disable the nearest 'D' senator in the lineup.
   • Conversely, if a senator is 'D', they target the nearest 'R'.
3. Continue this simulation round by round, skipping over any senators that have been previously disabled.
4. The game ends when all active senators belong to only one party. The senators from this party can declare victory.

The complexity of the approach is in managing the list of senators, their states (active or disabled), and simulating each round efficiently without necessarily having to recreate the lineup of active senators every round.

From the examples:

• In the first example with senate = "RD", the Radiant senator immediately bans the Dire senator, leading quickly to a victory for Radiant as there are no opponents left by round two.
• In the second example senate = "RDD", the first Radiant senator bans the first Dire but the second Dire senator disables the first Radiant senator, eventually leading to Dire's victory as they outnumber the opposition in subsequent rounds.

This procedural elimination showcases the game's strategic depth where each senator's decision impacts the potential outcomes in subsequent rounds.

Solutions

class Solution {
public:
    string predictPartyVictory(string senate) {
    
        // Initialize counts for Radiant and Dire senators
        int radiantCount = 0, direCount = 0;
    
        // Initialize counters for the bans applied by each side
        int bansByDire = 0, bansByRadiant = 0;
    
        // Queue to handle the senators sequence
        queue<char> senatorQueue;
        for (char senator : senate) {
            senatorQueue.push(senator);
            if (senator == 'R') radiantCount++;
            else direCount++;
        }
    
        // Process the senators
        while (radiantCount > 0 && direCount > 0) {
            char currentSenator = senatorQueue.front();
            senatorQueue.pop();
    
            // Check senator party and apply rules for bans
            if (currentSenator == 'D') {
                if (bansByDire > 0) {
                    bansByDire--;
                    direCount--;
                } else {
                    bansByRadiant++;
                    senatorQueue.push('D');
                }
            } else {
                if (bansByRadiant > 0) {
                    bansByRadiant--;
                    radiantCount--;
                } else {
                    bansByDire++;
                    senatorQueue.push('R');
                }
            }
        }
    
        // Outcome based on which side has senators left
        return radiantCount > 0 ? "Radiant" : "Dire";
    }
};