M.A.H.M.O.O.D's blog

help for finding out the reason behind TLE
By M.A.H.M.O.O.D, history, 8 years ago, In English

Hi everyone

so today I was solving 645C - Enduring Exodus and I was struck by TLE.

I'm not pretty sure but I think that my solution should pass can you help me figure out if it's a coding bug or is the idea complete wrong I think that my solution's complexity is O(3N).

my submission 20031002

thank you very much

:)

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it 
for( ; j <= i ; j++)
{
                    if(s[j] == '0')
                        break;
}

this makes it n^2, do you see why?

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

    I don't think it does since I'm not resetting "j"

    "j" doesn't decrease so it iterates over the string only one time and "i" is the same.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm not sure if that's the problem, but you didn't initialize j and sum.

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

    No it isn't because in C++ when you declare a variable outside of a function it automaticlly takes zero as a initial value.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      good to know, I always initialize my variables manually :D

      Anyways, I found the reason for your TLE. It's because of this part:

      pos = j;
while(pos <= i)
{
        if(s[pos] != '1' && max(pos - j , i - pos) < max(cur - j , i - cur))
            cur = pos;
        pos++;
}

      suppose the test case contains 100 000 zeroes, and k is 50 000. In this case your while loop will keep checking a range with length 50 000, repeating this checking for 50 000 times, which makes your total complexity O(n^2).

      → Reply