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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Dota2 Senate

Number: 649

Difficulty: Medium

Paid? No

Companies: Amazon, Apple, Adobe, Meta, Valve

Problem Description

In the Dota2 Senate problem, there are senators belonging to two parties: the Radiant and the Dire. Each senator can either ban an opposing senator’s rights or, if all remaining senators are from the same party, announce victory. The senators take turns in rounds according to their position in the input string. The task is to simulate the rounds until one party wins, assuming every senator plays optimally.

Key Insights

  • Use two queues to track indices of Radiant and Dire senators.
  • At each turn, compare the front elements (indices) of both queues.
  • The senator with a lower index bans the opponent and then gets appended back to its queue with an updated index (current index + n) to simulate the round-robin system.
  • Continue the process until one queue is empty, meaning one party has been completely banned.
  • This greedy approach efficiently simulates the rounds while maintaining the order and using modulo arithmetic.

Space and Time Complexity

Time Complexity: O(n) – Each senator is processed at most once per round, and their index is updated to simulate rounds. Space Complexity: O(n) – Two queues are used to store the indices of the senators.

Solution

To solve this problem, we use two queues (or lists) to store the indices of senators from the Radiant and Dire parties. On each iteration, we dequeue the front senator from each queue. The senator with the smaller index (i.e., the one who gets to act earlier in the round) bans the other senator and is then enqueued with an updated index (current index + n) ensuring that the senator re-enters in the next round. This process repeats until one of the queues is empty, meaning all senators in that party have been banned. Their optimal moves guarantee that the simulation correctly reflects the outcome if both parties strategize perfectly.

Code Solutions

# Python solution using collections.deque for efficient pops from the left.
from collections import deque

def predictPartyVictory(senate):
    n = len(senate)
    radiant = deque()
    dire = deque()
    
    # Fill queues with senator indices
    for i, s in enumerate(senate):
        if s == 'R':
            radiant.append(i)
        else:
            dire.append(i)
    
    # Process the rounds until one queue is empty
    while radiant and dire:
        # Get the top senator from each party
        r_index = radiant.popleft()
        d_index = dire.popleft()
        
        # The senator with lower index bans the other
        if r_index < d_index:
            # Radiant bans Dire, reinsert Radiant with an updated index for next round
            radiant.append(r_index + n)
        else:
            # Dire bans Radiant, reinsert Dire with an updated index for next round
            dire.append(d_index + n)
    
    # If Radiant queue is not empty, Radiant wins; otherwise Dire wins
    return "Radiant" if radiant else "Dire"

# Example usage:
print(predictPartyVictory("RDD"))
← Back to All Questions