faiyaz26's blog

12939 — Keep Fit! Solution Idea ??
By faiyaz26, history, 9 years ago, In English

Can anyone help me with this problem ?

12939 — Keep Fit!

I have followed the idea of this problem to solve the problem.

But the complexity becomes Q * NlogN , which gives TLE.

Any optimized idea ?

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

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

Have you submitted the solution? The Time Limit is 15s, so try to submit it.

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

    Yes!! I have submitted it during the contest.

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

If the queries are of type [i..j] you can try using Mo's Algorithm to sort the queries: here

This allows solving the Q queries with O(N sqrt(N)) insertions / deletions of points.

Now, you have to think of a Data Structure that should be able to insert points, delete points, and query how many points are within Manhattan distance <= d. I believe you could use a QuadTree for that matter, and just keep the required number dynamically at each step.

For example:

When inserting a point, first query how many points are within Manhattan distance <= d from that point (which can be done using a QuadTree or KD-Tree -> see if a whole region intersects with the needed square, if it is completely within the square then just add all the points in the region -- QuadTrees should help you do that, if not recurse), and add this number to TOTAL. When deleting a point, query the same thing and then subtract from TOTAL (excluding the point itself, of course). I believe 2d range trees have a complexity of O(sqrt(N)), although I am not very sure. Total complexity should be O(N*Q), although in practice it should go better :).

If you do not understand what square I am reffering to, here is a drawing:

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

    Check something else out -> if you can make you QuadTree represent 45-degrees-rotated squares instead of normal squares, you are golden — the queries get very fast, you just have to check squares against squares. Rotating all the points 45 degrees against the origin would also be an option, although the precision issue that this option gives should make you very cautious in your implementation

    → Reply