Dota2 Senate - Practice Coding Problems

Dota2 Senate - Problem

In the world of Dota2, there are two parties: the Radiant and the Dire. The Dota2 senate consists of senators coming from two parties.

The Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.

Given a string senate representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".

Input & Output

Example 1 — Basic Case

$ Input: senate = "RD"

› Output: Radiant

💡 Note: R senator (position 0) acts first and bans D senator (position 1). Only R remains, so Radiant wins.

Example 2 — Multiple Rounds

$ Input: senate = "RDD"

› Output: Dire

💡 Note: Round 1: R(0) bans D(1), D(2) survives. Round 2: Only D remains, so Dire wins.

Example 3 — Complex Pattern

$ Input: senate = "DDRRR"

› Output: Radiant

💡 Note: Multiple rounds of competition, but R senators eventually outnumber and eliminate all D senators.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

String of senators: 'R' for Radiant, 'D' for Dire

Process

Senators take turns banning opponents in optimal order

Output

Winning party name: 'Radiant' or 'Dire'

Key Takeaway

🎯 Key Insight: Each senator optimally bans the next opponent to maximize their party's chances

Asked in

a Amazon 15 M Microsoft 10

The key insight is that each senator will optimally ban the next opponent in line. The two queue approach efficiently tracks senator positions and determines the winner. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with String Manipulation	O(n²)	O(n)	Simulate each round by iterating through the string and removing banned senators
Two Queue Approach	O(n)	O(n)	Use two queues to track senators from each party and their positions

Simulation with String Manipulation — Algorithm Steps

Iterate through senate string character by character
For each active senator, find and ban the next opponent
Repeat rounds until only one party has active senators

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

All senators are active

Round 1

Each senator bans next opponent

Continue

Repeat until one party wins

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* senate) {
    int len = strlen(senate);
    char* active = (char*)malloc((len + 1) * sizeof(char));
    strcpy(active, senate);
    
    while (1) {
        int rCount = 0, dCount = 0;
        int activeLen = strlen(active);
        
        for (int i = 0; i < activeLen; i++) {
            if (active[i] == 'R') rCount++;
            else dCount++;
        }
        
        if (rCount == 0) {
            free(active);
            char* result = (char*)malloc(5 * sizeof(char));
            strcpy(result, "Dire");
            return result;
        }
        if (dCount == 0) {
            free(active);
            char* result = (char*)malloc(8 * sizeof(char));
            strcpy(result, "Radiant");
            return result;
        }
        
        char* newActive = (char*)malloc((activeLen + 1) * sizeof(char));
        int newIdx = 0;
        int rBans = dCount, dBans = rCount;
        int rBanned = 0, dBanned = 0;
        
        for (int i = 0; i < activeLen; i++) {
            if (active[i] == 'R' && rBanned < rBans) {
                rBanned++;
            } else if (active[i] == 'D' && dBanned < dBans) {
                dBanned++;
            } else {
                newActive[newIdx++] = active[i];
            }
        }
        
        newActive[newIdx] = '\0';
        free(active);
        active = newActive;
    }
}

int main() {
    char senate[100001];
    fgets(senate, sizeof(senate), stdin);
    senate[strcspn(senate, "\n")] = 0;
    
    char* result = solution(senate);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each round can scan the entire string, and we may need multiple rounds

⚠ Quadratic Growth

Space Complexity

O(n)

Need to track which senators are still active

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation with String Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler