Unordered map-AC While Map-TLE in CLBRKT

help
33

Then you will have to implement custom hash and use unordered_map or you can use array compression and unordered_map

1 Like
34

Multiple Keys in a bucket means multiple keys which are all same?
like if we are inserting a value say,1e9 so many times, then it will lead to collisions.Right?

35

Do You mind if you can guide me how custom hash can be implemented or the word you used “array Compression”?

1 Like
36

No. It means multiple keys have same hash. So k1 and k2 have same hash, so we are unable to resolve whether particular key is k1 or k2 without doing a linear search.

1 Like
37

Are you trying to say like this?
if k1 has value 2
k2 has value 2
so we are unable to resolve whether particular key is k1 or k2 without doing a linear search.
Am I right?

38

Array Compression: Convert an Array to reduced form using Hashing - GeeksforGeeks

1 Like
39

User Defined Hash: How to create an unordered_map of user defined class in C++? - GeeksforGeeks

1 Like
40

Y

Yes. So k1 and k2 are colliding. Now imagine if there was a second hash function which resolves k1 and k2 differently. So if the first one collides, we can use the second.

1 Like
41

Thank You @dardev for links you shared!!!

43

Seriously, dont do PhD in hash and unordered_map and map. Invest energy elsewhere. Study rolling hash/polynomial hash and string hashing. You will learn something new and the concepts are totally transferable. You dont need to figure out 1001 ways to kill a cockroach.

3 Likes
44

During hashing, it’s impossible to come up with a perfect hash function. There are multiple ways to resolve collisions. One such solution is chaining.

2 Likes
45

Second hash Function means,
like we store k1 and k2 in two different maps
for ex-
m1[k1]++;
m2[k2]++;

Are you saying like this?

46

No. Refer to the links I shared and also chaining example shared @aneee004

2 Likes
47

Okay Thanks for the guidance, You were Such a help today @dardev

1 Like
48

Thank You So much @aneee004 for the help.I will look at the links shared!

1 Like
49

I used an array instead of map and it passes.
Input goes till 10^7 , So How Array is Accessing [(10^7)-1]th index?
Solution using array- Click Here

1 Like
50

You mean how you’re able to declare such a big array? I’m not sure. However global arrays of size 10^7 work I guess.

1 Like
51

Yeah I also found this strange. CodeChef: Practical coding for everyone I think there was no string of size 1e7

2 Likes
52

But i have declared my array in main which can access maximum index as [(10^6)-1], but in this question input is 10^7 ,So How array is accessing [(10^7)-1]th index?

1 Like
53

Yes, But in the Problem it’s written that
" Sum of |S|and Q over all testcases for a particular test file does not exceed 10^7 and 10^6 respectively."

But we should not take it for granted that there will be no such string with length as 10^7.May be they have included only one test file and its written to trick the participant. Right?