PaleBlueDot's blog

Code's runtime depends on the way I'm declaring the MOD value
By PaleBlueDot, 3 months ago, In English

I was trying the problem Coin Combinations II on the CSES platform, where I encountered a strange behaviour. Firstly my code got rejected with the TLE verdict, but as soon as I changed the way I declared the variable MOD (1e9 + 7), the code got accepted.

In the first code, I globally declared MOD as long long MOD = 1e9 + 7; which led to TLE. While in the second code, I globally defined MOD as #define MOD (long long)(1e9 + 7); which led to my code getting accepted. I just wanted to know the reason behind this difference in the runtime depending on the way I declare the variable MOD.

Code that gave TLE

Code that got AC

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Another code that gets accepted (added const to mod): https://cses.fi/paste/96c0c55ef85ac10a9ab595/

Taking modulo is a expensive operation and compilers can optimize modulo if the mod is constant. When you define the mod like that it is inserted in the code so it is constant. Another way is defining the variable constant and that would also let the compiler know the mod is constant.

→ Reply
»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I also was doing a problem today, and with me defining mod as: int MOD=whatever; it ran accepted in 1500 ms however, when I ran this code const int MOD=whatever; it ran in like 400 ms

much more efficient!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A better way to use MOD in this case is:

DP[j] = DP[j - c[i]] + DP[j];
if(DP[j]>=MOD) DP[j]-=MOD;
→ Reply