Блог пользователя rumman_sust

Almost Equal — Advanced, HackerRank
Автор rumman_sust, история, 9 лет назад, По-английски

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 :)

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Something like this

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

          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)

          → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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?

→ Ответить