Unordered map-AC While Map-TLE in CLBRKT

help
1

Problem-Click Here

Unordered Map Solution -Click Here (AC)
Map Solution - Click Here (TLE)

Worst Case Complexities:-
Unordered Map - O(n) [I know Best case is O(1) for unordered_map]
Map-O(Log n)

Even Complexities are saying that map should give AC.

Can Anyone Explain the reason Why is it Happening ?
Thanks In Advance!

2

Unorderedmap is hashtable of C++

While the complexity in the worst case is O(N), this is very rare on random input. And unordered_map will fail, only if we study the hashing function and intentionally provide such an input, that’ll increase collisions, blowing it up

Thus it’s safe to assume the complexity is O(1).

Since O(1) is faster than O(logN) map gives TLE, but unorderedmap doesn’t

5 Likes
3

O(nlgn) will not give AC. It was luck that unordered map gave AC as there were no collisions. Now a days, setters deliberately put some TC where unordered map will give TLE ( O(n) ).

1 Like
4

Thanks For Replying,
But its not everytime that we can assume unordered map will be O(1) , Most Of the time it’s Reverse,map gives AC while unordered map gives TLE.

How can i figure out what to use when?

5

I’ve never faced any problems with unorderedmap, but when we use it, we risk getting hacked.

Better way is to use an auxiliary array.

1 Like
6

That’s what i am saying that we can’t trust unordered map as it’s worst case is O(n) but we can trust a map as in every situation it gives O(Log n).
and Unordered map giving AC means Test Cases are weak.Right?

7

Using int instead of long long sometimes let O(NlogN) solutions pass at places where O(N) is expected

1 Like
8

what we will do when when input exceeds 10^5 because array will not work in that case

9

But i am using long long int

10

I’ve never used auxiliary array in practice.
Unordered_map has always worked for me, but if you’re concerned about getting hacked, this shows how to avoid getting hacked

1 Like
11

I’m just saying that, when we don’t need long long, we could just use simple int, it speeds up execution and saves us from TLE in some cases, like solving Multiset from CF, using BIT. Using long long gets TLE here, but int does not.

1 Like
12

I have read this blog,the technical terms are so deap that its unclear to me

13

Exactly, idk who uses it, unordered containers have always worked perfectly fine for me, if you know a problem where it doesn’t, please provide the link.

1 Like
14

The solution is Ostrich method.

“Put your head in the ground, and act as if there’s no problem”

1 Like
15

Problem-Click Here
In this Problem i used unordered map which gave TLE
And when i changed it to map it gives AC

16

unordered_map performs better because hash collisions aren’t very common. In fact, they are extremely rare. Here is a program that illustrates this:

#include <bits/stdc++.h> 
using namespace std; 
#define ll long long
int main() 
{ 
    unordered_map<ll, ll> umap;
    ll num = 2e7;
    ll val;        

    for (ll i = 0; i < num; ++i)
    {
        val = rand() % (10000009);
        cin >> umap[i];
    }

    ll n = umap.bucket_count(); 
    cout << "umap has " << n << " buckets.\n\n"; 

    ll collisions = 0;
    for (ll i = 0; i < n; i++) { 
        if(umap.bucket_size(i) > 1)
        {
            cout << "Bucket " << i << " has "
            << umap.bucket_size(i) << " elements.\n"; 
            collisions++;
        }
    } 

    cout << "Total Collisions: "<< collisions << "\n"; 
    return 0; 
}

Here is the ideone: h3YjjY - Online C++0x Compiler & Debugging Tool - Ideone.com

Tell me, how many collisions do you see?

2 Likes
17

@aneee004 , Can You Help Out in this Doubt?

18

Share both solutions?

1 Like
19

Thank You So Much @dardev , You mean to say that collisions in unordered map happens when there are more than one key value pair in a particular bucket.
Right?

20

Unordered Map - Click Here
Map - Click Here

Submit these two solutions Unordered map gives TLE while Map gives AC.