rumman_sust's blog

Almost Equal — Advanced, HackerRank
By rumman_sust, history, 9 years ago, In English

I've found an interesting problem in hackerrank. But couldn't solve it. I've tried so many ways, but no one can pass the time limit. That's why I've decided to seek some help from you guys :) Here is the problem link. If anyone have an idea to solve it, please share your thoughts :)

UPD: Solved it with mo's algorithm + binary index tree. Thanks for the hint mkirsche :)

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

Comments Comments (15)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Assuming you have enough time to sort the input, you could sort it and use two pointer method.

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

    mkirsche how can I use two pointer mathod here? Can you please explain a little bit more?

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

      Something like this

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

        I appreciate your solution. But there are Q queries. For each query you have two integer L and R. You have to output the ans within range [L, R] for each query where, 1 <  = N <  = 105 ,1 <  = Q <  = 105.

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

          Oh, oops! Well, I think you can solve it with Mo's algorithm plus an interval tree or other data structure that lets you quickly add, remove, and sum over a range for a runtime of n * log(n) * sqrt(n)

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

            Thanks for the reply :) I'll let you know if I've came up with a solution :)

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

I've solved it using hashing (Rabin Karp, 2 different hashes to have less collisions) And binary search for every query. Using Rabin Karp during preprocess you can get every hash in O(1) And then just binary search the different char between the two substrings And check the other two parts to be equal.

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

Auto comment: topic has been updated by rumman_sust (previous revision, new revision, compare).

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

binary index tree? how we can use it? elements of array are 10^9

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

    Compression of numbers(sorting + map/hash).And for every value you add in interval,binary search the wanted values(minimum/maximum so that is satisfies that condition). Take care that you have to compare their hashed values,not the compressed ones.

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

I implemented Mo's algorithm with an implicit segment tree ( since values are upto 109 in this question ) but my code TLEs on most cases, as expected.
The complexity of my code is
How do I optimize it to
Also, rumman_sust , could you post your accepted solution that used binary indexed trees?

→ Reply