shakil_AUST's blog

DP and Binary Indexed tree problem help

By shakil_AUST, 9 years ago, In English

Can anyone please tell me the process how to solve this problem . Thanx in advance :)

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

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

Fix two rows and consider all cells between them as an single array... From left to right count for each position the subarrays ending in it, that subarray sum is between A and B, this can be done in for fixed rows (with a binary indexed tree), and overall time ...

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

    ... which will probably not fit in the time limit. You should remember about two pointers method when you come up with a binary search solution — perhaps it would make the solution faster.

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

      you are right, but my pass in time... but i have to recognize than two pointer method is even better...

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

    can you explain how to use that BIT ? Thanks!

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

      we are going to solve the problem with 1D array L = {x1, x2, ..., xn}, let be si = x1 + x2 + ... + xn, and s0 = 0. process L from left to right, if we have an structure that allow us to know how many elements are in range [a, b] when we process xi, if it is the last element in a subarray whose sum is in [a, b], then exists sj(j < i) such that a ≤ si - sj ≤ b, or the same si - b ≤ sj ≤ si - a, then we can add to our solution how many sj are in this range, and add si to the structure for future queries. We can use a treap, but if we process and compress in advance all si, we can use a BIT and the implementation would be easier.

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

Your text to link here...

→ Reply