**Hello everyone, I hope you all are fine :)**↵
↵
↵
**There are basically two questions, both concerning this problem "Molly's Chemicals ( http://codeforces.com/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 in1497390 ms but second runs in 3901497 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 :)**
↵
↵
**There are basically two questions, both concerning this problem "Molly's Chemicals ( http://codeforces.com/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
↵
-------------------------------------↵
↵
**_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 :)**
