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

general
, , , ,
1

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 - https://www.codechef.com/viewsolution/11566448
  2. by using ‘tmp’ as a local variable to the main() - https://www.codechef.com/viewsolution/11566447

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
2

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
3

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?”