Discussion @ 1713. Key Substrings @ Timus Online Judge

wa #7

Posted by Baurzhan 3 Nov 2010 15:38

I'm afraid that i'm getting WA on 7-th test because of hash collisions. How to avoid it? Please, give me some recipes) I tried to change prime base - 31,43,57 - anyway WA#7.

Edited by author 07.11.2010 10:15

Re: wa #7

Posted by Baurzhan 7 Nov 2010 10:16

Re: wa #7

Posted by KALO 7 Nov 2010 19:08

Try 3737 or 1717.

Re: wa #7

Posted by Baurzhan 7 Nov 2010 20:52

P=1000000007 - only this base helped me! 31,57 - and other small bases - sucks! BTW, I didn't take anything by modulo and I declared hash as integer not long long. Now I have only one question: why 5.000.000 pairs of integers eats ~40 MB memory(it's ok - each pair - (4B+4B) *5.000.000 ~ 40) BUT!!! why 5000 000 pairs of <long long,int> eats ~80MB?? I expected
( 8B(long long)+4B(int) )* 5.000.000 ~60MB!! very strange...

Edited by author 07.11.2010 20:58

Edited by author 07.11.2010 20:58

Re: wa #7

Posted by Nickolay Bukreyev 6 May 2015 20:16

It's due to data alignment. sizeof(pair<long long, int>) == 16. 8B(long long) + 4B(int) + 4B(unused).

Discussion of Problem 1713. Key Substrings