skpro19's blog

Unable to detect the bug in the polynomial hash function
By skpro19, history, 8 years ago, In English

I am getting a WA on testCase 6.

Question — Div 2C

My Submission

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

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Ok.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I changed s[j] to c(to fix the logic at your code) and get WA at test 16 instead. 25885244

I 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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But I just used a polynomial hash function as given in the tutorial for the question

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have no idea then. But looking at most people's code, they have better hash function than a polynomial hash.

      → Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Each line consists only of letters 'a', 'b', 'c'.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So? What are you trying to imply?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Such a cryptic comment, we can only try to guess what he means.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I have already assigned 'a', 'b' and 'c' with the values 1, 2 and​ 3 respectively. So, that's I am asking

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Good question.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I wish I could say your comments are helping, but sadly, they are not. So, how about getting a life, huh?

              → Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You can get rid of hashing by replacing set<ll> with set<string> 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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I fix the logic as pointed out above, and got TLE on test 28. 25929172.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Great! Have you tried adding hashing back?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did that above, and it got WA on test 16. 25885244

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yup, i agree with you. I am not the poster of this problem btw. Just trying to help out here.

            → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1 1
ab
ab
should be no, but your code says yes.

→ Reply