PROBLEM LINK:
Author: Amit Yadav
Tester: Udit Gulati
Editorialist: Jatin Nagpal
DIFFICULTY:
HARD
PRE-REQUISITES:
Merge Sort Tree, Maths, Parabola, Sorting, Binary Search, Trignometry, Differentiation
QUICK EXPLANATION:
First Build a merge sort tree, then for each query from L to R find 2 things:-
- Max element \leq A\sqrt2
- Min element \geq A\sqrt2
as max area is at A\sqrt2. Then compare areas of both, and output the side with max area.
EXPLANATION:
Merge sort tree is just like segment tree(you can read about it in detail from this link) with a difference that at every node you have to store a sorted array of size R-L+1, which contains the values of the range.
First of all, you have to build a merge sort tree, for the values before taking the queries.
Now for each value A of each query, max area is when the third side is A\sqrt2, which can be easily found by differentiation and trignometry (Maths) (or check this video).
Since the area function with third side is an parabola whose max is at A\sqrt2, and limited to the range (0,2A), by merge sort tree, we develop 2 type of queries as explained:-
- For calculating Max value less than or equal to A\sqrt2, first similar to segment tree, you reach in between the range L to R, then by Binary Search at the node, you find it and return the Max.
- For calculating Min value greater than or equal to A\sqrt2, first similar to segment tree, you reach in between the range L to R, then by Binary Search at the node, you find it and return the Min.
Now, simply check which query has the max area, by comparing taking in consideration the range of side i.e. (0,2A).
Time Complexity:
O(N log(N) + Q log(N)[For reaching node] + Q log(N)[For Binary Search at node] )
TESTER’S SOLUTION:
Tester’s solution can be found here