Problem requiring solution that is vulnerable to hash collisions

Правка en9, от kfqg, 2018-04-08 09:21:06

I was reading the tutorial of CF 763D, a problem about tree isomorphism. The solution involved computing polynomial hashes of all possible subtrees of a tree (max 10^5 vertices), 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? Shouldn't a good problem 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.

Теги #hashing, #graph, #trees

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский kfqg 2018-04-08 09:21:06 29
en8 Английский kfqg 2018-04-08 09:20:13 9 Tiny change: 'hism. The official solution ' -> 'hism. The solution '
en7 Английский kfqg 2018-04-08 09:19:46 9 Tiny change: 'tree (max size n = 10^5 vert' -> 'tree (max 10^5 vert'
en6 Английский 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 Английский kfqg 2018-04-08 09:16:25 26
en4 Английский kfqg 2018-04-08 09:15:40 194
en3 Английский kfqg 2018-04-08 09:12:43 1
en2 Английский kfqg 2018-04-08 09:10:48 64
en1 Английский kfqg 2018-04-08 09:09:36 704 Initial revision (published)