I_am_Drew's blog

Hashing a list (vector)
By I_am_Drew, history, 4 years ago, In English

I have come up with (invent) a new list hashing algorithm that you can use to hash lists whenever you want. The secret is simple:

Suppose B is a dict (map) ar = list (vector)

Then for a list consisting of two elements, we need to match this number:

B[pow(ar[0], 37, 1000000007) + pow(ar[1], 43, 1000000007)] = [ar[0], ar[1]]

So we have mapped a list of 2 elements to a number!!!

The more items in the list, the further we can add pow(ar[i], P_i, 1000000007), where i is the trace. index in the list (vector), and P_i is the trace. Prime number.

With this hashing of lists (vectors), we can with a probability of 95-99% drive the problem to OK without much bother!!!

I hope the article was useful!

  • Vote: I like it
  • -34
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hm, I will try this on problem that I haven't solved a week ago!

Thanks!

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

It is genius! But why you use 37 and 43? I will hack you in future codeforces rounds by this!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Hm, good luck!!

    But I will use other prime numbers next time)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Your rating is so high! But you can't understand this easy lalgorithm! You just need to use random prime number. It's not hard enough for you to understand why it's a nice way to solve problems. You're just a stupid master! We students are the best participants of codeforces!!! And the most clever too :)))))

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Lol, someone don't understand this, and I hacked them and my rating increaaaaaaases

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

What do you think about this algorithm? Is it quite good or not?)

→ Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

what is the "pow"???

powAR or powER ????

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it -10 Vote: I do not like it

by the way, it is the best idea in whole competetive programming!!!

→ Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

This is very interesting !

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    do you know about HUNGARIAN LALGORITHM? it is also very interesting

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Absolutely agree! That algorithm helped me to have sex with my girlfriend for the first time! It was so amazing!

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"I hope the article was useful!"

do not hope. Be sure it was useful!!!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I_am_Drew basketballer keklol45 andryusha_na_knopke Drew_is_me sevlll777 300_are_queue MikMirzoyanov EvgenKarpov

are you actually one person guys?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am truly eager to know how did you figure that out????

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Unfortunately, no, but we are friends :)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh god! I figured out how you figured out! ;)

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don’t understand the idea... can anybody(Or I_am_Drew)explain it better please?

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

So how to compare subarrays when they start at different places?

F.e $$$arr[i..i+k-1], arr[j..j+k-1], i<>j$$$

In traditional hashing, you multiply hash by $$$p^{BIGNUMBA-i}$$$ or smth to compare.

→ Reply