Global and local thing boggles my mind ! (TACNTSTR - Sept-Cook-off)

So there was this great question in the ‘September-Cook-Off 2016’ called ‘Counting strings’ ie ‘TACNTSTR’

I tried two solutions for this -

  1. by using ‘tmp’ as a global variable - CodeChef: Practical coding for everyone
  2. by using ‘tmp’ as a local variable to the main() - CodeChef: Practical coding for everyone

Solution with ‘tmp as local to main’ got accepted, while solution with ‘tmp as global’ results in TLE.

Is that a bug in the system or something really really tricky happening ?
Can someone please help me understand whats happening ?

1 Like

Your bug is due to repeatedly calling strlen(str) in the loop termination condition. strlen has a time complexity of O(n) and calling it everytime makes it O(n*n). Store it as a variable and it will get AC. Link

Why it passes when declared as a local variable is due to -O2 optimization. It is interesting such thing isn’t being done for globally declared variables, this provides good insight on that

3 Likes

Okay so using slrlen() every time was a silly mistake. Thanks for that :slight_smile:

But can their be a case when my code gets a TLE because of using a global variable ?

If yes, what is the solution ? should global only be used when it is REALLY required ? and we cant do like “Oh i declare everything global every time?”