Problem requiring solution that is vulnerable to hash collisions

Revision en5, by kfqg, 2018-04-08 09:16:25

I was reading the tutorial of CF 763D, a problem about tree isomorphism. The official solution involved computing polynomial hashes of all possible subtrees of a tree, and then comparing the hashes as a substitute for checking tree equality. It seems to me like the solution is vulnerable to hash collisions.

I'm relatively new to competitive programming. Is it normal for there to be problems that require solutions that are vulnerable to hash collisions? It seems like a good problem should be one that is provably solvable for 100% of all possible inputs.

The problem is here: http://codeforces.net/problemset/problem/763/D

The tutorial is here: http://codeforces.net/blog/entry/50205

rng_58 also wrote a blog post on this: http://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html. The solution given there also has a nonzero hash collision probability.

Tags #hashing, #graph, #trees

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English kfqg 2018-04-08 09:21:06 29
en8 English kfqg 2018-04-08 09:20:13 9 Tiny change: 'hism. The official solution ' -> 'hism. The solution '
en7 English kfqg 2018-04-08 09:19:46 9 Tiny change: 'tree (max size n = 10^5 vert' -> 'tree (max 10^5 vert'
en6 English kfqg 2018-04-08 09:19:22 29 Tiny change: ' of a tree, and then' -> ' of a tree (max size n = 10^5 vertices), and then'
en5 English kfqg 2018-04-08 09:16:25 26
en4 English kfqg 2018-04-08 09:15:40 194
en3 English kfqg 2018-04-08 09:12:43 1
en2 English kfqg 2018-04-08 09:10:48 64
en1 English kfqg 2018-04-08 09:09:36 704 Initial revision (published)