arujbansal's blog

[Video Tutorial] Range Queries with Mo's Algorithm
By arujbansal, 4 years ago, In English



I made a short tutorial on answering range queries offline with Mo's algorithm on my YouTube channel here: Offline Range Queries with Mo's Algorithm

I explain how to use Mo's algorithm in general and solve the problem 221D - Little Elephant and Array using it in the video.

Improving runtime: CP-Algorithms — Tips for improving runtime
Alternative sorting order for Mo's algorithm: An alternative sorting order for Mo's algorithm by gepardo

Here are some practice problems (feel free to recommend some in the comments):
- SPOJ — Range Distinct Queries
- Hackerearth — Range Inversion Queries

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

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Really nice tutorial!

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

Why is my code giving Runtime Error?

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

    Not sure why you were getting runtime error but I managed to change a few things in general and get AC.
    Here's the working code: DQUERY Submission

    Some of the things I changed in your code:
    1. Variable lt is 0 and rt = -1. Since you are using 1 based indexing, you have to increment both of them by 1.
    2. You should always increase the bounds of your query first to you should always try to move your right pointer to the right and your left pointer to the left before shrinking them.
    3. Your code got TLE after changing this so I reverse sorted the queries in odd indexed blocks. You can read about that here: Improving Mo's runtime
    4. Note that you can just use integers... Using long long is not required.

    → Reply