Блог пользователя raihatneloy

Weak data set in Round 291-C ?

Автор raihatneloy, 9 лет назад, По-английски

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! :(

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Right?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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! :)

        → Ответить