Walid_Amin's blog

Very strange behavior in time analysis of map and question about unordered_map
By Walid_Amin, history, 8 years ago, In English

Hello everyone, I hope you all are fine :)

There are basically two questions, both concerning this problem "Molly's Chemicals ( http://codeforces.me/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 390 ms but second runs in 1497 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 :)

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +35 Vote: I do not like it

1) Don't forget that you query the map twice in the first way and only once in the second, so it can give worse performance depending on the data. A better way to do this is

map<>::iterator it = cnt.find(x);
if(it != cnt.end()) ans += it->second;
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Your way is much better way, Thanks!

    But I made a typo in the post, the first version runs in 390 ms and second one runs in 1497 ms (I accidentally swapped them)

    This should makes the constant even much less than 2

    → Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Is there anyway to make unordered_map pass?

Two ways from me:

1) 25064963 Fast way. Add x + x / P instead of x.

2) 25065058 Apply some random bits permutation before adding number to set.

→ Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

regarding unordered_map:

http://codeforces.me/blog/entry/50626#comment-345515

http://codeforces.me/blog/entry/21853

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks!

    They seem very good useful resources, I'll read it now :)

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Question 1:

I think that in the second way, you also cannot forget that in order for a test case to be 'difficult', the numbers in the array must be small (for more possiblities of different powers). But this means that there are a lot of common elements in the hardest case. Your first method will insert less things into the map because in this hardest case, there are a lot of 'collisions'. However, in your second method, it inserts a lot of random different values which do not collide and result in possibly a lot more values in the map than you expected!

→ Reply