CMPVIRS - Editorial

PROBLEM LINK:

Contest
Practice
Author:Tapish Pratap Singh
Tester:Arnab Samanta
Editorialist:Tapish Pratap Singh

DIFFICULTY:

Hard

PREREQUISITES:

Math, Combinatorics, Pascal Triangles

EXPLANATION:

The sequence in the question is the generalisation of Moessner sequencce. In Moessner sequence d_1=d_2=........d_{m-1}=d_{m}.
Consider N=8, m=2, d_1=d_2=4

alt text
As we can observe every group satisfy the Pascal property (each interior element is the sum of the elements immediately above it and to its left).
Lets add a new row and column of 1’s in the first group.

alt text
Pascal Traingle

Similarly for Second group add a new row of 1’s and a column containing previously marked numbers,
alt text
Now we will represent the above sequence algebraically using Pascal triangle.
Let h_k(x,y) be the algebraic representation of the kth triangle.
So, h_k(x,1) will be the polynomial having coefficients as the marked numbers for the kth triangle then,

Each triangle is obtained from the previous by taking the homogeneous component of degree diff_k, and multiplying by ∆(x,y) and then putting y=1 in the obtained triangle.

h_{k+1}(x,y)=[h_k(x,1)*∆(x,y)]_{d_k} and h_0(x,1)=1 where d_k is the size of group k and

∆(x,y) =\frac{1}{1-(x+y)}=(x+y)^0+(x+y)^1+(x+y)^2+...=\sum_{d=0}^{\infty}(x+y)^d

(Note:-∆(x,y) is the algebraic representation of pascal triangle.
The nth north-east to south-west row of the pascal triangle will be:-
[[\Delta(x,y)]_{n-1}]_{y=1}=(1+x)^{n-1})

which simplifies to

h_k(x,1) = \prod_{i=0}^{k-1}((k-i)*x+1)^{diff_i}) where diff_i=d_i-d_{i-1} and d_0=0

Now what we require is the sum of all marked numbers in the original group which is:h_k(x,1)-1 (subtracting 1 as we added the rows of 1’s ,so 1 needed to be subtracted)

Final ans:-
\sum_{k=1}^{m}(h_k(x,1)-1)

Eg:-
Consider n=4,m=2,d_1=d_2=2
now h_0(x,1)=1
now
h_1(x,y)=[h_0(x,1)*∆(x,y)]_2=[1*((x+y)^0+(x+y)^1+(x+y)^2+...)]_2=(x+y)^2
h_2(x,y)=[h_1(x,1)*∆(x,y)]_2=[(x^2+2x+1)(1+x+y+x^2+y^2+2xy+...)]_2=4x^2+4xy+y^2
now h_1(x,1)=1+2x+x^2 represents the first modified triangle
alt text
and
h_2(x,1)=1+4x+4x^2 represents the second modified triangle
alt text

TIME COMPLEXITY:

O(m*m*log(max(diff[i])))

SOLUTIONS:

18052824
18052829

1 Like

For some reason, the note is being rendered incorrectly despite showing correctly in the editing tab, the actual equation is
alt text