Problem Setter: Ashish Khatkar
Problem Tester: Ambar Pal
Editorialist: Ashish Khatkar and Ambar Pal
Contest link : TOFFEE
Practice link : TOFFEE
Pre-requisites : Segment Tree
We will try to explain what segment tree is in the problem but for more detailed information please visit this link.
In the problem you were given some array containing integers. Than there were queries of the form i j for which you need to tell the minimum value for A[i], A[i+1], …………….. , A[j].
For 30 points n and q were small so you could easily loop from i to j for each query to find minimum in that range.
Pseudocode :
for a = 1 to q:
take i and j as input
ans = A[i]
for b = i+1 to j:
ans = min(ans, A[i])
print ans
Now, if you use this algorithm for 70 points you will get TLE. Why ???
Because constraints were n = pow(10, 6) and q = pow(10, 5), so the running time of the complete algorithm will be n*q which in worst case will be pow(10, 11) which our computers can’t solve in 1 second. So we need a smarter way.
For other 70 points we will need to use a data structure called Segment Tree.
The basic idea behind a segment tree is that we divide the array into smaller and smaller subarrays, each of whose data we can store at one node. For example, if suppose we had an array with 8 elements, we could store the minimum of every two elements, and now given any index-range, we only need to search in at max 4(=8/2) values. For the given constraints, by the way, there was a clever solution using this idea alone(more on this later).
The segment tree improves on this idea in a sense that we now have multiple levels of array-halving steps. So say in an 8-element array, at the first level we store the minimum of every two elements, at the second level, we store the min of every 4 elements and finally at the third level the minimum of all the eight elements is stored. A graphical representation would look like this
How does this help???
Well, lets say we have a query from [0…4]. Now this time we do not have to traverse the array all the way from 0…4, we already have the solution to [0…3] in the left child of [0…7], all we have to do is to find the solution to 4, and then take the minimum of [0…3] and 4. Again, for getting 4, we have to visit a number of nodes equal to the logarithm of 8 to the base 2, which is the height of the tree. So, it can be easily seen that any query on this search tree takes time of the order of log2(N). Q queries will take Qlog2(N), which is nearly of the order of pow(10, 5)*20. This can be solved under 1s.