Problem link : https://codeforces.com/contest/1374/problem/D

Solution using unordered map : https://codeforces.com/contest/1374/submission/85524935

Solution using map : https://codeforces.com/contest/1374/submission/85524806

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.

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 ?

https://codeforces.com/contest/670/submission/17758293

https://codeforces.com/contest/670/submission/17728217

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

so this mean we should use map always??

it depends on the situations we need to implement it.

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.

okk thanks

Map takes O(Logn) time in worst case

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

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

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?

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.

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.

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`

.

Yes i always use map now instead of unordered_map.

Iâ€™ve implemented MinHeap in https://codeforces.com/contest/1374/problem/D , but itâ€™s giving TLE at Testcase â€ś5â€ť. (link: https://codeforces.com/contest/1374/submission/86907927)

{ Iâ€™m not getting the logic used in editorial for this problem }

Any kind of help will be truly appreciable

{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

}