arasmus's blog

Case of the Curious macro
By arasmus, history, 6 years ago, In English

35685511 <- This has a macro min() at line 12 35686050 <- This does not In the first case...the code at line 44 && 45 (query() function) runs twice....this gave a TLE ... but why? In the second case when the macro is removed...no TLE happens!

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

»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Imagine it like a binary tree. Each call to query function generates 2 further recursive calls. The height of tree will be O(logN). So, the complexity for query function will be O(2logN) = O(N). Thus, TLE.

In other code, the binary tree becomes a path of length O(logN) due to single recursive call which reduces complexity of query function to O(logN).

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ...but why is the query function is being called twice because of the macro? From what i can figure.... the macro gets replaced at compile time into actual code..and hence the query function must run just once

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      ans = min(ans, query())changes to ans = ((ans>query())?query():ans). That's why it is called twice, once for comparison and then for assignment.

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

        ah yes!! thanks...i should've noticed that

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      C/C++ macros are dumb text replacements so expression can be evaluated multiple times if it gets used multiple time. This is one of reasons why use of macros is discouraged in most professional c++ style guide (conditional compiling is an exception). I would also suggest avoiding them to beginners. Saving a few symbols might save some seconds for top participants but will not help beginners become red. The time debugging unexpected macro behaviour would be better spent getting better at algorithms and data structures. At least half the time macro can be replaced with different c++ feature that achieves the same but better.

      → Reply