Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

decoder__'s blog

Request to fellow coders
By decoder__, history, 4 years ago, In English

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.

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

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

You may consider a hash based solution

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

    Ohh yeah, the hash based solution, works every time

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

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

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

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

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

        And what about open addressing? ;)

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

          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.

          → Reply