Ninja and the experiment

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
0 upvote

Problem statement

Ninja performed an experiment 'N' times. In each attempt, he took 'M' readings and noted them down.

For any attempt to be successful, all the readings should be in non-decreasing order.

Due to some malfunctioning of the instrument, the readings were quite inaccurate.

For the evaluations of his work, Ninja has to answer 'Q' queries.

In each query, he is given two integers, 'L' and 'R', and he needs to return 'YES', if he has performed any of the experiments successfully, only considering the readings in the range 'L' to 'R'. Else return 'NO'.

Example: 
Input: 'N' = 3, 'M'=3, 'Q' = 1, READINGS =[[1, 3, 2], [4, 2, 3], [1, 2, 3]] 

For a query, L = 2 and R = 3 (1-based indexing) 

Output: YES

If we only consider the readings in the range [L, R], the readings are [[3, 2], [2, 3], [2, 3]].
The experiment is successful on the second and the third attempt.
Hence we return 'YES'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains two integers 'N' and 'M' denoting the number of attempts and the number of readings in each attempt.

The next 'N' lines of each test case contain 'M' space-separated integers, where the 'i'th line denotes the readings of the 'i'th attempt.
The next line contains the integer 'Q' denoting the number of queries asked.
The next 'Q' lines contain two integers 'L' and 'R' for each query.
Output format : 
For each test case, You need to answer the 'Q' queries.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N*M <= 10^5
1 <= Q <= 10^5
1 <= L,R <= M

Sum of N*M Over all the Test cases <= 10^5 and sum of Q Over all the Test cases <= 10^5 

Time Limit: 1 sec
Sample Input 1 :
2
4 5
1 3 4 5 4
2 1 5 5 4
3 3 2 3 3
5 2 3 2 4
3
1 1
2 5
4 5
1 1
1 
1
1 1
Sample Output 1 :
YES
NO
YES
YES
Explanation Of Sample Input 1 :
For the first case:

'N' = 5, 'M' = 4, 'Q' = 3 

Output:

YES
NO
YES

If we only consider the readings in the range [1, 1], the readings are [[1], [2], [3], [5]].
All the experiments are successful.
Hence we return 'YES'.
If we only consider the readings in the range [2, 5], the readings are [ [3 ,4 ,5 ,4],

[1 ,5 ,5 ,4], [3 ,2 ,3 ,3], [2 ,3 ,2 ,4] ]. All the experiments are unsuccessful. Hence we return 'NO'. If we only consider the readings in the range [4, 5], the readings are [[5, 4], [5, 4], [3, 3], [2, 4]]. The experiment is successful on the third and the fourth attempt. Hence we return 'YES'.

For the Second case:

'N' = 1, 'M' = 1, 'Q' = 1 

Output:

YES

If we only consider the readings in the range [1, 1], the readings are [[1]].
The experiment is successful on the first attempt.
Hence we return 'YES'.
Sample Input 2 :
1
4 5
1 3 4 5 4
2 1 5 5 4
3 3 2 3 3
5 2 3 2 4
3
3 5 
1 3    
1 5
Sample Output 2 :
YES
YES
NO
Hint

For each reading ‘i’ precompute the maximum reading ‘j’ such that all the readings are non-decreasing

Approaches (1)
Dynamic Programming
  1. Initialize a 2D ‘DP’ table of size ‘N’*’M’ and an array ‘rowBest’ of size ‘N’.
    • Run a loop from 'j' = 'M' - 1…0:
    • Again run a loop from 'i' = 0…..'N' - 1:
      • If we are not in the last reading and the current reading is smaller than or equal to the next reading, DP[i][j] = DP[i][j+1]
      • Else DP[i][j] = ‘i’
      • Update rowBest[j] with maximum of DP[i][j] and rowBest[j].
  2. Run a loop from 'i' = '0'... 'K' -1:
    • // Using 0-based indexing here.
    • For each query, if rowBest[R-1] is greater than or equal to ‘R-1’, print ‘YES’.
    • Else print ‘NO’.
Time Complexity

O( N*M + Q ), Where ‘N’ is the number of attempts, ‘M’ is the number of readings in each attempt and ‘Q’ is the number of queries asked.

 

We are iterating over all the reading in O( N*M ) and answering all the ‘Q’ queries in 

O( Q ) time complexity.

 

Hence the time complexity is O( N*M + Q ).

Space Complexity

O( N*M+M ), Where ‘N’ is the number of attempts, and ‘M’ is the number of readings in each attempt.

 

We are using a space of O( N*M ) space to maintain the DP table for each attempt and another O( M ) space to maintain the maxUp table.

 

Hence space complexity is O( N*M+M ).

Code Solution
(100% EXP penalty)
Ninja and the experiment
Full screen
Console