JADUGAR- Editorial

general
, , , ,
1

PROBLEM LINK:

Div1
Practice

Note: This editorial is a copy of the editorial of JADUGAR2, which is a very similar problem from the same contest.

Setter- Utkarsh Saxena
Tester- Misha Chorniy
Editorialist- Abhishek Pandey

DIFFICULTY:

HARD

PRE-REQUISITES:

Generating Functions, Fermat’s Little Theorem (for implementation and finding inverses), Prefix Array and our favorite topic, i.e, MATHS (Calculus, Solving quadratic equations &etc.), Finding Modular Inverses (O(N) time).

PROBLEM:

Given the recurrence relation such that-

  • dp(1)=K
  • If n>1, then dp(n)=A*dp(n-1)+B*\sum_{i=1}^{n-1} dp(i)*dp(n-i)

We need to calculate \sum_{i=L}^{R}{dp(i)}^{2} modulo ({10}^{9}+7) for Q queries where N,K,A,B are provided in input.

QUICK EXPLANATION:

This O({N}^{2}) recurrence is of no direct use to us - we must reduce it further. On further simplification, we are able to convert this recurrence into the following-

n*dp(n)=(2n-3)(A+2KB)*dp[n-1]-{A}^{2}(n-3)*dp[n-2]

Calculating dp(n) became trivial now by a single for loop. We can then, maintain a prefix-sum of the following dp[] array to answer the queries in O(1) time.

EXPLANATION:

This editorial will stress on solving this problem (and hence, problem JADUGAR as well) by the Generating Function technique. The solution of tester and setter are similar, and editorialist’s solution is derived from the same idea. The problem has little implementation and more conceptual derivation, so the editorial will attempt to tackle that. For implementations, refer to the code of Editorialist.

Setter/Tester/Editorialist’s Solution-

Notice that one of the methods to solve/find recurrence relations is Generating functions. Going by the standard technique, we make a (ordinary) generating function f(x) such that-

f(x)=S_1x+S_2{s}^{2}+S_3{x}^{3}....\infty

which is nothing by f(x)=\sum_{i=1}^{\infty}S_i{x}^{i}.

Note that the S_i, which is the coefficient of {x}^{i}, is nothing but dp(i). Allow me to represent dp(i) from henceforth as S_i for convenience.

Now, we know that-

S_n{x}^{n}=AS_{n-1}{x}^{n} + B\sum_{i=1}^{n-1} S_i*S_{n-i}{x}^{n}

Note that it is simply equivalent to multiplying L.H.S and R.H.S of our original relation by {x}^{n}. Now, we need to get rid of \sum_{i=1}^{n-1} S_i*S_{n-i}{x}^{n}. Thankfully, a property of generating function (as proved here ) comes to our rescue. We see that-

f(x)*f(x)=({\sum_{i=1}^{\infty}S_i{x}^{i}})^{2} =\sum_{i=1}^{\infty} S_i*S_{n-i}{x}^{n} (…from the above property.)

Now, notice that S_n{x}^{n}=AS_{n-1}{x}^{n} + B\sum_{i=1}^{n-1} S_i*S_{n-i}{x}^{n}

\implies \sum_{n=1}^{\infty}S_n{x}^{n}= Kx+ Ax\sum_{n=1}^{\infty}S_{n-1}{x}^{n-1}+B({\sum_{n=1}^{\infty}S_n{x}^{n}})^{2}.

Note that the Kx comes due to S_1.

Now we know that, f(x)=\sum_{i=1}^{\infty}S_i{x}^{i}

\therefore f(x)=Kx+ Ax*f(x)+B({f(x)})^{2}

Let us denote f(x) as g, so we have a quadratic equation-

g=Kx+Axg+B{g}^{2}

We can find the Generating function g (i.e. f(x)) by solving this quadratic equation. We get the result-

\large g=\frac{1-Ax\pm\sqrt{{A}^{2}{x}^{2}-(2A+4KB)x+1}}{2B}

You can take either sign of the \pm\sqrt{{A}^{2}{x}^{2}-(2A+4KB)x+1} term, you will get same recurrence relation. Lets go by the - sign for now.

We need to somehow get past this square root in our equation, because if we can do that, we can easily get the recurrence relation by collecting coefficients of {x}^{n}. Lets try playing with calculus!

Let {Q}^{2}={A}^{2}{x}^{2}-(2A+4KB)x+1.

We need an equation involving g without the square root. Can you give it a try? The hint is, differentiation! They are given under the two tabs, click them to proceed further if stuck!

Click to view

Notice that-

\large g=\frac{1-Ax\pm\sqrt{{A}^{2}{x}^{2}-(2A+4KB)x+1}}{2B}
\because {Q}^{2}={A}^{2}{x}^{2}-(2A+4KB)x+1
\implies 2Bg=1-Ax-Q........eq(1)

Differentiating both sides w.r.t. x-

2Bg'=-A-Q'
\implies Q'=-A-2Bg'..........eq(2)

Click to view

Notice that-
\because {Q}^{2}={A}^{2}{x}^{2}-(2A+4KB)x+1

Differentiating both sides w.r.t. x-

2QQ'=2{A}^{2}x-2A-4KB
QQ'={A}^{2}x-A-2KB

But we know Q' from eq(2)!!

\because Q'=-A-2Bg'

\large \implies Q=\frac{A+2KB-{A}^{2}x}{A+2Bg'}

\implies (A+2Bg')Q=A+2KB-{A}^{2}x...........eq(3)

From above, we are finally able to get eq(3) which is (A+2Bg')Q=A+2KB-{A}^{2}x

Now, multiply Q on both sides-

(A+2Bg'){Q}^{2}=Q(A+2KB-{A}^{2}x)

From previous equations, we already know the value of {Q}^{2} and Q!!. Refer to eq(1) and eq(2) for those. After substituting the appropriate values, we get something like-

(A+2Bg')({A}^{2}{x}^{2}-(2A+4KB)x+1)=(1-Ax-2Bg)(A+2KB-{A}^{2}x)

Now-

\because g=\sum_{n=1}^{\infty}S_n{x}^{n}
\implies g'=\sum_{n=1}^{\infty}nS_{n}{x}^{n-1}

Remember that our aim was to find dp(n), i.e. S_n. We know that S_n is nothing but the coefficient of {x}^{n} in the above relation. On collecting coefficients of {x}^{n}, we get-

(n+1)S_{n+1}=(2n-1)(A+2KB)S_{n}-{A}^{2}(n-2)S_{n-1}

\implies nS_{n}=(2n-3)(A+2KB)S_{n-1}-{A}^{2}(n-3)S_{n-2}

This, was the solution of JADUGAR.

For solving JADUGAR2, all we need to do is, compute the prefix sum. After calculating all values upto dp(n), we do an additional step-

dp(i)=dp(i-1)+dp(i)*dp(i) (of course, modulo ({10}^{9}+7) !!)

If we use one based indexing, then the answer for query Q L R is simply dp[R]-dp[L-1].

SOLUTION:

Setter
Tester
Editorialist

Time Complexity= O(N)

CHEF VIJJU’S CORNER:

**1.**Remember to give a read about Generating functions first. At first, few parts of proof will seem really difficult to grasp, but as you get acquainted with the basics involved, you will be able to do well here :). Also, dont hesitate to put request for derivation of any part which you could not work out.

**2.**You can refer to another good problem on Generating Function from ICPC here

**3.**During the contest, we saw many interesting solutions for JADUGAR which involved stuff like Gaussian Elimination, Inclusion-Exclusion Principle &etc. I would like to invite all those coders to explain their intuition and approach so that we can get a new perspective for this problem :slight_smile:

4. One interesting thing I would like to point out, is that we can see the costliness of \% operator in this problem. Look at editorialist solution and setter’s solution. Setter’s solution is nearly 4x fast that editorialist, due to very less use of \% operators. Whenever constraints go upto as high as {10}^{7}, its better to use expensive operators like *,/,\% etc. as reluctantly as possible.

5. For A=0, this problem becomes very similar to finding the n'th Catalan Number C_n. You can read about them here. :slight_smile:

6. Woe behold! For what I have in my possession! The ancient scrolls of knowledge and manipulation of Generating Functions which were used to construct the solution of this question itself!

Click to view

Ha! You think I will hand over the ancient treasure of scrolls that easily? Think twice!

Click to view

There is no treasure here :frowning:

7.

Click to view

alt text

alt text

I think thats it for this problem xD. If there is any more reference material which you guys want, do tell me. I will try to fit in the requests whenever possible :D.

8. The problems on Generating Functions arent easy to find :(. Lets solve that by making a list of related problems here. Community’s contribution appreciated!!