AJ__20's blog

NEED OPTIMAL SOLUTION
By AJ__20, history, 18 months ago, In English

I was given a question with integer array A of size N, And asked to find answer for Q queries. Each query consists of (L, R, Min, Max). One need to find the minimum sum in the given range(L, R) with atleast 'Min' element and atmost 'Max' elements should be in the minimum sum. Constraints : 1 <= N <= 1e5, 1 <= Q <= 1e5, 1 <= Testcases <= 1e5. I tried brute force approach and got TLE. I searched the internet for the optimal approach and couldn't find the answer, so could anyone explain how to approach this problem? Edit : All the queries are available to function as a parameter when the function is invoked.

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

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

Two questions:

  1. Do you mean that we need to choose at least $$$min$$$ elements and at most $$$max$$$ elements from the segment $$$[l, r]$$$?
  2. Can the array contain negative elements?
→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    (1).We need to choose some elements from the segment [l, r] such that the no.of.elements chosen should be in the range[Min, Max]. Eg: If array A is [5, -2, 10, -4, -11, 15] and Query is (0, 3, 2, 3) L -> 0 (0-based indexing) R -> 3 (0-based indexing) Min -> 2 (you need to pick atleast 2 elements) Max -> 3 (you can pick atmost 3 elements) So if we choose (-11, -4, -2) we will get minimum sum of -17. (2).Yes, the array consists of negative elements.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I think this can be solved by persistant segment tree

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Thanks for the advice. Could you please share some links to study the persistant segment tree?

        → Reply