ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1713. Key Substrings

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
up
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).