jhjfbsbfkbjfnfnfjfj's blog

Segment Tree Doubt
By jhjfbsbfkbjfnfnfjfj, history, 5 years ago, In English

https://www.codechef.com/problems/PSHTRG Can you please guide me how i answer for the second query in this question?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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})$$$?

Hint 1
Hint 2
Hint 3

Back to the original problem:

Hint 4
Hint 5
Hint 6

This should lead to an $$$O(n\log{n}\log{(\max{A_i})})$$$ solution.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply