Monster Kill

Intuition

From the above problem statement, we can understand that for a particular contiguous subsegment of troops, we have to calculate the sum of the column-wise maximums of powers of every troop in the subsegment. Until this sum of maximums is less than or equal to ‘K’, we can keep increasing this subsegment with the help of two pointers.  

Approach

Let us consider a segment from ‘l’ to ‘r’. To destroy this segment, Rohan will need the following number of shots:

Where P[i][j], is the power of the ‘j’th member in the ith troop.

If this sum is less than or equal to ‘K’, Rohan can kill the segment of troops from ‘l’ to ‘r’. In this case, we will simply increase the right border of the segment, i.e., increase ‘r’, and in the other case, when the sum is greater than ‘K’, we will increase the left border, i.e., increase ‘l’. 

And we will keep updating the answer after every change in the segment. 

In order to find the maximum power from a segment, we can use a priority queue, as it can give us the troop with maximum power for a particular index with the cost of just O(log(N)). Else we will need to iterate through all the members of the troops to obtain the member with the maximum power.

Below is the implementation of the above approach.

Implementation

// Program to solve the kill monsters problem.
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// Function to return the vector of the number of shots.
vector<int> killMonsters(int N, int M, int K)
{
      // Variables to implement two pointers.
      int l = 0, x, r, mx = 0;

      /*
            Priority queue to prioritize the
            more powerful members.
      */
      priority_queue<pair<int, int>> pq[M];

      /*
            Vector to store the number of shots
            for each type of member.
      */
      vector<int> shots(M, 0);

      /*
            Iterating through each troop and
            updating the maximum length segment.
      */
      for (int i = 0; i < N; i++)
      {
            // Second pointer.
            r = i;

            // Pushing the powers in the priority queue.
            for (int j = 0; j < M; j++)
            {
                  // Input of powers.
                  cin >> x;
                  pq[j].push({x, i});
            }

            /*
                  Updating the range of the segment
                  satisfying the given conditions.
            */
            while (l <= r)
            {
                  int sum = 0;
                  for (int j = 0; j < M; j++)
                  {
                        while (pq[j].top().second < l)
                              pq[j].pop();
                        sum += pq[j].top().first;
                  }
                  if (sum <= K)
                        break;
                  l++;
            }

            // Updating the answer vector after every change.
            if (r - l + 1 > mx)
            {
                  mx = r - l + 1;
                  for (int j = 0; j < M; j++)
                        shots[j] = pq[j].top().first;
            }
      }

      // Finally returning the number of shots.       
return shots;
}

// Main function.
int main()
{
      // Input of the variables.
      int N, M, K;
      cin >> N >> M >> K;

      // Vector to store the number of shots.
      vector<int> shots = killMonsters(N, M, K);

      // Final output.
      for (int i = 0; i < M; i++)
            cout << shots[i] << " ";

      return 0;
}

Input

4 2 7
1 2
1 3
2 2
3 4

Output

3 4 

Complexity Analysis

Time Complexity

O(N * M * log(M)), where ‘N’ and ‘M’ are the number of troops and number of members in every troop respectively.
Explanation: In the function killMonsters(), we are iterating through each troop and adjusting the length of the segment with the help of two pointers. So, iterating through ‘N’ troops and then ‘M’ members give us the complexity of O(N * M), but we are using a priority queue to prioritize the powers, which increases a factor of log(M) into the final time complexity. Thus the final time complexity is O(N * M * log(M)).

Space Complexity 

O(N * M), where ‘N’ and ‘M’ are the numbers of troops and number of members in every troop, respectively.
Explanation: We use the priority queue to store the powers of the ‘M’ members of every ‘N’ troop; thus, space complexity sums up to O(N * M).

FAQs

1. Why are we using two pointers method in this program?
   While finding the current longest valid subsegment after each iteration, it becomes easier when you have two variables that can be slid towards left or right to expand or compress the range. So this is the reason we are using two-pointers.
    
2. What is the use of priority queue in the above program?
   To find the number of shots for destroying the troops of the current segment, we need to extract the maximum power among members from each index, which can be efficiently done with the help of a priority queue with a cost of O(log(N)).
    
3. What is the time complexity of the above algorithm?
   The time complexity of the above algorithm can be calculated by analyzing the most costly function, i.e., killMonsters(). So from the analysis of the above function, we can conclude that the overall time complexity of the above program is O(N * M * log(M)).
    
4. What is the space complexity of the above algorithm?
   We used a priority queue to store the powers of the ‘M’ members of every ‘N’ troop which sums up to O(N * M).
    
5. Why are we inserting elements in pairs to the priority queue?
   We are inserting pairs so that we can have a track of indices, that which troop this power belongs to. This helps us to distinguish the powers of a particular troop from other troops.  

Key Takeaways

The above problem is an interesting competitive programming problem involving the use of two-pointers. Solving these types of problems is the key to boosting your problem-solving skills. 

Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.

Happy Coding!