Euler Sum Editorial (Unofficial)

Problem Link

contest link

practice link

PREREQUISITES

Beatty Theorem

Solution

The question is based on Beatty Theorem

Using the above theorem , for given irrational number alpha , you can calculate the the sum of first N terms of beatty sequence in O(log(N)) as follows :

Let S(α,n)=∑(k=1 -> n) ⌊αk⌋ for α some irrational positive number.

if α≥2 we let β = α −⌊α⌋ + 1 and you get

S(α,n) = S(β,n) + (⌊α⌋ - 1)∑(k=1 -> n)k = S(β,n) + (⌊α⌋ - 1) * n(n+1)/2

else if 1<α<2

if β satisfies α^−1 + β^−1 = 1 and m = ⌊αn⌋ , then

S(α,n)+S(β,⌊m/β⌋) =∑(k=1 -> m) = m(m+1)/2

Also, ⌊m/β⌋ = m − ⌈m/α⌉ = m−n = ⌊(α−1)n⌋.

Then, letting n′=⌊(α−1)n⌋ you have

S(α,n)=(n+n′)(n+n′+1)/2−S(β,n′)

This gives us a solution for O(log(N))

A naive implementation of the above would only fetch 50 points and would get TLE on the rest . To secure complete 100 few things need to be kept in mind :

  1. Integer Division is very very faster as comparative to decimal division , especially when numbers are of of order of 10^4000 .

  2. You convert a decimal into integer as follows :

if u want to preserve M digits of a decimal number e , then

new_e = e * ( 10 ** M )

thus e - 1 would change to new_e - 10**M , similarly for addition

for division a/b will change to ( new_a * 10**M ) // new_b

to find floor(e) you can use new_e // 10**M

These are the operations that need to performed with decimal numbers for this question .

This will make your code fast , but not enough , we need to do better .

  1. Division and multiplication by a power of 2 can be done a lot faster .

thus new_e = e << N , where N is some number that will preserve enough digits of e ,( for given question N = 26600 would suffice )

A careful implementation with above optimizations would get AC .

My AC solution

Note: You would have to calculate the value of e online . There many ways to do so , refer link

One of the fast ways to do so is link

1 Like

@hokagenaruto nice editorial there. Please use LaTex for formula and other stuff.It’s really convenient to read it.

2 Likes

is it possible to solve this problem using language C as I cannot find a way to input and perform computations for nos like 10^400 which is specified in the constraints.

Hey man nice editorial;) How do we store the value of n in C/C++ though??
I probably found a pattern! floor(1e)=2 and in the remaining sequence i.e. floor(2e)…,floor(ne), all the elements except the multiples of 4 (i.e. floor(4e),floor(8*e)) yield a result equal to 3 + result of the one prior to it… In the case of multiples of 4, they give 2 + result of the element prior. I think this can help us do in O(1) time!

Correct me if I am wrong :slight_smile:

@hokagenaruto Sorry,I dint understand.Can you please explain this with an example?

I used the continued fraction of e. This method is generally faster in getting answers for large numbers (the last 5 inputs). Here is my solution: https://www.codechef.com/viewsolution/14201562

There are also several other solutions using the continued fraction. Some of them even have about 0.67 secs for each of the last 5 inputs.

Mine may have some inefficiency in setting up the arrays. That is probably because I mainly do mathematics rather than coding.

1 Like

can anybody tell me why my code is givind wrong ans link

No , you cannot do this in O(1) , the Equidistribution theorem ( https://en.wikipedia.org/wiki/Equidistribution_theorem ) says that the fractional part will be equidistributed on (0,1) , thus no such pattern would exist .

Even if you find it true for a set on values , it wont always hold good.

Thanks for pointing that out… Can u pls explain a bit about that theorem?