JADUGAR2- Editorial

general
, , , ,
21

I wanted to include this solution in editorial as well, but couldn’t get the desired proofs xD. Thanks for sharing here!! :slight_smile:

22

Well Played. :slight_smile: @vijju123 .

1 Like
23

@hemanth_1 I don’t think it can be don, at least I wasn’t able to. So this works for JADUGAR but not JADUGAR2. @usaxena95’s comment makes the situation clear.

24

Thanks, didn’t know this existed :smiley:

25

Searching on OEIS is just of the many ways to solve a problem and I don’t think badly of it, having done it many times myself :stuck_out_tongue:
I thought that it wouldn’t help in this problem because of the parameters A, B, K.

26

Exactly same code now passed all test cases in PyPy. Too disappointing :frowning:
https://www.codechef.com/submit/complete/18315028

1 Like
27

I know its disappointing, but its hard for us to set time limit for such cases. If we increase it too much, unoptimized ones pass, if we decrease it, then such issues occur. In the end the conclusion boils down to accepting the fact that faster languages such as C++ do have an edge in competitive coding, and we cannot make platform fair for all the languages- each one has its own set of pros and cons and we should focus on choosing the best language suited for problem rather than “one language for everything” approach. Hpe you understand :slight_smile:

2 Likes
28

This is cited on the OEIS for Schroder numbers :stuck_out_tongue:

29

I should be missing some math background but I can’t get how you get:
(n+1) Sn+1 = ((…)(…)) Sn - A²(n-2)Sn-1
from
(A+2Bg’)(A²x²-…) = (1-Ax-2Bg)(A +…)
What do you mean by counting or collecting coefficient of xn?

Can someone give more details or point to a link?

30

@sideralis - Yes, you are missing some background. Collecting coefficients is a common method used in last step of solving recurrence relations. I think Frobenius and Power-Series method come close to this, try having a look at them.

In the step you mentioned, we simply substituted the value of g and g' and found what is the coefficient of {x}^{n}

Were other parts of derivation clear to you? :slight_smile:

1 Like
31

Thanks @vijju123, with your explanation I understood what I was doing wrong (not shifting base of all sums to get only power of n). Now I got the same result. All other parts were clear for me.

32

I am glad to hear that :slight_smile: . I tried my best to make the mathematics portion as clear as possible so that those who dont know the topics can at least try learning them and derive the answer. I am glad its clear enough :smiley:

33

@vijju123 can u share any similar problems related to generating functions?

34

Did you check problem in point 2? Will have to search a bit.

35

Thanx i’ll check it out!!

By the way ,awesome editorials,crystal clear explaination.

If u do find any more related problem,please do add .

1 Like
36

Thanks for your words vivek. The problem is, most of problems with generating functions use the tag “Math” for it which makes differentiating and finding the problems difficult. Will add more as I find. :slight_smile:

37

You can add this :