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

Request to fellow coders
Автор decoder__, история, 4 года назад, По-английски

Hello coders, recently I came across this thing that many people who are new to CP often find it difficult to reduce the time complexity of their algorithm. They know the O(n^2) or any higher complexity algorithm but find it hard to reduce it to better time complexity. I request my fellow coders who are now comfortable in reducing the time complexity of their algorithms, to share their approaches and thought processes. This will help many people to think along those lines and eventually get better. Thanks and hope this post may help many.

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

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

You may consider a hash based solution

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

    Ohh yeah, the hash based solution, works every time

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

      $$$O(n^2)$$$ to $$$O(1)$$$ in seconds.

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

      And get hacked everytime.(if there is open hacking and you didn't make at least double randomized hashing)

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

        And what about open addressing? ;)

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

          Yeah, those hashing resolvers are cool. But notice, that if collisions happens a lot, it might get hacked from TLE not from only WA. Also, resolving collisions while hashing a string is not recommended. It slows down the algorithm by a lot. For example, if you saw a hash collision, you need to compare the whole length of the substring of the string with the other one. Collision Resolvers will work well if only one of the substring exist. That means, no other substrings that are similar to each other would exist. Randomized Double hashing is the safest for now with a very low chance of collisions which nearly always pass.

          → Ответить