wrg0ababd's blog

514C Watto and Mechanism WA 27 (Hashing)
By wrg0ababd, 9 years ago, In English

I understand that I'll get downvoted here, but maybe I'll get some help as well. I'm trying to solve 514C using hashing, as it's done in editorial, but why my submission gets WA on test 27?

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

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

Most probably a false positive due to a hash collision. The hash function is probably telling your program that the string only has a single character changed, but multiple characters may have changed and the same hash value has been computed.

To avoid this, maintain a Map<Long, String> for each hash value -> string, then when you think you found a solution, double check that the difference is indeed one letter. See my submission for an example.

→ Reply