MCHEF - Weirdest problem ever!?

Take a look at these two submissions made by me:

  1. http://www.codechef.com/viewsolution/7483130

Result: AC (for both tasks)

  1. http://www.codechef.com/viewsolution/7483167

Result: TLE (for second
task)

Note that the only difference between the two is that the 2nd one contains two lines extra;

#define min(a,b) ((a < b)?a:b)
#define max(a,b) ((a > b)?a:b)

Why is the 1st one AC but 2nd TLE!? o_O

Am I overlooking something that is insanely obvious?

Please Help!

Most probably this is the line that makes difference:

return min (queryUtil ( 2 * i + 1, a, mid, l, r ), queryUtil ( 2 * i + 2, mid + 1, b, l, r ) );

Your min macro makes additional function calls thus increasing the time which probably lead to TLE for 2nd subtask.

You should store those values in some temporary variables and then use your min(macro) or just use the default min function.

2 Likes

Yes one of the function calls will be done twice. It would be far better to use the built in function or convert your macro to a function. The preprocessor converts your macro to the following for the above example:

return ((queryUtil ( 2 * i + 1, a, mid, l, r ) < queryUtil ( 2 * i + 2, mid + 1, b, l, r )) ? queryUtil ( 2 * i + 1, a, mid, l, r ) : queryUtil ( 2 * i + 2, mid + 1, b, l, r );
1 Like

Aha! That completely slipped out of my mind! Thanks.

//