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
:)
this makes it n^2, do you see why?
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.
I'm not sure if that's the problem, but you didn't initialize
j
andsum
.No it isn't because in C++ when you declare a variable outside of a function it automaticlly takes zero as a initial value.
good to know, I always initialize my variables manually :D
Anyways, I found the reason for your TLE. It's because of this part:
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).
Thank you very much.
:)
You are very welcome :D