New update is available. Click here to update.

Ninja and the experiment

MEDIUM

35 mins

Matrices (2D Arrays)

Dynamic Programming

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Ninja and the experiment

Contributed by

Ratnesh

Medium

0/80

35 mins

60 %

0 upvotes

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 :

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 :

Sample Output 2 :

YES
YES
NO

Autocomplete

Console