Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

__wizzz's blog

Another coding problem for discussion
By __wizzz, history, 6 years ago, In English

I was giving online exam on hackerearth. The problem statement is
Note: It has already ended few days back.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

At first, I thought of using polynomial rolling hash function. But since we have integral values, there will be high probability of collision. So, couldn't able to verify its truthfulness.

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it +13 Vote: I do not like it

    I can't come up with a better solution, but I think you can use suffix array to compare 2 substrings in O(log(n)) instead of hash. Nevertheless, hash still works pretty well if you use 2/3 mods. (and seems to be easier to implement too?)

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

    I solved it using the above solution during contest and it passed all tests :)

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

      In the contest, I submitted a brute force solution and even that passed, which means that test cases were quite weak.

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

    Very true, I was doubtful that hashing would work, then I thought oh wait I am on hackerearth not on codeforces, walla ac, lol.
    Still I guess double hashing or triple hashing would reduce the collision probability.

    → Reply