Almost Equal — Advanced, HackerRank

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

Автор 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 :)

data structures, rmq, interval tree, segment tree, sqrt_decomposition, binary indexed tree

rumman_sust
9 лет назад
16

Комментарии (15)

Показать архивные | Написать комментарий?

mkirsche

9 лет назад, # |

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

→ Ответить

rumman_sust

9 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

mkirsche

9 лет назад, # ^ |

Something like this

→ Ответить

rumman_sust

9 лет назад, # ^ |

← Rev. 3 →

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 < = 10⁵ ,1 < = Q < = 10⁵.

→ Ответить

mkirsche

9 лет назад, # ^ |

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)

→ Ответить

rumman_sust

9 лет назад, # ^ |

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

→ Ответить

carlotheboss

9 лет назад, # |

← Rev. 2 →

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.

→ Ответить

rumman_sust

9 лет назад, # ^ |

← Rev. 2 →

carlotheboss I think you are talking about wrong problem(no offense). Please read the problem statement here :)

→ Ответить

carlotheboss

9 лет назад, # ^ |

yeah i was talking about the problem "Almost Equal" not "Almost Equal Advanced", sorry

→ Ответить

rumman_sust

9 лет назад, # |

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

→ Ответить

Gaajvi

9 лет назад, # |

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

→ Ответить

Archazey

9 лет назад, # ^ |

← Rev. 3 →

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.

→ Ответить

animeshf

9 лет назад, # |

← Rev. 2 →

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