Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

raihatneloy's blog

Weak data set in Round 291-C ?

By raihatneloy, 12 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

»
12 years ago, hide # |
 
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
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    Right?

    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        12 years ago, hide # ^ |
        ← 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