SP_22's blog

Help: What is the Time Complexity of this?
By SP_22, history, 12 months ago, In English

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
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been updated by SP_22 (previous revision, new revision, compare).

→ Reply
»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

(string)a==(string)b isn't $$$O(1)$$$, it's $$$O(\min(|a|,|b|))$$$

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

    So what should be done instead of that?

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

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

    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)?

    → Reply