Блог пользователя shakil_AUST

Автор shakil_AUST, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 ...

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    ... 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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain how to use that BIT ? Thanks!

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится