Dota2 Senate

How it works

We can track pending bans using a single counter. When we encounter a Radiant senator (R), they either get banned by a waiting Dire (if cnt < 0) or they ban a future Dire senator. Similarly, Dire senators either get banned or ban future Radiant senators. The twist is that when a senator is banned, their surviving opponent is appended to the end to act again in future rounds.

Steps

1. Convert the string to a list and initialize a counter cnt = 0.
2. Iterate through the list (which grows as we append survivors):
   • If the senator is R:
     • If cnt < 0, a Dire senator bans them; append D to the end.
     • Increment cnt (representing a pending Radiant action).
   • If the senator is D:
     • If cnt > 0, a Radiant senator bans them; append R to the end.
     • Decrement cnt (representing a pending Dire action).
3. After processing, if cnt > 0, Radiant wins; otherwise, Dire wins.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Not Understanding the Circular Nature

The senate voting is circular, meaning after the last senator votes, it wraps back to the first. A banned senator in round 1 could have banned someone who would act later in the same round or in subsequent rounds.

Banning the Wrong Opponent

Each senator should optimally ban the nearest opposing senator who would otherwise act before them in the next round. Banning a distant opponent wastes the opportunity and may lead to suboptimal outcomes.

Forgetting to Re-add Surviving Senators

In the queue-based approach, when a senator bans an opponent, the survivor must be re-added to the queue to vote again in future rounds. The index must be incremented by n to maintain proper ordering.

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        senate = list(senate)
        cnt = i = 0

        while i < len(senate):
            c = senate[i]
            if c == 'R':
                if cnt < 0:
                    senate.append('D')
                cnt += 1
            else:
                if cnt > 0:
                    senate.append('R')
                cnt -= 1
            i += 1

        return "Radiant" if cnt > 0 else "Dire"

class Solution {
public:
    string predictPartyVictory(string senate) {
        int cnt = 0, i = 0;

        while (i < senate.size()) {
            char c = senate[i];
            if (c == 'R') {
                if (cnt < 0) {
                    senate.push_back('D');
                }
                cnt++;
            } else {
                if (cnt > 0) {
                    senate.push_back('R');
                }
                cnt--;
            }
            i++;
        }

        return cnt > 0 ? "Radiant" : "Dire";
    }
};