DCP-19: Multiplication Interval Back to All Problems

Hard Data Structures > Segment Tree/Interval Tree


Software Engineering requires knowledge about algorithms, data structures, design pattern, UML diagram, software development approach. The main focus of all this knowledge is to make the software more efficient, robust and workable. Because if you develop a software which does something slower than human, then what is the point of building that software? Below, there is a problem which can be done with simple looping to all the elements of the array for each query, but that is not efficient, can you make it efficient? Given an array with **N** elements, indexed from **1** to **N**. Now you will be given some queries in the form **I J**, your task is to find the minimum multiplication value of all possible interval between index **I** to **J**, and also for that multiplication value you need to find the longest interval. Lets say we have an array A size 5, indexed from 1 to 5. Now the multiplication value of the interval [1,3] = A[1]*A[2]*A[3] Input: ------ Input starts with an integer **T (≤ 5)**, denoting the number of test cases. The first line of a case is a blank line. The next line contains two integers **N (1 ≤ N ≤ 10^5), q (1 ≤ q ≤ 10^5)**. The next line contains **N** space separated integers forming the array. There integers range in **[0, 10^5]**. The next **q** lines will contain a query which is in the form **I J (1 ≤ I ≤ J ≤ N)**. Output: ------- For each test case, print the case number in a single line. Then for each query you have to print a line containing three numbers, first one is the minimum multiplication value of all possible interval between index **I** to **J**, second and third number will point to the start index and end index of the interval which is longest interval between index **I** to **J** having the minimum multiplication value. If there are multiple intervals having the minimum multiplication value as well as the longest then print the interval which starts earlier. See the output section for further understanding Sample Input ------------ 2 5 3 2 22 10 12 2 2 4 4 5 1 5 2 1 10 10 1 2 Sample Output ------------- Case 1: 10 3 3 2 5 5 2 1 1 Case 2: 10 1 1 **Notes** For the first test case, for query 2, 4, these intervals are possible: [2,2] = 22 [2,3] = 22 * 10 = 220 [2,4] = 22 * 10 * 12 = 2640 [3,3] = 10 [3,4] = 10 * 12 = 120 [4,4] = 12 Among all of these intervals, [3,3] interval have the minimum multiplication value. For the Second test case first query [1,2] we have two longest intervals with minimum multiplication value [1,1], [2,2]. So print [1,1] as it starts earlier.


Problem Setter:

Ahmad Faiyaz

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 4.00
Go 4.00
Java 4.00
JavaScript 4.00
Objective-C 4.00
Perl 4.00
PHP 4.00
Python 4.00
Python3 4.00
Ruby 4.00
VB.Net 4.00

Problem Stats

17/128

Solve/Submission

Ranking

# User Language Timing
01 Morass Cpp14 0.32s
02 feodorv C 0.36s
03 Masum_ice Cpp14 0.53s
04 Mahin_shefat Cpp14 0.54s
05 seyedssz Cpp14 0.61s
06 moshiur_cse15 Cpp14 0.63s
07 jalal Cpp 0.65s
08 ovis96 Cpp14 0.83s
09 skmonir Cpp14 0.85s
10 lightlessShadO Cpp14 1.01s
11 Hasinur_ Cpp14 1.52s
12 nasif2587 Cpp14 1.63s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support