JADUGAR2- Editorial

PROBLEM LINK:

Div1
Practice

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!!

4 Likes

How to prove this:
let n = N - 1
when dp(N) = Wolframalpha link

You can see it works here:
https://www.codechef.com/viewsolution/18128684

1 Like

@tautsjasiunsas I solved it similarly, and here is my proof:

I prefer to start with index 0, so the generating function of the sequence is given by

f(x) = \sum_{n=0}^{\infty} F_n x^n

Putting the definition of F_n similar to the editorial gives

f(x) = K + Ax f(x) + Bx f(x)^2 \\ f(x) = \frac{1 - Ax - \sqrt{(1 - Ax)^2 -4 KBx}}{2Bx}

Now the generating function of the Catalan numbers is

c(x) = \frac{1 - \sqrt{1 - 4x}}{2x} = \sum_{n=0}^{\infty}\frac{1}{n + 1}\binom{2n}{n} x^n

So,

f(x) = \frac{K}{1 - Ax} c\left(\frac{BKx}{(1 - Ax)^2}\right) \\ f(x) = \frac{K}{1 - Ax} \sum_{n=0}^{\infty}\frac{1}{n + 1}\binom{2n}{n} \frac{B^n K^n x^n}{(1 - Ax)^{2n}}

Expanding \frac{1}{(1 - Ax)^{2n + 1}},

f(x) = K \sum_{n=0}^{\infty}\frac{1}{n + 1}\binom{2n}{n} B^n K^n x^n \sum_{m=0}^{\infty} \binom{m + 2n}{2n}A^m x^m \\ f(x) = K \sum_{n=0}^{\infty}\sum_{m=0}^{\infty}\frac{1}{n + 1}\binom{2n}{n}\binom{m + 2n}{2n} B^n K^n A^m x^{n+m}

To get the coefficient of x^k, m + n = k. So F_k is given by

F_k = K \sum_{n=0}^{k} \frac{1}{n + 1}\binom{2n}{n} \binom{k + n}{2n} B^n K^n A^{k-n}
6 Likes

@meooow that coefficient was available on OEIS.

@meooow I used this link.

2 Likes

I had implemented exactly same O(N) logic with same recurrence relation. Had found that linear recurrence after enough maths. Link: https://www.codechef.com/viewsolution/18249742

But it could not pass all, gave TLE for three large inputs. Why? Can anyone explain?

Thank you for sharing it :slight_smile:

Really enjoyed this maths problem :slight_smile:

1 Like

In the generalized form with A, B, K? Could you share the link?

Sadly I didnt saw any python solution getting full points :frowning:

Code this in C++ adn try- I think you’re getting WA because of python being slow :frowning:

Thanx for sharing

By printing the pattern for first few terms,we get a sequence which could be searched in oeis,i too did it the same way,(not at all proud :frowning: )

Or try in pypy ,i too got tle in c++,bt ac in pypy.Try reducing modulo operation as much as possible,write

if (a>=mod) a%=mod everywhere

Yes, as I mentioned in bonus content- modulo takes a significant portion of time.

once i derived a reccurence for triangle read by rows,observed some similarity and then searched on oeis,though derived it later to confirm.

sort of hacking like on codeforces :frowning:

1 Like

@vijju123 How can a ‘slow’ python generate WA?

It’s a typo. xD xD. :slight_smile:
P.S. Even I have looked comment more than once. But didn’t noticed this. :slight_smile:

Can you explain how to use the final expression for F_k that you have mentioned to calculate all F_i (i=1 to N) in O(N) ? I’m not able to figure it out

1 Like

Thanks for sharing this. This solution was not anticipated by us. This allows to calculate F_k in O(K) time. But we wanted to enforce the calculation of all F[i]'s in O(N) time. This was the reason to add another version JADUGAR2.

2 Likes

“I was just testing your attention.”
-Vijju123 :slight_smile: xD xD :stuck_out_tongue:

PS: You never know- after you get the TLE removed, it can be WA :3

2 Likes