I was attempting the E problem of round #878 Div 3. I am getting TLE in my code but it seems to me that the Time complexity of the code if O(T * (t + q)) which should get accepted. Please tell me the mistake in the code.
Approach: I am storing the position which are unblocked at time (relative to current time) in a queue. The string a and b are just a copy of s1 and s2 which will be blocked and unblocked throughout the process (s1 and s2 are not altered).
Problem: Div 3 E
My submission: Submission
Code
Auto comment: topic has been updated by SP_22 (previous revision, new revision, compare).
(string)a==(string)b
isn't $$$O(1)$$$, it's $$$O(\min(|a|,|b|))$$$So what should be done instead of that?
For example managing the positions $$$x$$$ which $$$S_{1,x} \neq S_{2,x}$$$ and $$$x$$$ isn't locked, with some data structure or smarter way.
But in my AC submission, I also did (s1 == s2) and didn't get TLE. Why so?
Also how to check if two strings are equal in O(1)?
Hacked :)
Bullying :((
Read info about polynomial hashing