https://www.codechef.com/problems/PSHTRG Can you please guide me how i answer for the second query in this question?
https://www.codechef.com/problems/PSHTRG Can you please guide me how i answer for the second query in this question?
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Disclaimer: I haven't actually tried submitting this.
First, you should know about the triangle inequality.
Clearly, testing all triples is too slow, so we need a faster way. First, can you solve the problem for a single range in $$$O(n\log{n})$$$?
Sort the numbers.
If we ignore the constraint from the triangle inequality, what three numbers should we pick? If these happen to satisfy the constraint, we are done. Otherwise, one of the three can be ignored from now on. Repeat.
Notice we don't need to repeat many times, since the numbers decrease rapidly. (The maximum halves every other iteration).
Back to the original problem:
Suppose we have a data structure that gets the largest numbers in a range in $$$O(\log{n})$$$ each. Can you solve the original problem now?
How can you use a standard max segment tree to make this data structure?
You can ignore numbers by temporarily setting them to $$$-\infty$$$. ($$$0$$$ would work for this problem.)
This should lead to an $$$O(n\log{n}\log{(\max{A_i})})$$$ solution.
Lemma: If you have the sorted sequence of $$$a[l,r]$$$. If there is an answer then it will be contiguous three elements in the sorted sequence.
Start with retrieving elements from $$$[l,r]$$$ in decreasing order. If $$$1^{st}, 2^{nd}, 3^{rd}$$$ elements doesn't satisfy triangle inequality then we know $$$3^{rd}$$$ element is $$$<1^{st}/2$$$. So we just have to retrieve $$$O(lg(A_{MAX}))$$$ elements per query and we will find the answer among them.
If the question was you are given an array on n integers and if we have to select the sides forming maximum perimeter. Then our procedure would be to sort the array in decreasing order then check for triangle inequality until we find one and just break out of the loop, right? is this what you said. but i don't get this line ""So we just have to retrieve O(lg(AMAX)) elements per query and we will find the answer among them."" won't iterating give time limit?
You won't sort the sequence for every query since it will lead to tle, but retrieve the maximum $$$O(lg(A_{MAX}))$$$ elements using segment tree.