I am trying to solve http://codeforces.net/contest/514/problem/C but repeatedly getting wa at test 6.Tried a lot but can't figure out the problem...Link to my solution http://codeforces.net/contest/514/submission/9883601
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I am trying to solve http://codeforces.net/contest/514/problem/C but repeatedly getting wa at test 6.Tried a lot but can't figure out the problem...Link to my solution http://codeforces.net/contest/514/submission/9883601
Название |
---|
=(((str[j]-'a'+1)*(ll)pow(5,j))%mod);
pow function is declared likedouble pow(double x, double n)
some powers of 5 will not fit into double and number will be truncated(size of double is 8 bytes).
Use your own Pow function to power number modulo mod.
I did but still WA http://codeforces.net/contest/514/submission/9883905
No. You did not. It's still call standart function pow. Rename function to "Pow" with capital letter, or "Bar" or "Foo".
Still no use :( http://codeforces.net/contest/514/submission/9918779
uncomment lines.
//val%=mod; //val+=mod;
I had TLE with your code a few days ago. Next step is to replace set::find with binary_search or hashtable.You have to name your pow function other than pow, becasue pow is a C++ function. And your pow function work slow. You should try Log(n) pow or pre-compute pow function
Your bug is in hash calculation: pow function is calculating result in double type. It won't work as you expect: pow can return something like 3e100, it won't be taken by modulo and will moreover loose a lot of significant digits.
I think the solution with trie is better than the hashing one. I haven't perfectly analized your code but maybe the bug is that your hashing is not perfect so I suggest you to implement the trie solution, which is much easier
Why you don't try with different bases?For example try with 37 or 71...
I tried doing it using trie but i cannot figure out the search procedure. Can you help me?
Here is my solution. 12563068