cylo's blog

What can be the most efficient solution for this?

By cylo, history, 5 years ago, In English

Given n integer coordinates of the form (x, y) and Q queries in which a pair (a, b) is given. For each query output the number of coordinates whose x<=a AND y<=b.

Q<100000 N<1000 1<= x, y, a, b <= 1000

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

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

2D partial sum DP will do the job. DP[i][j] - the number of points with x <= i and y <= j. The recurrence is easy. DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1].

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

    Thanks :)

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

      How to solve if there is query is of OR form i.e. (x<=a || y<=b)?

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

        Using 2D prefix sum you could actually answer any query of type — "How many points exists in range xi <= x <= xf && yi <= y <= yf." After building your 2D Prefix Table you would need to get the sum in a given rectangle. That can be done using the following formula: dp[xf][yf] — dp[xf][yi — 1] — dp[xi — 1][yf] + dp[xi — 1] + dp[yi — 1].

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

sort by X, fenwick tree by Y, NlogN

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

    $$$Q \log N$$$ or how do you answer queries?

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

      Of course, N in my message is (N+Q)

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

        I am stuck in a similiar problem actually. And 2D Prefix Sum can't be done due to Memory restrictions. Could you explain a little further how Sorting + Fenwick would work ? If I sorted by X and the Fenwick by Y, how would I be sure that the corresponding Y in the Fenwick belong to the points in the range [0 — X] ? Thanks !

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

You can strengthen the problem into an online version: dynamically insert and query. For that, use 2D BIT.

→ Reply