Learning Notes on Hashing

I wouldn’t think of summarizing problems on hashing if I didn’t include “hashing” in the tag for my training plan and see those nice problems recently… While hashing can be used in string checking (so-called “polynomial hashing”), it can be extended to do things like set identity checking.

Problems like this is one of the direct application: We can give each number a random number. Then if two set has the same xor sum, the content of the set will likely be the same.

Shortest/Longest Path Cut Vertex Checking: 1214D, 650D
Sometimes, if we want to check if a vertex is neccesary for a shortest path/longest path, we can use hashing to calculate the number of ways and see if $f(s, v) * f(v, t) = f(s, t)$, where $f(u, v)$ is number of ways to go from $u$ to $v$.
P.S. There are simpler ways as talked here.

Permutation Checking: 213E
We want to maintain a data structure which characterizes a permutation, and supports addition and deletion of an element. How to characterize a permutation? Well, we can put the question like this: ” What uniquely determines the permutation? ” One way that can be implemented relatively easily is inversion sequence, where is $i$th term is the number of numbers before the number $i$. We can keep this structure efficiently using a Fenwick Tree.

Symmetry Checking: 452F
In this problem, we want to check if a certain group of number is symmetric. To solve this, we can store two values for a group, giving powers to numbers in reverse order. Say the frequency list is $[1, 1, 1, 0, 0]$, we can give them two string $”11100″$ and $”00111″$. To check whether they are symmetric around, for example, the second element, we can shift them (in hash) and then check whether they are the same.

Leave a Reply

Your email address will not be published. Required fields are marked *