Dota2 Senatution

Introduction

 

In the world of Dota 2, there are two parties: the Radiant and the Dire. The Dota 2 senate consists of senators coming from two parties. The senate wants to make a decision about a change in the Dota 2 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 the right to vote are all from the same party, he can announce the victory and make the decision about the change in the game. 

 

Given a string representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party respectively. 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, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire. Let's see one example, if the senators are "RD" then the result will be "Radiant". Since the first senator comes from Radiant and he can just ban the next senator's right in the round 1. And the second senator can't exercise any rights anymore since his right has been banned. In round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

 

Let's have another example, if the senators are "RDD" then the result will be "Dire". Because the first senator comes from Radiant and he can just ban the next senator's right in round 1. The second senator can't exercise any rights anymore since his right has been banned. The third senator comes from Dire and he can ban the first senator's right in round 1. In round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote. Here are some more examples and the leetcode question:

static void Main(string[] args)
{
    var result = PredictPartyVictory("RD");
    // example 1 : result = "Radiant"
    result = PredictPartyVictory("RDD");
    // example 2 : result = "Dire"
    result = PredictPartyVictory("DRDDR");
    // example 3 : result = "Dire"
    result = PredictPartyVictory("DRRRRD");
    // example 4 : result = "Radiant"
}

Solution

 

This problem can be best solved by a greedy algorithm which is building up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. In simple terms, the next character in the given string will decide the next loop over the party's victory. So the algorithm goes like:

1. Defining two queues for the two parties and storing the index value of their senators.
2. Loop over both the queues and compare the two index values of the senate for the two parties.
3. And keep dequeuing the two queues of the parties.
4. Finally, check any one queue for the results, if the radiant queue has any element then radiant is the winner and vise versa.

Here is the C# code for the algorithm:

public static string PredictPartyVictory(String senate)
{
    var radiants = senate.Select((b, i) => b.Equals('R') ? i : -1).Where(i => i != -1);
    var dires = senate.Select((b, i) => b.Equals('D') ? i : -1).Where(i => i != -1);

    Queue<int> radiantQ = new Queue<int>(radiants);
    Queue<int> direQ = new Queue<int>(dires);

    while (!radiantQ.Count.Equals(0) && !direQ.Count.Equals(0))
    {
        int radiantIndex = radiantQ.Dequeue();
        int direIndex = direQ.Dequeue();
        if (radiantIndex < direIndex)
            radiantQ.Enqueue(radiantIndex + senate.Length);
        else
            direQ.Enqueue(direIndex + senate.Length);
    }
    return radiantQ.Count.Equals(0) ? "Dire" : "Radiant";
}