We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Dota2 Senate

Difficulty: Medium

Problem Description

In the world of Dota2, there are two parties: the Radiant and the Dire. The Dota2 senate consists of senators coming from these two parties. The voting procedure for a change in the game is round-based, where each senator can either ban another senator's rights or announce victory if all remaining senators belong to the same party. Given a string representing the party of each senator, predict which party will ultimately announce victory.

Key Insights

  • Senators can either ban an opponent or declare victory if they have majority control.
  • The order of senators matters, as each senator has to make decisions based on the current state of the game.
  • The game can be modeled using a queue to track which senators can still vote.
  • The strategy involves prioritizing the bans based on the order of appearance.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the senate string. Each senator is processed effectively in a single pass. Space Complexity: O(n), for storing the queue of senators who can still vote.

Solution

To solve the problem, we can use a queue to simulate the voting process. Each senator from the Radiant (R) or Dire (D) will attempt to ban an opponent in each round. The senator that gets to vote first will have the advantage in banning an opponent. We keep track of the remaining senators from each party using counters. When one party runs out of senators, the other party wins. By maintaining the order of bans and votes using a queue, we can efficiently determine the winner.

Code Solutions

from collections import deque

def predictPartyVictory(senate: str) -> str:
    radiant = deque()
    dire = deque()
    
    # Populate the queues with the indices of the senators
    for i, s in enumerate(senate):
        if s == 'R':
            radiant.append(i)
        else:
            dire.append(i)

    n = len(senate)
    
    # Process the rounds
    while radiant and dire:
        r_index = radiant.popleft()
        d_index = dire.popleft()
        
        # The senator with the smaller index gets to act first
        if r_index < d_index:
            radiant.append(r_index + n)  # R bans D, R gets to vote again in the next round
        else:
            dire.append(d_index + n)  # D bans R, D gets to vote again in the next round
    
    return "Radiant" if radiant else "Dire"
← Back to All Questions