How to get 100pts in Euler Sum?

How to get 100pts in Euler Sum? I could get only 50.

1 Like

Not a single cpp solution of 100 pts :stuck_out_tongue: waiting for editorial.

1 Like

Apparently all people who submit in cpp too did in python, i think to handle the overflow, I hope editorials are out soon. :smiley:

@ hacker_sk : Yes exactly. Why all the accepted solution are in python?

I saw your solution and the reason why it gets a WA is because of the imprecise value of e. Since n has a value of upto 10^4000 your e must be precise upto atleast 4000 digits.

However even with a precise value of e it times out. It is because division in python takes O(n^2) and the step a/=(a-1) takes 1.6*10^7 operations just for one divsion(I am assuming precise value of e).

So to rectify this you can use a continued fraction approach. A continued fraction gives a good approximation for e. For a given n we take a continued fraction of e for which the denominator is greater than n. This is to ensure precision. Then for the operation e=e/(e-1) since e=b/a we can write b=b-a and a will not change. Then the denominator also changes in the following steps. Now for generating the continued fraction for e look for oeis sequences – A007676,A007677,A113873,A113874.The first 2 are the values of numerator and denominator of convergents of e and the second 2 are their respective generators.

my solution.

5 Likes

My solution:
If we somehow express e as a fraction p/q then we will be able to calculate it as \sum_{i=1}^n [\frac{pi}{q}] in O(log n) time using this. To find p/q I used formula e=\sum_{i=1}^{\infty}\frac{1}{i!}\approx\frac{1}{k!}\sum_{i=1}^{k}\frac{k!}{i!} up to few thousand terms. Note that \frac{k!}{i!} is integer for i\leq k so we can have p=\sum_{i=1}^{k}\frac{k!}{i!} and q=k! but we still need to divide them by their gcd.

I first coded a solution in C++ using big integers but when submitting I learned that there is a source code limit (I guess to make it impossible to hardcode the digits of e) so I rewrote the solution in python because then I didn’t need to implement big integers. Without the source code limit it is solvable in C++ (although more painful).

The idea is to use continued fraction of e. For detail see: continued fraction of e. For a good enough approximation \frac{p_n}{q_n}, we have [ek]=[\frac{p_n}{q_n}k] for all k\le 10^{4000}. Here I used n=4001 in my code. Now the problem is to find \sum_{k=1}^{N}[\frac{p_n}{q_n}k]. There is a way to find this sum in a quick way and the runtime is equal to the runtime of finding gcd of p_n and q_n. For detail see: summing floor trick.

If you have got 50 it’s great. For 100 use Continued fraction of ‘e’ https://www.youtube.com/watch?v=CaasbfdJdJg then with some some math you’ll figure out.
Keep Coding. Have Fun. :slight_smile:

1 Like

If you have got 50 it’s great. For 100 use Continued fraction of ‘e’ [https://www.youtube.com/watch?v=CaasbfdJdJg][1] then with some some math you’ll figure out.
Keep Coding. Have Fun. :slight_smile:
[1]: https://www.youtube.com/watch?v=CaasbfdJdJg

Taylor Series approach

I see many people used continued fractions. Alternatively, you can solve this problem using 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!}

With that, I was able to separate numerator and denominator, used python int throughout while doing the summing floor trick for irrational numbers. Here’s link to my solution :slight_smile:

5 Likes

You could also spigot algorithm for digits of e. Sadly I didn’t get the gcd the like algorithm as mentioned by @phben rather was coding a sum of beatty sequence … and hence I got only 50 points

I used both spigot algo(that too optimized for fast output) for calculation of e and used floor optimization but my solution gave TLE for 2nd Subtask.
Please if anyone could figure out mistake it is thankful
https://www.codechef.com/viewsolution/14224131

Because it’s not so easy to handle overflow(upto 8000 digits) in cpp i think. :smiley:

Yes the source code limit is low for including Big Integer but 2 people @hacker_sk and @usaxena95 managed to get 50 points. Really great I believe.

2 Likes

Because of constraints on source limit size. to import your big integer library with fast multiplication, division and mod operations will exceed atleast 2000 bytes.

2 Likes

nice solution indeed. short and precise.

1 Like

Unfortunately, I couldn’t prove well why M=3000 was enough. I tried doing Taylor series error approximation for 4000 digits of e, which gives M=1465, but that solution gave me WA. Probably have something to do with summing floor trick. If someone can help me with a good proof to approximate taylor series value (with summing floor), I would appreciate that.

Wow! This is great.