Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### skpro19's blog

By skpro19, history, 6 years ago,

I am getting a WA on testCase 6.

Question — Div 2C

My Submission

Can someone please tell me what's wrong with the code?

• -6

 » 6 years ago, # |   +28 Ok.
•  » » 6 years ago, # ^ |   0 ??
 » 6 years ago, # |   0 Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).
 » 6 years ago, # |   0 Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).
 » 6 years ago, # | ← Rev. 2 →   0 I changed s[j] to c(to fix the logic at your code) and get WA at test 16 instead. 25885244I think there is hash collision which cause this to still fail. So either use a better hash function or don't hash! :)UPD: The problem do lies in the hashing. I simply change the hash function and now the answer is wrong on another line
•  » » 6 years ago, # ^ |   0 But I just used a polynomial hash function as given in the tutorial for the question
•  » » » 6 years ago, # ^ |   0 I have no idea then. But looking at most people's code, they have better hash function than a polynomial hash.
 » 6 years ago, # |   +7 Your function returns this same hash for strings "af" and "ba"... Seems like it isn't very good... Try changing 5 for something bigger, it should help (bigger than 26). I haven't look for other bugs, so I am not sure that it will help.
•  » » 6 years ago, # ^ |   +15 Each line consists only of letters 'a', 'b', 'c'.
•  » » » 6 years ago, # ^ |   0 So? What are you trying to imply?
•  » » » » 6 years ago, # ^ |   0 Such a cryptic comment, we can only try to guess what he means.
•  » » » » » 6 years ago, # ^ |   0 I have already assigned 'a', 'b' and 'c' with the values 1, 2 and​ 3 respectively. So, that's I am asking
•  » » » » » » 6 years ago, # ^ |   0 Good question.
•  » » » » » » » 6 years ago, # ^ |   0 I wish I could say your comments are helping, but sadly, they are not. So, how about getting a life, huh?
 » 6 years ago, # |   +6 You can get rid of hashing by replacing set with set and still get WA 6: 25894661. It means that your solution has some other problems. I'd recommend finding them first, getting TL, and add hashing only afterawards.Also, as far as I can see, your hashing function is just fine.
•  » » 6 years ago, # ^ |   0 I fix the logic as pointed out above, and got TLE on test 28. 25929172.
•  » » » 6 years ago, # ^ |   0 Great! Have you tried adding hashing back?
•  » » » » 6 years ago, # ^ |   0 I did that above, and it got WA on test 16. 25885244
•  » » » » » 6 years ago, # ^ |   +3 Ok, I believe that there is a chance of collision when using small modulo (like 109 + 7). Birthday paradox tells us that if there are approx. random hashes, then chances of collision are greater than 50%. I'd suggest using bigger module as long as you use long long — like 1018 + 9 (it's prime, which is important).Afterwards you'll find out that your code is in fact quadratic, because calculation of a single hash takes linear time in your code (can be done more efficient by recalculating hash when changing the character). Try optimizing that. And afterwards you may encounter that endl makes your program extremely slow — replace it with "\n" if it's the case.
•  » » » » » » 6 years ago, # ^ |   0 yup, i agree with you. I am not the poster of this problem btw. Just trying to help out here.
 » 6 years ago, # |   0 1 1 ab ab should be no, but your code says yes.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 fixed that issue. Still fails on test case 16 :-(