Last Updated: 15 Feb, 2021
Save The World
Easy
Asked in company
This story is about an alternate timeline of Avengers Endgame.
Thanos becomes inevitable in this timeline by acquiring all infinity stones. Now Thanos wants to kill all the universe. Thanos launched an attack to kill all the world at once by snapping his fingers. The world is now going to explode in ‘time’ hours.
To save the world, Avengers decided to time travel using time quantum. There are ‘N’ avengers running towards the time quantum. Each Avenger is running with some speed from some initial position. If an Avenger fails to reach the ‘time quantum’, then he/she will die.
Doctor Strange wants to save as many Avengers as possible by swapping initial positions of Avengers adjacent to each other.
Doctor Strange went ahead of time and saw all 1,44,89,121 results of the Thanos vs Avengers battle. He found that he needs to save at least ‘K’ Avengers to defeat Thanos.
Doctor Strange has very little energy left to save the world by doing the minimum number of swaps.
Doctor strange is busy assembling all the Avengers, so he asked you to help him.
The fate of the world lies in your hand.
Note :
The initial positions of all the Avengers are sorted in increasing order and no two Avengers have the same initial position.
If an Avenger crosses the other Avenger, they will travel together with Avenger’s speed moving ahead i.e. with the speed of slower Avenger.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.
The first line of each test case contains four space-separated integers ‘N’, ‘K’, ‘destination’ and ‘time’ representing the total number of Avengers, required number of Avengers to be saved, the position of time quantum, and the time remaining to destroy the world in hours.
The next line contains ‘N’ single-spaced elements sorted in increasing order, representing Avenger's initial positions.
The next line contains ‘N’ single-spaced elements, representing Avengers speed in km/hour.
Output Format :
For each test case, print the minimum number of swaps required to save at least ‘K’ Avengers. Print -1 if it is impossible to save ‘K’ Avengers.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= K <= N <= 5000
1 <= destination, time <= 10^9
1 <= Speed[i] , Position[i] <= 10^9
Where Position[i] is the initial position of the Avengers and Speed[i] is the initial speed of the Avengers.
Time Limit: 1 sec
Approaches
The idea here is to traverse the list of Avengers from right to left, and for each Avenger, we will calculate the maximum distance he/she can cover. If this maximum distance is greater than equal to the required distance (distance from the initial position to time quantum), we will increment the count of saved Avengers by 1. Else, we will increase the count of the Avengers which can’t be saved.. If we have encountered an Avenger that can be saved but we have ‘X’ number of Avengers which cannot be saved ahead of him then we will And ‘X’ to our ‘answer’ as we need to bring the Avenger ahead of all Avengers who cannot be saved, for that we need ‘X’ swaps.
Algorithm
- Declare a variable ‘answer’ to calculate the minimum number of swaps required to save at least ‘K’ Avengers,’ ‘saved’ to keep track of total saved Avengers so far, and currentAhead’ to keep track of Avengers that are ahead and cannot be saved.
- Run a loop from i = ‘N - 1’ to 0
- Calculate the distance required to reach time quantum by current Avenger, say ‘distanceRequired’ as ‘Destination’ – ‘Pos[i]’ . Here, Destination is the Position of time quantum and ‘Pos[i]’ is position of the current Avenger.
- Calculate the maximum distance which current Avenger can cover in given time, say ‘canCover’ as speed[i] * time. Here ‘time’ is the time after which the world will get destroyed and ‘speed[i]’ is the speed of the current Avenger.
- If ‘canCover’ >= ‘distanceRequired’ then increment ‘saved’ by 1 and add ‘currentAhead’ to the answer.
- Else, increment ‘currentAhead’ by 1.
- If saved equal ‘K’, then break the loop.
- If saved is less than ‘K’, then return -1 as we cannot save at least ‘K’ avengers.
- Finally, return the ‘answer’.