Referring to this solution http://www.codechef.com/viewsolution/3331816 (got AC) for the question http://www.codechef.com/problems/CLMBSTRS, i came across teh confusion regarding modulo operator.
I initially framed the array fib[] this way
for(i=2;i<=MAX;i++)
{
fib[i]=(fib[i-1]%mod+fib[i-2]%mod);
}
and this gave WA. I, just in case,changed the above to
for(i=2;i<=MAX;i++) {
fib[i]=(fib[i-1]+fib[i-2])%mod; }
and this gave AC. As far as i know (a+b)%mod = a%mod + b%mod, then why such??
Not so.
Let a = 4 , b = 4 , p = 7 .
(a+b) mod p = 1
a mod p + b mod p = 8
3 Likes
Remeber this:
(a + b) m = ((a m) + (b m)) m
(a * b) m = ((a m) * (b m)) m
4 Likes
You still have to take modulo of the final result, (a + b) mod is not the same as a mod + b mod, you still need the modulo of the result: (a + b) mod = (a mod + b mod) % mod;
2 Likes
Hehe, I’ll beat you next time…
1 Like
Something about performance .
fib[0] = 0;
fib[1] = 1;
for(i=2;i<=MAX;i++)
{
fib[i]=fib[i-1]+fib[i-2];
if(fib[i]>=mod) {
fib[i] -= mod;
}
}
This would give best performance . Since each fib before already stored with respect to mod , fib[i-1] + fib[i-2] can be atmax 2*mod-2 . Hence a single subtraction is enough after checking if fib[i-1] + fib[i-2] is >= mod .
You may not be pressed for performance here , but i have encountered problems in codechef like SPMATRIX in which you get TLE if you use unnecessary use too many % operators
Please compare the time taken by my code and the code using % . You will see the difference .
Also , in (a+b)%mod = ( (a%mod) + (b%mod) ) % mod , two mod's are reduntant if a and b have already been stored with respect to mod . Optimizing the number of % operations is key to avoiding TLE in several medium and hard problems .
3 Likes