Save The World

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.

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.

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.

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

Test Case 1 : Given ‘N’ = 4, ‘K’ = 3, ‘destination’ = 10 and ‘time’ = 3. Avengers position = [1, 2, 3, 4] Avengers speed = [4, 8, 6, 3] Fourth Avenger can easily reach 10 from 4 in 3 hours as he can travel 9 km in 3 hours. Third Avenger can easily go 10 from 3 in 3 hours as he can travel 18 km in 3 hours. Also, as Third Avenger is running faster than the fourth Avenger, he will cross the fourth Avenger and reach the time quantum together. Second Avenger can easily reach 10 from 2 in 3 hours as he can travel 24 km in 3 hours. He will cross paths with the third Avenger and reach time quantum together. We have three Avengers that can reach the time quantum. So we don’t need any swaps. Test Case 2 : Given ‘N’ = 3, ‘K’ = 3, ‘destination’ = 10 and ‘time’ = 5. Avengers position = [1, 4, 5] Avengers speed = [1, 5, 2] No matter how many swaps we do, we cannot save at least 3 Avengers. So we need to print -1.

Test Case 1 : Given ‘N’ = 1, ‘K’ = 1, ‘destination’ = 10 and ‘time’ = 3. Avengers position = [1] Avengers speed = [7] First Avenger can easily reach 10 from 1 in 3 hours as he can travel 21 km in 3 hours. So we need to print 0 Test Case 2 : Given ‘N’ = 3, ‘K’ = 2, ‘destination’ = 8 and ‘time’ = 5. Avengers position = [1, 2, 5] Avengers speed = [8, 1, 2] Third Avenger can easily reach 10 from 5 in 5 hours as he can travel 10 km in 5 hours. Second Avenger cannot reach 10 from 2 in 3 hours as he can travel 5 km in 5 hours. So we will swap the second Avenger with the first Avenger as the first avenger can reach 10 from 2. So we need to print 1.

Greedy Approach

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

Time Complexity

O(N), where ‘N’ is the total number of elements in the given array.

Here, we are running a single loop that takes O(N) time.

Space Complexity

O(1).

No extra space is being used.

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation of Sample Input 1 :

Sample Input 2 :

Sample Output 2 :

Explanation of Sample Input 2 :