Getting tle by using unordered map but ac using map

help
1

Problem link : Problem - D - Codeforces
Solution using unordered map : Submission #85524935 - Codeforces
Solution using map : Submission #85524806 - Codeforces

1 Like
2

I was talking about the same thing right here.
We have to use a custom hash, if we are using unordered map. It reduces collision probability.

2 Likes
3

It is this because, when unordered map runs out of contguous space so it takee O(n) time to shift all the elements to a new space ?

see the differences in these codes, in one code he just reserved memory for his unordered map.

2 Likes
4

so this mean we should use map always??

5

it depends on the situations we need to implement it.

6

If O(logn) operation on the map is within bounds, then use map. If you need a HashMap for a faster look up, use custom hashing and reserve memory for the unordered_map as @anon41069019 has mentioned.

1 Like
7

okk thanks

8

Map takes O(Logn) time in worst case
Unordered map takes O(1) time in best case and O(n) Time in Worst case

9

It can also blow up to O(n^2) I guess. When there are rehashing and reallocation of space.

10

I never understood this concept named “blow up to O(n^2)” in Unordered map what does it actually mean and why does it happen can you explain?

11

I am not very familiar with the implementation of unordered_map in C++ stl. But apparently, one can easily build a test case to make the map run into O(n) collisions. And as the number of elements/collisions increase, with each insertion it will change the hash function it uses (the prime it chooses for MOD I guess), recompute the hashes for all the elements, and reallocates them, thus costing you a lot of time. More on this here.

The last paragraph (just before the custom hashing solution), he has explained how one can make test cases to blow up a hash map.

12

Yeah i have seen this link before and read it too but the writer of this blog was so much into technicality that i couldn’t understand anything.

13

Haha, even I don’t understand much of it. But the only way to gain more knowledge on this is to dig deep into the stl implementation. Until then, lets stick with map.

1 Like
14

Yes i always use map now instead of unordered_map.

1 Like
15

I’ve implemented MinHeap in Problem - D - Codeforces , but it’s giving TLE at Testcase “5”. (link: Submission #86907927 - Codeforces)
{ I’m not getting the logic used in editorial for this problem :frowning: }

Any kind of help will be truly appreciable :slight_smile:

{Logic used in minHeap:

For i such that a[i]%k!=0, store minimum difference (a[i]//k+1)*k - a[i] in heap and than sequentially travel from x=0 until heap beacome empty, solving for “top of heap” in each iteration. If at any time the top is less than x, than increase that top to (top+k). The logic is working but giving TLE at TC 5 :frowning:

}