Блог пользователя I_am_Drew

Автор I_am_Drew, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • -34
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

Thanks!

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Hm, good luck!!

    But I will use other prime numbers next time)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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 :)))))

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

what is the "pow"???

powAR or powER ????

»
4 года назад, # |
Rev. 4   Проголосовать: нравится -10 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

This is very interesting !

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"I hope the article was useful!"

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.