Unordered map-AC While Map-TLE in CLBRKT

help
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?

54

Yep. As @sebastian says, I donā€™t think they had any 10^7 size string. :face_with_hand_over_mouth:

1 Like
55

They hadā€¦I used assert statements to check.

1 Like
56

I just tried in cc IDE to create an array of size 1e7 in main and it ran

2 Likes
57

I think you should write following statement:

assert (n==1e7);

instead of:

assert (n<=5*1e6);

Because we are checking if there is a input of 10^7 or not.
Am i Right?

58

Noā€¦try to understand on your own.

1 Like
59

Can You Explain Pleaseā€¦ Not able to undertand!

60

Bro Can You Explain Why is the Following Running. It Blew My Mind:
Click Here

61

Okay, there will be many casesā€¦ in some cases n will be 1e6(say) and 1e7 in others. So former assert statement will always give re because Problem says n<=1e7 doesnā€™t guarantees n=1e7. So with that re we canā€™t infer anything.
With second assert statement, it gives re so that means there are tc were n> 5*1e6.
You can try something like - assert n<1e7. If it gives re then we are sure there are tc where n=1e7.

1 Like