raihatneloy's blog

Weak data set in Round 291-C ?

By raihatneloy, 10 years ago, In English

This Solution got AC, but it gave wrong output for the input below:

3 1
a
b
c
aaaaa

The program gave output: YES but I think the output should be: NO

Am I right? If I'm, then the data set may b too weak! :(

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, it seems you're right. According to your code strings like 'aaa..a' have hash equels 0. So, HASH("baaaa") == HASH("b") and so on.

Unfortunatly, testset doesn't cover this case.

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

    HASH("baaaa") == HASH("b") * BASE^4

    Right?

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

      But actually HASH("b") == HASH("aaaab"). That's why it's good to use BASE = 5 and a = 1, b = 2 and c = 3.

      BTW, this is my first way when I use a as 0, b as 1 and c as 2 and it seems I was really really really lucky with that :D :D :D

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

        Wow, actually I compare the strings not only by the hash value but by the length too, so in my case it doesn't depend on luck. Sorry for the misunderstanding! :)

        → Reply