MR.AC's blog

How to find the distance between two pointers?
By MR.AC, 2 years ago, In English

I came across an issue when solving problem C in today's contest. I was trying to find the distance between two pointers (by subtracting) in a set to determine the number of elements between those two pointers. However, I got an error. Is there a way to find this distance?

Submission (under "if(t == 3)")

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

Comments Comments (18)
| Write comment?
»
2 years ago, # |
  Vote: I like it -16 Vote: I do not like it

let's consider that you have two pointers , the left one in position l and the right one in position r , then if you want the number of elements there (including the pointers) it is r-l+1 , if it was without them it is r-l-1 , and if it was without one of them it is r-l

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

    but you have to make sure that l<r or l<=r (as you want) so it is a positive value

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

      Oh my bad I knew that but the issue was not about that, it was about a compilation error.

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

use ordered set(policy based set)

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

    That might be a good idea. If I am trying to find elements in range L to R, should I do something like order_of_key(R+1) — order_key(L)? (reminds me of prefix sums)

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

      This correctly gives #of rooks between rows L,R, but that's different than "at least one rook in each row in range [L,R]" which is what the problem asks

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

        However, I am using a set combined with a multiset to ensure that only distinct rooks are stored. (Please check my most recent submission) Therefore, in my case, it can be used to check if the condition is satisfied.

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

          Ah true, my bad

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

            I understand why you thought that, as I didn't mention anything about it in my post.

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

You can't do it with a set, because a set doesn't have random access iterators.

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

    Okay, thanks for clarifying. It must have something to do with an underlying binary structure that prevents linear access.

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

      if you want to solve the problem use ordered_set or a fenwick tree/segment tree.

      this is my solution using a fenwick tree 157240227.

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

        Will take a look. I definitely need to learn more about those two...

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

std::distance, works in linear time.

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

    I knew there had to be something! Thank you.

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

      Note that it works in linear time for each call of the function, so if you were to use it in your solution, it still would not pass because the total complexity would be $$$O(n^2)$$$. I'm 99% sure that the implementation for std::distance with not random access iterators just increments the smaller one repeatedly until it reaches the bigger iterator...

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

        Yeah, I tried it and it got TLE on test case 5. But I am sure it will be useful elsewhere!

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

You can't do this with set. You can use ordered_set which requires some installation. Or if you are first inserting then doing queries, i.e You don't insert anything after you make first query, you can use Coordinate Compression and then use Fenwick Tree/Segment tree

→ Reply