Ninja And Movie Dilemma

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in company
Facebook

Problem statement

Ninja has a list of movies and other details regarding the movies. The details of each Movie with Ninja are [ 'MovieID', 'Rating' of the Movie, Whether Movie is 'Age' Restricted or not, 'Price' for the movie ticket, 'Distance' of the theater]. If Ninja goes to the theater with his family, he will choose movies with 'Age' Restriction, but if he plans to go with his friends, he can select any movie from the movie list. Also, Ninja has constraints on the maximum 'Distance' of the theater he chooses and the 'Price' he pays for each ticket. Can you end the Ninja’s Dilemma?

You have to print the array/list of 'MovieID's from the list of movies, ordered by 'Rating' of the Movie from highest to lowest. For movies with the same 'Rating', order them by 'MovieID' from highest to lowest. Do not forget to consider the 'Age' Restriction factor!! ( 'Age' Restriction will be 1 for 'Age' Restricted Movies and 0 otherwise.)

Note : The list of movies is denoted by the array/list ‘movie’.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ which denotes the number of Movies in the list with Ninja.

The next ‘N’ lines contain the five space-separated integers ‘movie[i][0]’,  ‘movie[i][1]’,  ‘movie[i][2]’,  ‘movie[i][3]’,  ‘movie[i][4]’ , where ‘movie[i][0]’ is the MovieID of the ‘i-th’ movie, ‘movie[i][1]’ is the rating of the ‘i-th’ movie,  ‘movie[i][2]’ indicates whether ‘i-th’ movie is Age Restricted or not,  ‘movie[i][3]’ is the price of the ticket for the ‘i-th’ movie and  ‘movie[i][4]’ is the distance of the theater where the ‘i-th’ movie is being shown.

The next line contains three space separated integers ‘AgeRes’ , ‘MaxPrice’, ‘MaxDistance’ where ‘AgeRes’ will be 1 if Age Restricted Movies has to be selected and 0 otherwise, ‘MaxPrice’ is the maximum amount of price that Ninja can spend on one ticket and ‘MaxDistance’ is the maximum distance ninja can travel from home.
Output Format : 
For each test case, print the array/list of ‘MovieID’s after filtering as discussed above.

Output for every test case will be printed in a separate line.

Note: You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 100
1 <= N <= 10000
1 <= movie[ i ][ 0 ], movie[ i ][ 1 ], movie[ i ][ 3 ], movie[ i ][ 4 ] <= 100000  for each ‘i-th’ movie
0 <= movie[ i ][ 2 ], AgeRes <= 1
1 <= MaxPrice, MaxDistance <= 100000 
All movie[ i ][ 0 ] ( MovieIDs ) are distinct.

Where ‘T’ is the number of test cases.

Where 'N' is the number of movies, ’movie[i][0]’ is the ‘MovieID’ of the ‘i-th’ movie, ‘movie[i][1]’ is the ‘Rating’ of the ‘i-th’ movie,  ‘movie[i][2]’ indicates whether ‘i-th’ movie is ‘Age’ Restricted or not,  ‘movie[i][3]’ is the ‘Price’ of the ticket for the ‘i-th’ movie and  ‘movie[i][4]’ is the distance of the theater where the ‘i-th’ movie is being shown.

Where ‘AgeRes’ will be 1 if ‘Age’ Restricted Movies has to be selected and 0 otherwise, ‘MaxPrice’ is the maximum amount of price that Ninja can spend on one ticket and ‘MaxDistance’ is the maximum distance ninja can travel from home. 


Time limit: 1 sec
Sample Input 1 :
2
3
1 7 1 5 7
2 6 0 4 6
3 6 1 7 4
1 6 7
3
1 7 1 5 7
2 6 0 4 6
3 6 1 5 4
0 6 7
Sample Output 1 :
1 
1 3 2
Explanation of sample input 1 :
In the first test case, only the movie with MovieID 1 passes all the conditions.

In the second test case, all three movies pass the conditions. Movie with MovieID 1 has the highest rating and hence will be first in the answer array. The other two movies have the same ratings but MovieID 3 has a higher ID than MovieID 1 and hence the resulting array will be 1 3 2.
Sample Input 2 :
2
2
1 8 0 5 7 
2 3 1 2 2
1 5 7
5
1 1 1 1 1
2 6 1 4 6    
3 9 0 7 5    
4 7 0 6 5
5 2 1 3 3
0 6 5
Sample Output 2 :
2
4 5 1
Explanation for sample input 2 :
In the first test case, only the movie with MovieID 1 passes all the conditions.

In the second test case, the movie with MovieID 2 does not pass the maximum distance condition while the movie with MovieID 3 does not pass the maximum price condition. All the other three ( MovieIDs 1, 4, 5) pass the conditions. According to the rating of the movies, the order will be [ 4, 5, 1 ] as MovieID 4 has the highest rating (7) , and MovieID 5 follows it with rating (2) and MovieID 1 with the lowest rating (1) will end the sequence.
Hint

Can you filter all the needed movies list by iterating and then compare the filtered movies?

Approaches (1)
Sorting

The basic idea is to iterate the list of movies and filter the movies based on three conditions of Age Restriction, Maximum Price willing to pay for the ticket and the Maximum Distance willing to cover for the theater. If the movie passes through all the conditions, then its ‘Rating’ and ‘MovieID’ is stored as a ‘PAIR’ in the vector/list ‘result’. After the filtering, sort the obtained list of the filtered movies that is the vector/list ‘result’. Now, the vector/list ‘result’ will contain all the filtered movies in the sorted order from lowest to highest and hence reverse the vector/list ‘result’ because we wanted the list with the ordering from highest to lowest and at last return it.

 

Algorithm:

 

  1. Declare the vector/list ‘result’ which will store the pairs of [‘MovieID’, ‘Rating’] of the filtered movies from the movie list.
  2. Declare the vector/list ‘answer’ which will store the required order of ‘MovieID’ which needs to be returned.
  3. Run a loop for ‘i’ to the length of ‘movie’:
    • If ‘AgeRes’ is 1 and ‘movie[i][2]’ is 0:
      • Skip the current movie.
    • If ‘movie[i][3]’ is greater than ‘MaxPrice’:
      • Skip the current movie.
    • If ‘movie[i][4]’ is greater than ‘MaxDistance’:
      • Skip the current movie.
    • Add the [ ‘Rating’, ‘MovieID’ ] pair to the vector/list ‘result’.
  4. Sort the obtained vector/list ‘result’ after adding the filtered movies.
  5. Reverse the vector/list ‘result’.
  6. Store the ‘MovieID’ of every pair from vector/list ‘result’ to the vector/list ‘answer’.
  7. Finally, return ‘answer’.
Time Complexity

O(N * log(N)), where ‘N’ is the total number of movies.

 

First, we are iterating through the all movies which take O(N) time. Then we are sorting the obtained list/vector of movies which takes O(N * log(N)) time. Thus, the overall time complexity will be O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the total number of movies.

 

Since we are storing all the filtered movies in the vector ‘result’ which can take maximum space of the order of ‘N’ and hence, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Ninja And Movie Dilemma
Full screen
Console