Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Ninja and the experiment
MEDIUM
35 mins
Matrices (2D Arrays)
Dynamic Programming
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Matrices (2D Arrays)
-
-
Dynamic Programming
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
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.

Ninja and the experiment

Contributed by
Ratnesh
Medium
yellow-spark
0/80
Avg time to solve 35 mins
Success Rate 60 %
Share
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, Constraints, Images )
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
Reset Code
Full screen
Auto
copy-code
Console