Unofficial Editorial-Angry Grandfather(September Mega Cookoff-2019)

Problem Link : -

Hey, Guys!!

Grandfather is angry , so lets please solve this problem :-)

Part-1 discusses the brute-force solution which does not pass the test cases but clears up many thing about the problem.

For the real solution, refer Part-2 .

Part-1 : -

Say, M=4 and N=5

dp[i][j] means the number of sequences of length 'i' which have "j" prefix-sums divisible by “M” .

dp[1][0]=(number of sequences of length-“1” which has prefix not divisible by “M”–>[1],[2],[3])= 3

dp[1][1]=(number of sequences of length-“1” which has one prefix divisible by “M”–>[0])= 1

dp[2][0]=(number of sequences of length-“2” which has prefix not divisible by “M”–>[1,(0,1,2)],[2,(0,1,3)],[3,(0,2,3)])= 9

dp[2][1]=(number of sequences of length-“2” which has exactly one prefix divisible by “M”–>[0,(1,2,3)],[1,3],[2,2],[3,1])= 6

dp[2][2]=(number of sequences of length-“2” which has exactly two prefixes divisible by “M”–>[0,0])= 1

Final answer will be dp[n][k] + dp[n][k+1] + dp[n][k+2] + ...... + dp[n][n],
where,
dp[n][k]=number of sequences of length "n" with "k" good prefixes :slight_smile:

For our case, the dp-relation is given by : -

dp[i][j]= 3*dp[i-1][j] + dp[i-1][j-1]

Explanation:-

dp[i-1][j-1] means that these are guys which need just one correct value and they will become sequences of length “i” with “j” good-prefixes, each of them can be given only 1 good value, so if we have dp[i-1][j-1]=5, then 5-guys can become good :slight_smile:

Now, dp[i-1][j] is already good, we need to add wasteful values so number of prefixes remain “j” and length becomes “i

For each good guy, example:- 1, there are 3-values([0,1,2]…not 3, because 1+3=4, which will increase the length of array by 1 without affecting the number of good prefixes :slight_smile: ), which don’t make any change to number of good-prefixes :slight_smile:

Photo of the dp-table of this particular case :-

This is our lovely dp-but we can’t use it as it will give time-out :frowning:

Part-2 :-

Consider this sequence of length “4” and M=4

:–> 0132

Prefix array :-0,1,4,6

0 and 4 are divisible by “M”, so the answer is : - 2(as 2 numbers are divisible by “M”)

Now, consider prefix array Modulo M :- 0,1,0,2

[Solution:- Number of zeroes in prefix-modulo array will give us the answer]

Lets repeat!!:-:

Once a great man said,

Number of zeroes in prefix-modulo array will give us the answer

Now, dp[n][k]= number of ways to put k-zeroes in the prefix-modulo array.
If we can find this, we are done…

Say k = 1, m=5, n=4

What are the number of ways to put “1” zero in an array of length “4” ?

Here are the ways :-

x,x,x,0
0,x,x,x
x,0,x,x
x,x,0,x

(4-ways)

“Mathematics say that the number of ways to arrange k-zeroes in array of length-“n” is {(N)}C_{(K)}

There are basically, {(N)}C_{(K)}=4 ways to do this …(equation…a)

Now, for this one , say :-

x,x,x,0… what are the number of ways to give appropriate values to each “x” ?
x can be anything from [1,M-1] …so you agree that we have to fill (N-K) values with appropriate numbers ?

Number of ways to do this :- (M-1)^{N-K}

So the total number of ways(dp[n][k]) = 4 . (M-1)^{N-K} ={(N)}C_{(K)}. (M-1)^{N-K}…(as 4={(N)}C_{(K)} … fromequation -(a) :slight_smile: )

So, now we know how to calculate the answer for dp[n][k] :slight_smile:

Final answer, as mentioned in part-1 is :—>

dp[n][k] + dp[n][k+1] + dp[n][k+2] + ...... + dp[n][n]

Happy Coding

Once a wise man said, coding is easy if you understand everything clearly. Clarity is true power

1 Like

well i think it should be divisible by k rather than 0

1 Like

Divisible by M , not k . Corrected! Thanks!

@anon55659401 dp approach was awesome man…can you give me some tips how do you know where to apply dp…

2 Likes