How to get 100pts in Euler Sum? I could get only 50.
1 Like
Not a single cpp solution of 100 pts 
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. 
@ hacker_sk : Yes exactly. Why all the accepted solution are in python?
Because it’s not so easy to handle overflow(upto 8000 digits) in cpp i think.
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.
5 Likes
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
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. 
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.
[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
5 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
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
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.
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