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

Автор farmersrice, история, 5 лет назад, По-английски

https://mirror.codeforces.com/contest/1200/submission/58612411

https://mirror.codeforces.com/contest/1200/submission/58619785

I'm that unlucky to just get the wrong base on test 19? Are you kidding me? Can I get this restored?

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

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

Yes, that's just because of unluckiness.

Remember, when using hash, especially in CF rounds, use at least two hash arrays.

Also, don't write hash when you come up with another solution.

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

ll base = uniform_int_distribution<int>(11, 30000)(rng);
Base should not be less than the max alphabet value.

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

Unlucky :(

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

I can't get it back??????

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

Why do you have random base and constant modulo?

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

    Anti-hack, but turns out it caused my stupidity with "base should not be less than the max alphabet value"

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

      I mean, why didn't you make modulo random as well?

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        I don't think that's necessary for anti-hack as long as the base is random. Should it be done?

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

          No you are correct, because modulo should be prime or at least coprime to base, unless you want to generate random prime

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

          It makes way more sense intuitively to use different random coprime modulos. Consider that as long as base > |alphabet|, a polynomial hash without mod will always be a unique number. If two strings have these hashes $$$h_1$$$ and $$$h_2$$$, then a collision modulo $$$m$$$ means $$$h_1-h_2$$$ is divisible by $$$m$$$. When you use several coprime modulos $$$m_1, m_2, \ldots$$$, a collision means that $$$m_1 \cdot m_2 \cdot \ldots$$$ divides $$$h_1-h_2$$$. I don't know how it works with random bases, but with random modulos, as long as the polynomial hashes give sufficiently random remainders modulo $$$m_1, m_2, \ldots$$$, the chance of a collision drops extremely quickly with added modulos.

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

btw did you heard about double hash but one without modulo? It's as fast as normal hash couse you dont use more modulo. Variables will "overflowing-same" (end up with same numbers) so it will works. But dont try it without first noraml hash couse technically overflowing is nothing more then modulo some power of 2. I hope you got what i had on mind :D gl in future coding!

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

    Sometimes it will be more faster than normal hash. Moduloing takes lots of time.

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

    Wouldn't recommend a modulo $$$2^{64}$$$ hash by itself: link
    But I have seen people use it paired with another prime modulo hash.

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

Oh come on. You got 493 upvote on this blog. You think it really deserves that much?. It's just karma striking back

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

Only randomizing the base and not the modulo is fine, but you have to pick the base from a large range of values. In your code you do ll base = uniform_int_distribution<int>(11, 30000)(rng);, so you're picking the base from less than $$$30'000$$$ values. This is an issue:

  • you're more likely to pick a small base, which might fail on the regular system tests.
  • it is possible to hack all $$$30'000$$$ bases in a single test with around 360'000 characters in total. (Due to the arbitrary 256kb input size limit for hacks, you can only hack around $$$18'000$$$ of them at a time, but that still gives the hacker over 50% odds at success.)
  • there might be strings of length $$$\log_{26}(10^9+7) \cdot 30'000 \approx 191'000$$$ each for which all $$$30'000$$$ bases collide at the same time. I however don't know how to compute such strings.

A better thing to do would be ll base = uniform_int_distribution<int>(0, mod1-1)(rng);. Intuitively, with such a large range of bases, you're unlikely to pick a small base. The exact math behind this can be found here.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    ll base = uniform_int_distribution<int>(0, mod1-1)(rng);

    you mean

    ll base = uniform_int_distribution<int>(11, mod1-1)(rng); right?

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      Short answer: It doesn't really matter.

      Long answer: From a worst-case point of view (i.e. hacks), the first one is slightly better. Using the fact that a polynomial of degree $$$n$$$ has at most $$$n$$$ roots in any field, you can show that for every fixed modulo and every fixed pair of strings of length $$$n$$$, there are at most $$$n$$$ bases that cause a collision. With bases picked uniformly at random from $$$\{0,1,\dots, mod_1-1\}$$$, the chance of collision is at most $$$\frac{n}{mod_1}$$$, with bases from $$$\{11, 12, \dots, mod_1-1\}$$$, the chance is a most $$$\frac{n}{mod_1 - 10}$$$, which is slightly worse.

      I guess that you think that small bases are bad as it is easy to construct tests against them. But in fact, it is easy to construct tests against any fixed base (assuming modulo is also fixed). (If you're just dealing with fixed tests and not with hacks, then tests against very small bases are more likely to be in the testdata. But with hacks, there is little difference between different fixed bases.) This is why you need to pick you're based randomly at runtime, so that the hacker can't know against which base he has to find a test case.

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

        I guess that you think that small bases are bad as it is easy to construct tests against them

        I am instead thinking that having small base is bad because the size of the alphabet is bigger than the base. I am not concerned about hacks, but if you are unlucky to get 0 or 1 as your base in your systest, then it is quite likely for you to fail those test?

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

          You have a good point: If you only worry about system tests and not about hacks, then I could see that a base smaller than the alphabet size is more likely to cause collisions. If we model system tests as uniformly random strings of various lengths, then for bases larger than the alphabet size, small strings won't collide and large strings will have approximately uniformly distributed hash values, so chance of collision might be around $$$\frac{1}{mod_1}$$$. Bases smaller than the alphabet size will have many collision on small strings, so they're worse.

          Let's compute how unlucky you'd have to get: With $$$mod_1 = 10^9+7$$$, the probability of getting base below $$$256$$$ is only $$$2.5 \cdot 10^{-7}$$$. If you're comparing $$$10^5$$$ pairs of strings, then the probability of getting a random collision on random testdata is already $$$10^{-4}$$$, which is much higher. So I'd worry more about random collisions that about getting a small base.

          Ideally you use multiple hashes with large modulus so that you're incredibly unlikely to get a collision even with hacks. Then you'll have an implementation for which you can prove that it will work on any input with high probability (and don't need to hand-wave about how you model system tests). For instance, if you use $$$4$$$ hashes with $$$mod = 10^9+7$$$ and randomized bases, $$$n = 10^5$$$, then the probability of a single comparison colliding is at most $$$\left(\frac{n}{mod}\right)^{4} \approx 10^{-16}$$$. If you're comparing $$$10^5$$$ strings, then the chance of a collision is still only $$$10^{-11}$$$ per test case. (If you use $$$mod=2^{61}-1$$$, then the probabilities are even better, but the implementation becomes tricky.)

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

            I picked from range [300, mod — 1] (300 to avoid alphabet size problem) and it gave me WA test 5:

            https://mirror.codeforces.com/contest/1200/submission/58714718

            I submitted 3 more times and it worked all 3 times, is this just incredibly bad luck? Or I did something wrong elsewhere?

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

              Actually, now that I think about it, you want to use $$$[300, mod-300]$$$ to avoid the alphabet size problem. Having a base that is minus a small number is just as bad as having a small base.(Once again, the probability of a random collision is much higher than the probability of getting a base close to $$$0$$$ or $$$mod$$$, so this shouldn't really matter.)

              Regarding your submission, I guess it's just bad luck. On a max-test, you're comparing close to $$$10^6$$$ pairs of strings, so the probability of a random collision on random strings is $$$10^{-3}$$$. (We don't know if the string is really random, so the chance might be higher or lower.) (If you'd use two hashes, that would drop to $$$10^{-12}$$$.)