Day 22 | Fighting Tournament | C++

Today I found a gem of a question, it is fun, interesting, and feels good to implement.

You can attempt the problem yourself first here - Fighting Tournament

This question seems tough but is actually not that hard.

Since the player with more power wins a match and remains in front for the next match, there will come a time when the player with power = n will come and will start winning all the matches as no matter who it plays against, it will have maximum power.

So let's say player P is the one with power n and comes to play the first match after the R rounds. Then queries with rounds > R are quite simple

if player we are talking about have the maximum power then answer is rounds - R (as it won all the matches)

and if it is not then we can store matches won for all players upto match R

So we need to actively solve it for queries with rounds <= R

How we can store data of who won how many matches upto round R

map<int,int> victories;
int player_in_front = a[0];
for(int i = 1; i <= R; i++){
        int winner = max(player_in_front, a[i]);
        victories[winner]++;
        player_in_front = winner;
}

Before we go on, let's discuss two types of solutions when it comes to solving queries problems

Online Solutions and Offline Solutions

Online solutions - Have you ever been in a viva exam, teacher asks a question and you have to answer it before recieving another question. Online solutions are such - you are asked a query and you have to answer it before another query. Generally you need this kind of solution when your previous queries can affect later queries or in other words if we solve queries in some other order than given, it will be incorrect Consider an array where we are given query to find maximum element in range [l,r] and change it to it's sqrt. So as we keep doing it, maximum element keep changing thus we need to solve queries in given order only.

Offline solutions - This solution is like homework, you can start with easiest, hardest or whatever your choice is. Just remember to properly index the answer.

For example, if you have to find maximum in range [l,r], then you can solve any query at anytime and put answer in correct place in answer array.

Here you can notice that, it doesn't matter which query we solve first. Hence we solve the problem offline.

We notice that in building victory map for R rounds, we build it round by round. Thus when we build round for round i we can answer the queries with rounds = i and save it in the answer array

So we can solve it like this

1. Sort the queries by rounds. Queries with smaller rounds should be before, so we answer them first while building victory map

2. Calculate rounds_for_max_player_first_round

3. Build victory map upto rounds_for_max_player_first_round and also answer queries for the given round

4. Answer the queries for rounds > rounds_for_max_player_first_round

Let's implement it step by step

Note: We will use this struct for queries

struct query{
    int playerIndex;
    int rounds;
    int queryIndex;
};

Sort queries by rounds

Let's say you want to sort any vector arr, you can use this snippet

sort(arr.begin(),arr.end()); 

But there is one requirement, the datatype which arr contains should have their operator< defined. It is generally done for pair, string and other primary data types in C++.

If you want to learn how to define your own for classes and strucutures - Check this out

If you don't want to overload operator, you can also passing comparison function like this

 sort(queries.begin(), queries.end(), [](query left, query right){
        return left.rounds < right.rounds;
    });

Quick hack to understand-

If we return true, left parameter will remain in left, else it will go to right in array.

Calculate rounds_for_max_player_first_round

We can do it like this

for(int i = 0; i < n; i++){
        if(a[i] == n){
            rounds_for_max_player_first_round = i - 1;
            break;
        }
    }

Build victory map upto rounds_for_max_player_first_round and also answer queries for the given round

We discussed building victory map earlier, let's add calculate adding answer for queries

int player_in_front = a[0];
    for(int i = 1; i <= rounds_for_max_player_first_round; i++){
        int winner = max(player_in_front, a[i]);
        victories[winner]++;
        player_in_front = winner;
        while(queriesSolved < queries.size() && 
                              queries[queriesSolved].rounds == i){
            int playerIndex = queries[queriesSolved].playerIndex;
            int player = a[playerIndex-1];
            ans[queries[queriesSolved].queryIndex] = victories[player];
            queriesSolved++;
        }
    }

Answer the queries for rounds > rounds_for_max_player_first_round

As discussed in start

 while(queriesSolved < queries.size()){
        int playerIndex = queries[queriesSolved].playerIndex;
        int player = a[playerIndex-1];
        int rounds = queries[queriesSolved].rounds;
        if(player == n){
            ans[queries[queriesSolved].queryIndex] = rounds - rounds_for_max_player_first_round;
        }else{
            ans[queries[queriesSolved].queryIndex] = victories[player];
        }
        queriesSolved++;
    }

If you like my content, please leave a message or like. That makes me happy :D

You can find my complete implementation here.