ES - Editorial (Unofficial)

Taylor Series approach (alternative solution)

I was able to solve this without continued fractions for 100pts. I’ll share the approach I commented on another question, since it seems relevant. Alternatively, we can also use Taylor Series of e:

e=\sum_{k=0}^\infty\frac{1}{k!}

For a good approximation, around M=3000 iterations is enough, and you can simplify:

e\approx\sum_{k=0}^M\frac{1}{k!}=\frac{\sum_{k=0}^M(M!/k!)}{M!}

I stored the numerator and denominator as big integers, and got accepted with python with similar summing floor trick found at part 1 above (*). Unfortunately, I am not able prove why M=3000 is enough, I would appreciate any comments. I tried to do the usual taylor approximation (which resulted to M=1465, but gave WA), so I would like some help in finding a better approximation method for taylor series with summing floor. Here’s a link to my solution :slight_smile:

1 Like

You solved it in JAVA or Python??? Which language you’ll recommend for such type of questions? (Since i didnt come across a C++ soln yet, i wanna know which language is msot user friendly for such questions :slight_smile: )

Usually python (or pypy) because int in python is automatically big integer. It’s more readable and math-friendly than java’s BigInteger, since operations are primitive. Though python is slower, CodeChef has 5x time limit multiplier for it anyway :smiley:

1 Like

Thanks!! :slight_smile: