__RS__'s blog

Hash function for matrix
By __RS__, history, 2 years ago, In English

How can I generate hash function for matrix ? or how can we compare if two submatrix are equal or not ?

EDIT : tagging source problem , just to make sure it's not from an ongoing contest | interview.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by __RS__ (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hash of element $$$a_{i,j}$$$ is equal to $$$a_{i,j}u^iv^j$$$, where $$$u,v$$$ are some random numbers. The hash of a submatrix is equal to the sum of hashes of its elements. You can do row/column translations by simply multiplying by powers of $$$u,v$$$.

→ Reply