Help:Modular Arithmetic.

general
1

I was doing this Problem : Count all Longest Common Sub sequences

I completely understand the editorial.
But when i went and look at others people solutions almost every one has used this approach(Not the one given in editorial)(Which too i understand completely):

1].Dynamic Programming Approach to solve “Length of longest common sub sequence”.

2].Dynamic Programming Approach to solve “No of longest common sub sequences”, using step 1.

Link to one of the sample solution

I am weak at Modular Arithmetic, so i got stuck at this part of above code:

if(dp1[i-1][j-1]==dp1[i][j-1])
                    dp2[i][j]=(dp2[i-1][j]+dp2[i][j-1]-dp2[i-1][j-1]+MOD)%MOD;

(I think it’s not hard to find this above piece of code).

Why we are adding MOD?

I know that is due to: (dp2[i][j]=(dp2[i-1][j]+dp2[i][j-1]-dp2[i-1][j-1]) can go negative.(I realized this when i looked at other solutions).

But unable to know How adding the MOD will fix the above issue??(Please Someone help).

2

suppose for certain values your answer goes negative somehow… Its just an additionary precaution taken. If u add mod to a +ve no then perform %mod then answer will remain same as when u perform %mod with that no alone. example suppose mod=5 and a=2. a%mod=a. (a+mod)%mod=(2+5)%mod=7%5=2. also if a=6 the a%5=1 and (a+mod)%mod=(11%5)=1. Now assume a=-2. Clearly -2 cant be an answer here as answer must be +ve. So we do (-2+mod)%mod=3. read congruency and congruence relations

3

The reason is simple. In every portion of the dp table, we are storing positive numbers which are LESS THAN MOD.

Now, in worst case, dp2[i-1][j] and dp2[i][j-1] can be 0, and dp2[i-1][j-1] can be (MOD-1).

We can understand like this-

Since we are storing %MOD in every part of table,

==>dp2[i-1][j], dp2[i][j-1] and dp2[i-1][j-1] is always less than MOD. (since its remainder)

Also, initially, we know that table does not have any negative number.

Now since no initial number is negative, I will prove that the numbers calculated using these will also be positive. Just have another look at a statement i said above-

in worst case, dp2[i-1][j] and dp2[i][j-1] can be 0, and dp2[i-1][j-1] can be (MOD-1).

For a number to be negative in the table, dp2[i-1][j-1] MUST be greater than dp2[i-1][j] +MOD+dp2[i][j-1] . But it will violate the fact that all numbers are less than MOD. Hence, this cannot hold.

Now, i can similarly prove that the numbers calculated by our newly found numbers will also be positive. And similarly we will fill up the entire table. The role of MOD comes when dp2[i-1][j] and dp2[i][j-1] are 0.

4

It is done to deal with negative numbers.

(-3) MOD 10 = 7

But (-3)%10 does not work like that in c++. It will give you -3 as output

So we do (-3 + 10) % 10 , i.e., 7%10 to get the answer as 7.

1 Like