Why is the usage of a boolean flag variable instead of an int flag variable causing a TLE?

ankitmaity · August 27, 2018, 11:33pm

Problem code: PRIME1 (warning for fast IO is included)

Slow IO with boolean: https://www.codechef.com/viewsolution/19890625 (TLE)

Slow IO with int: https://www.codechef.com/viewsolution/19890658 (0.94s AC)

Fast IO with int: https://www.codechef.com/viewsolution/19892348 (0.93S AC)

Fast IO with boolean and no flushing: https://www.codechef.com/viewsolution/19892367 (TLE)

Fast IO with int and no flushing: https://www.codechef.com/viewsolution/19892381 (0.92s AC)

This means the program bottleneck must be in the boolean flag variable, but why?

john_smith_3 · August 28, 2018, 1:12am

I’m not convinced.

My guess:

https://www.codechef.com/viewsolution/19892367 fails because the inner loop goes up to i/2 instead of j*j<=i
https://www.codechef.com/viewsolution/19890625 fails perhaps because it uses long, where int is sufficient

If I take your solution https://www.codechef.com/viewsolution/19890658, and convert it to use booleans in https://www.codechef.com/viewsolution/19893108, then the boolean version passes.

Can you really produce two solutions, identical except for swapping int for bool, where the bool takes significantly longer?

ankitmaity · August 28, 2018, 9:25am

@john_smith_3 Indeed it seems as if the long and the first unoptimised inner loop is to blame. Retried with all the best optimizations except for using int loop counters and got a TLE. It’s not the boolean clearly (I suspected boolean must mostly be faster due to clearing lesser memory allocation and repeated assignments, so I was surprised with this outcome), but what you said clears it up. Thanks a lot.