Hello everyone, I hope you all are fine :)
There are basically two questions, both concerning this problem "Molly's Chemicals ( http://codeforces.net/problemset/problem/776/C )
Sorry for the long post, I will appreciate it very much if anyone participated in this discussion.
1- Problem related question (about map)
First of them concerning C++ map in STL, it is obvious that time complexity intended for this problem is O(N * log(10^15) * search) where search using map is logN so total complexity is O(N * logN * log(10^15)). To make sure that there are only N elements in the map, I do this check: if(cnt.count(x)) ans+=cnt[x];
If I replaced previous part with this: ans+=cnt[x];
It will insert x as a key in the map with value 0 if x wasn't in the map, so this should make complexity O(N * log(NlogN) * log(10^15)).
So it can be shown mathematically that second version has a constant less than two times than that of the first version: N * log(NlogN) * log(10^15) < N * log(N*N) * log(10^15) = 2 * N * log(N) * log(10^15)
but first version runs in 1497 ms but second runs in 390 ms which is approximately 4 times while time analysis shows that it should be much less than 2
2- Problem unrelated question (about unordered_map)
Second and last question concerning C++ unordered_map in STL, the average search time is O(1) but in worst case is O(N) and it seems in the previous problem the author put nice cases for anti-hash tests for unordered_map so it causes TLE.
But I tried every method to pass those tests, and made for more than 20 different tries, I have used many combinations of those:
Used reserve function in unordered_map, set it to MAX, MAX+7, 2*MAX, 7*MAX and others.
Used max_load_factor function in unordered_map, set it to 1, 0.5, 0.2, 0.231 and others.
Changed hash function, set it to x%prime (tried different primes), tried to XOR it and also add it with a constant.
XORed value before sending it to unordeded_map hoping to change distribution of the numbers.
But all attempts to make it pass have failed, although the time limit is 2.5 seconds and map version passed in 0.4 second!!
Is there anyway to make unordered_map pass? and why it TLE although all previous attempts which should change distribution of the numbers and make it pass author's cases?
Thanks in advance
Sorry again for the long post, Wish you all best of luck and have a good day :)
