You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 05 Apr '18, 18:52

kr_abhinav's gravatar image

6★kr_abhinav
1213
accept rate: 20%

edited 06 Apr '18, 15:01

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 05 Apr '18, 19:08

kr_abhinav's gravatar image

6★kr_abhinav
1213
accept rate: 20%

edited 05 Apr '18, 19:09

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,643
×1,343
×887
×877
×25

question asked: 05 Apr '18, 18:52

question was seen: 655 times

last updated: 06 Apr '18, 15:01