nguyenmanhthien98's blog

Please help me solve this problem!
By nguyenmanhthien98, 9 years ago, In English

Give a sequence a[1], a[2], ..., a[n] (|a[i]| <= 15000, n <= 50000). Let function q(x, y) = max { sum(a[i]+a[i+1]+...+a[j]), x <= i <= j <= y }. There are m query form x y (1 <= x <= y <= n). (m <= 50000) calculate q(x, y)

Sorry for my bad English.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you give problem's link ?

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

Suppose for 2 given ranges (x, y) and (y+1, z) you know these things:
Maximum subarray starting at x and at y+1
Maximum subarray ending at y and at z.
Maximum subarray that lies completely within the intervals (x, y) and (y+1, z).
Total Sum of range (x, y) and (y+1, z).
Now, try calculating the same things for the range (x, z) using these 8 values.
Once you are done, you can make a segment tree storing these values to give you the answer.

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The solution to this problem is discussed here. The tutorial is written in Russian, use Google for translating.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You could find standard segment tree solution from lots of places, I would like to introduce a new solution under the constraints of this problem.

You can split queries into buckets by their x's. We will calculate answers for each of bucket separately.

Sort all of the queries of current bucket by theirs end points. As you see starts point can change only . End points are increasing, so you can calculate maximum sum interval lies between maximum start point and current end point. Also you can calculate max sum lies at left part with bruteforce O(N). One more thing, left optimal answer's start point can be at left part and endpoint at right part. This time one can just calculate maximum prefix sum of right part and minimum prefix sum of left part. Their difference equals maximum sum of last case.

Overall complexity is

I will add some visual samples soon. Feel free to ask any questions.

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

    Thanks, but the time limit is 0.09s...

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It still has chance because constant factor is too little. I will implement it and share results if get accepted.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Firstly test set has huge inputs with M > 105.

      Secondly time limit is not 0.09 seconds it is 0.23 seconds.

      Fortunalty my still gets AC with 0.19 secs which means 404th rank at best solutions list.(There are 5000 accepted solutions)

      Here is the link to the implementation

      → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I've solved it with segment tree. In each node you need to store the maximum sum starting with the leftmost element, the maximum sum starting with the rightmost element, the maximum sum of consecutive elements in the interval and the total sum. In my solution the variable indicator shows me if the total sum is equal to the maximum sum.

My solution

Ask if you didn't understand something.

→ Reply