[Problem] 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. Now 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. Then if there are n senators, the size of the given string will be n.

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".

Description

The problem has a lot of context, including those that are not necessary to solve the problem. To simplify the problem:

1. A string only consisting of R and D will be given.
2. A particular party wins if only senators of that party are eligible in the senate after all eligible senators have exercised their rights. A senator is eligible to exercise their right if they are not banned by a previous senator's action.
3. Voting is done from left to right. After the rightmost senator has voted, the voting process starts again from the leftmost senator, marking the beginning of the next Round. A senator cannot participate in any Round after they have been banned.
4. The party that survives after all voting is completed, wins.

Example

Input: senate = "RD"
Output: "Radiant"

Input: senate = "RDD"
Output: "Dire"

Input: senate = "DDRRR"
Output: "Dire"
Turn1: D at index 0 gets the turn, and will remove R at index 2. D adds at the end of the queue.
DRRD
Turn2: D at index 0 gets the turn, and will remove R at index 1. D adds at the end of the queue.
RDD
Turn3: R at index 0 gets the turn, and will remove D at index 1. R adds at the end of the queue.
DR
Turn4: D at index 0 gets the turn, and will remove R at index 1. D adds at the end of the queue.
D
So, D wins.

Approach

Take two arrays rIndices and dIndices to keep track of the indices of the eligible senators separately in sorted order. Take the first element (which represent indices of senators) of rIndices and dIndices and compare them.

We can continue to eliminate from one of each until there is only one remaining queue, and return the party related to that queue.

The minimum of these two will be the turn. It will not get banned, at least as of now. Thus, it will again be added to the array. Since it should get turn in the next round, we will add it to the end of the array, and the index will be turn + n because, in the next round, this would be the first index.

The maximum of these two will be the next target to ban. It will get banned. Thus, it will not be added back to the array.

Solution

from collections import deque

class Solution(object):
    def predictPartyVictory(self, senate):
        rq = deque()
        dq = deque()

        for i in range(len(senate)):
            if senate[i] == 'R':
                rq.append(i)
            else: dq.append(i)
        
        while rq and dq:
            rt = rq.popleft()
            dt = dq.popleft()
        
            if dt < rt:
                dq.append(dt + len(senate))
            else:
                rq.append(rt + len(senate))

        return "Radiant" if rq else "Dire"