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 (max size n = 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? 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.