Блог пользователя M.A.H.M.O.O.D

help for finding out the reason behind TLE
Автор M.A.H.M.O.O.D, история, 8 лет назад, По-английски

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

:)

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится 
for( ; j <= i ; j++)
{
                    if(s[j] == '0')
                        break;
}

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

      → Ответить