Problem requiring solution that is vulnerable to hash collision

Revision en1, by kfqg, 2018-04-08 09:09:36

I was reading the tutorial of CF 763D and it seemed like the official solution had a bug: it 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

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)