maniratnagupta's blog

By maniratnagupta, history, 6 years ago, In English

Your text to link here...

why this solution is time limit exceeded.

COuld anyone help me,please.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Consider input 00000... 0011... 11111. Do you see why your algorithm has quadratic time complexity?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry I am new to this coding I don't know what is a time complexity

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Well basically if some algorithm has time complexity O(x) that means it does amount of basic actions (like adding, subtracting, indexing an array, etc.) that is proportional to x in worst case where x is some function of input size.

      For example, if we say n is the size of input string of 0's and 1's, then your solution's time complexity is O(n2) because if the answer is 0 it has to remove "01" or "10" n / 2 times and each removal is done by rebuilding the whole string so it also takes n actions for the first time, n - 2 for the second, n - 4 for the third and so on, which is roughly n2 / 4 if summed up (it's actually more). So your solution's amount of basic actions in the worst case is 0.25 * n2, which is linearly proportional to n2, so its time complexity is O(n2).

      So, n's maximum value in the problem is 2 * 105, and your solution does 0.25 * n2 in the worst case, so your worst case is 1010 actions, which is impossible to squeeze into one second (moreover, on C#).

      I'm not an expert (though my rank states so), but I can say C# can easily do 106 actions in one second, so probably you should find a solution which time complexity is O(n) so it does about 105 actions and maybe a little more.

      UPD: in competitive programming, algorithm's time complexity usually very well represents its speed. In other words, if you plug in your maximum values for input size variables in time complexity's function and see that the number you get is about 106 or less, then you're good to go and your solution will probably pass the time limit. Very rare are cases in which that does not work, because if you came up with a solution which time complexity is the same as the problem's real full solution, then these two are probably the same (and are easiest to come up with)