You are not logged in. Please login at www.codechef.com to post your questions!

×

ES - Editorial (Unofficial)

10
2

PROBLEM LINK:

Practice
Contest

Author: Gaoyuan Chen
Editorialist: Tiny Wong

DIFFICULTY:

HARD.

PREREQUISITES:

Beatty sequence, Continued fractions.

PROBLEM:

Given $n \leq 10^{4000}$, calculate the sum $$ \sum_{k=1}^n \left\lfloor k \mathrm{e}\right\rfloor, $$

where $\mathrm{e} = 2.718\dots$ is Euler's number.

QUICK EXPLANATION:

Let $S(n, \alpha) = \sum\limits_{k=1}^n \left\lfloor k \alpha \right\rfloor$. If $1 < \alpha < 2$, we can get that $$ S(n, \alpha) = \frac 1 2 (n+n') (n+n'+1) - S(n', \beta), $$

where $n' = \left\lfloor (\alpha-1)n \right\rfloor$ and $\beta = \dfrac \alpha {\alpha-1}$.

EXPLANATION:

1. Universal Solution

Let $\alpha > 0$ be an irrational number. Then the sequence $B_\alpha = \{ \left\rfloor \alpha \right\rfloor, \left\rfloor 2\alpha \right\rfloor, \dots, \left\rfloor n\alpha \right\rfloor, \dots \}$ is a Beatty sequence, whose prefix sum is denoted as $$ S(n, \alpha) = \sum_{k=1}^n \left\rfloor k \alpha\right\rfloor. $$

If $\alpha > 2$, let $\beta = \alpha-1$, then $$ S(n, \alpha) = \sum_{k=1}^n \left\lfloor{k \alpha}\right\rfloor = \sum_{k=1}^n \left\lfloor{k \beta + k}\right\rfloor = \sum_{k=1}^n \left\lfloor{k \beta}\right\rfloor + \sum_{k=1}^n k = S(n, \beta) + \frac 1 2 k (k+1). $$

If $\alpha < 1$, let $\beta = \alpha+1$, then $$ S(n, \alpha) = S(n, \beta) - \frac 1 2 k (k+1). $$

Then we can assume that $1 < \alpha < 2$.

Here is an important theorem for solving this problem.

Theorem (Rayleigh). Let $\alpha$ and $\beta$ be two irrational numbers with $\dfrac 1 \alpha + \dfrac 1 \beta = 1$, then $B_\alpha$ and $B_\beta$ partition the set of positive numbers, i.e. $B_\alpha \cup B_\beta = \mathbb{N}^+$ and $B_\alpha \cap B_\beta = \emptyset$.

By Rayleigh Theorem, if $1 < \alpha < 2$, let $\beta = \dfrac \alpha {\alpha - 1}$, $m = \left\lfloor{n \alpha}\right\rfloor$ and $n' = \left\lfloor{\dfrac m \beta}\right\rfloor$, then $$ S(n, \alpha) + S(n', \beta) = \sum_{i=1}^m i = \frac 1 2 m ( m+1 ). $$

Note that $$ n' = \left\lfloor{\frac m \beta}\right\rfloor = \left\lfloor{\frac {m(\alpha-1)} \alpha}\right\rfloor = m - \left\lceil{\frac m \alpha}\right\rceil = m-n = \left\lfloor{(\alpha-1)n}\right\rfloor, $$

Then $$ S(n, \alpha) = \frac 1 2 m ( m+1 ) - S(n', \beta) = \frac 1 2 (n+n') (n+n'+1) - S(n', \beta). (*) $$

If $1 < \alpha < 2$, $n' = \left\lfloor{(\alpha-1)n}\right\rfloor < (\alpha-1)n < n$, we can calculate $S(n, \alpha)$ by $(*)$.

2. Continued Fractions

A positive irrational number $\alpha$ can be written as a continued fraction $$ \alpha = a_0 + \dfrac 1 {a_1 + \dfrac 1 {a_2 + \dfrac 1 {a_3 + \ddots}}}, $$

where $\{ a_0, a_1, a_2, \dots \}$ is an infinite sequence and $a_1, a_2, \dots \in \mathbb{N}^+$. We can use the shorthand $$ \alpha = [a_0; a_1, a_2, a_3, \dots]. $$

Note that the integer part of $a$ is $[\alpha] = a_0$, and the fraction part is $$ \{ \alpha \} = [0; a_1, a_2, a_3, \dots]. $$

And $$ \frac 1 {\{ \alpha \}} = [a_1; a_2, a_3, \dots]. $$

In the former analysis, we assume that $1 < \alpha < 2$, as a result $a_0 = 1$, and $$ \beta = 1 + \frac 1 {\alpha - 1} = 1 + \frac 1 {\{ \alpha \}} = [a_1+1; a_2, a_3, \dots]. $$

$$ n' = \left\lfloor{(\alpha-1)n}\right\rfloor = \left\lfloor{\{\alpha\} n}\right\rfloor < \frac n {a_1}. $$

3. Complexity Analysis

Now we describe the algorithm formally. Let $\alpha^{(0)} = \alpha$ and $n^{(0)} = n$. Now for each $k$, consider the calculation of $S(n^{(k)}, \alpha^{(k)})$. Let $\alpha^{(k)} = [a_0^{(k)}; a_1^{(k)}, a_2^{(k)}, a_3^{(k)}, \dots]$.

Let $n^{(k+1)} = \left\lfloor{ \{\alpha^{(k)}\} n^{(k)}}\right\rfloor$,$\beta^{(k)} = 1+\dfrac 1 {\{\alpha^{(k)}\}}$, by $(*)$, $$ S(n^{(k)}, \alpha^{(k)}) = \frac 1 2 (n^{(k)}+n^{(k+1)}) (n^{(k)}+n^{(k+1)}+1) - S(n^{(k+1)}, \beta^{(k)}). $$

Notice that $$ \beta^{(k)} = [a_1^{(k)}+1; a_2^{(k)}, a_3^{(k)}, \dots]. $$

And then $$ S(n^{(k+1)}, \beta^{(k)}) = S(n^{(k+1)}, \beta^{(k)}-a_1^{(k)}) + \frac 1 2 a_1^{(k)} n^{(k+1)} (n^{(k+1)}+1). $$

If we let $\alpha^{(k+1)} = \beta^{(k)}-a_1^{(k)} = [1; a_2^{(k)}, a_3^{(k)}, \dots]$, then $a_1^{(k+1)} = a_2^{(k)} = \dots = a_{k+1}^{(0)}$, and we get that $$ S(n^{(k)}, \alpha^{(k)}) = \frac 1 2 (n^{(k)}+n^{(k+1)}) (n^{(k)}+n^{(k+1)}+1) - \frac 1 2 a_{k+1}^{(0)} n^{(k+1)} (n^{(k+1)}+1) - S(n^{(k+1)}, \alpha^{(k+1)}). $$

Note that $$ \alpha^{(k)} = [1; a_k^{(0)}, a_{k+1}^{(0)}, \dots]. $$

and that $$ \begin{aligned} n^{(k+1)} & = \left\lfloor{\{\alpha^{(k)}\} n^{(k)}}\right\rfloor = \dots \\ & = \left\lfloor{\{\alpha^{(k)}\}}\right\rfloor \left\lfloor{\{\alpha^{(k-1)}\}}\right\rfloor \dots \left\lfloor{\{\alpha^{(0)}\}}\right\rfloor n^{(0)} \\ & < \{\alpha^{(k)}\} \{\alpha^{(k-1)}\} \dots \{\alpha^{(0)}\} n^{(0)}. \end{aligned} $$

Let $\gamma^{(k)} = \dfrac 1 {\{\alpha^{(k)}\}} = [a_1^{(k)}; a_2^{(k)}, a_3^{(k)}, \dots] = [a_{k+1}^{(0)}; a_{k+2}^{(0)}, a_{k+3}^{(0)}, \dots]$, then $$ n^{(k+1)} = \frac {n^{(0)}} {\gamma^{(k)} \gamma^{(k-1)} \dots \gamma^{(0)}}. $$

Note that $$ \gamma^{(k-1)} = a_{k}^{(0)} + \frac 1 {\gamma^{(k)}}, $$

i.e. $$ \gamma^{(k)} \gamma^{(k-1)} = a_{k}^{(0)} \gamma^{(k)} +1. $$

Here we have $\gamma^{(1)} \gamma^{(0)} = a_1^{(0)} \gamma^{(1)} + 1$. We may assume that $\gamma^{(k)} \gamma^{(k-1)} \dots \gamma^{(0)} = p^{(k)} \gamma^{(k)} + q^{(k)}$, and then

$$ \begin{aligned} & \quad \gamma^{(k+1)} \gamma^{(k)} \gamma^{(k-1)} \dots \gamma^{(0)} \\ & = \gamma^{(k+1)} (p^{(k)} \gamma^{(k)} + q^{(k)}) \\ & = p^{(k)} \gamma^{(k+1)} \gamma^{(k)} + q^{(k)} \\ & = p^{(k)} \left( a_{k+1}^{(0)} \gamma^{(k+1)} +1 \right) + q^{(k)} \gamma^{(k+1)} \\ & = \left(p^{(k)}a_{k+1}^{(0)}+q^{(k)}\right) \gamma^{(k+1)} + p^{(k)} \\ & = p^{(k+1)} \gamma^{(k+1)} + q^{(k+1)}. \end{aligned} $$

As a result, $p^{(k+1)} = p^{(k)}a_{k+1}^{(0)}+q^{(k)}$ and $q^{(k+1)} = p^{(k)}$, and then $$ p^{(k+1)} = p^{(k)} a_{k+1}^{(0)}+p^{(k-1)} \geq p^{(k)}+p^{(k-1)}. $$

Note that $p^{(0)} = 1$ and $p^{(1)} = a_1^{(0)} \geq 1$, then $p^{(k)} \geq f_k$, where $\{ f_k \}$ is the Fibonacci sequence, which is $f_0 = f_1 = 1$, and $f_k = f_{k-1}+f_{k-2}$ for all $k \geq 2$。

Again we have $$ \begin{aligned} & \quad \gamma^{(k)} \gamma^{(k-1)} \dots \gamma^{(0)} \\ & = \frac {\gamma^{(k+1)} \gamma^{(k)} \gamma^{(k-1)} \dots \gamma^{(0)}} {\gamma^{(k+1)}} \\ & = \frac {p^{(k+1)} \gamma^{(k+1)} + q^{(k+1)}} {\gamma^{(k+1)}} \\ & = p^{(k+1)} + \frac {p^{(k)}} {\gamma^{(k+1)}} \\ & \geq p^{(k+1)}+p^{(k)} \\ & \geq f_{k+1}+f_{k} = f_{k+2}. \end{aligned} $$

Then $$ n^{k+1} = \frac {n^{(0)}} {\gamma^{(k)} \gamma^{(k-1)} \dots \gamma^{(0)}} \leq \frac {n^{(0)}} {f_{k+2}} = \frac {n} {O(\phi^{k})}, $$

where $\phi = \dfrac {1+\sqrt5} 2$.

As a result, the number of iterations of $(*)$ is $O(\log n)$。

4. Details

In practice, we need only two values, which are $n^{(k)}$ and $\{ \alpha^{(k)} \}$ and can be calculate by the followings.

$$ \begin{aligned} & n^{(k+1)} = \left\lfloor{ \{ \alpha^{(k)} \} n^{(k)} }\right\rfloor, \\ & \{ \alpha^{k+1} \} = \left\{ \frac 1 {\{\alpha^{(k)}\}} \right\}. \end{aligned} $$

Algorithm 1. Calculate all floating numbers after dealing the errors.

Algorithm 2. Use continued fractions instead of painful floatings.

An irration number $\alpha$ can be approximated by a sequence of continued fractions $$ \{ [a_0], [a_0; a_1], [a_0; a_1, a_2], \dots, [a_0; a_1, a_2, \dots, a_n], \dots \}. $$

whose each term is an approximate representaion of $\alpha$ and the precision is increasing.

Suppose the $k$-th term of the above sequence is $\dfrac {P_k} {Q_k}$, then $$ \frac {P_k} {Q_k} = \frac {a_k P_{k-1} + P_{k-2}} {a_k Q_{k-1} + Q_{k-2}}. $$

What we are facing is to calculate $n^{(k+1)} = \left\lfloor{ \{ \alpha^{(k)} \} n^{(k)} }\right\rfloor$. If $\{ \alpha^{(k)} \} \approx \dfrac P Q$ with $Q > n$, then we can just calculate it forward $$ n^{(k+1)} = \left\lfloor{ \frac {P n^{(k)}} Q }\right\rfloor. $$

No matter which algorithm you choose, the overall time complexity is $O(\log^2 n \log \log n)$. That is because $O(\log n)$ for iterations, $O(\log n \log \log n)$ for big integer multiplications and divisions (More precisely, multiplication is $O(\log n)$ and division is $O(\log n \log \log n)$).

ALTERNATIVE SOLUTION:

There may be other ways to solve the problem, please share!

EDITORIALIST'S SOLUTIONS:

Editorialist's solution can be found here.

asked 12 Jun, 17:59

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6622211
accept rate: 12%

edited 12 Jun, 19:12

Any C++ soln of this problem??

(12 Jun, 18:15) vijju123 ♦4★
1

@vijju123 There are no C++ solutions because of the limit of the length of source code.

(12 Jun, 18:23) liouzhou_101 ♦♦7★

My solution uses this awesome paper : T.C. Brown and P.J.-S. Shiue, Sums of fractional parts of integer multiples of an irrational, J. Number Theory 50 (1995), 181–192.

http://people.math.sfu.ca/~vjungic/tbrown/tom-27.pdf

It ran in 0.38s on python : https://www.codechef.com/viewsolution/14167966

link

answered 12 Jun, 19:00

abhash_yadav's gravatar image

3★abhash_yadav
413
accept rate: 0%

It looks cool! Could you please give us a brief idea about it?

(12 Jun, 19:08) liouzhou_101 ♦♦7★
2

I am basically using lemma 4. In the first part, we are calculating the p/q form for e till q < Number. using continued fraction approach and storing then in num , denom array.

in the solver function :

S(N) = solution for N,

since N > qn , we write :

N = b * qn + k, from lemma 4:

S(b * qi + c) = S(b * qi) + S(k) + k * b * pi

S(b * qi) = (1/2) b(term) where term = b * pi * qi - qi + pi + (-1)^i here qi is ith denominator, similarly for pi.

we find qi for K, and using same above forumula, solve for S(K). this will surely end, since q0 and q1 are 1. recursion wont work.

(13 Jun, 17:38) abhash_yadav3★

My preview is correct. I don't know why it looks awful T_T!

link

answered 12 Jun, 18:01

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6622211
accept rate: 12%

Indeed, the forum latex preview is inconsistent with the real thing. You can try changing \floor{} to \lfloor\rfloor

(12 Jun, 18:08) hikarico6★
1

@hikarico It was a hard time for me. Now it looks correctly.

(12 Jun, 18:22) liouzhou_101 ♦♦7★

Only a suggestion, but can we have lesser problems of these types that need intense research and have less reusability in other contests. Being one of the hardest problems the research and efforts do pay off but I personally would like to see problems with rarer paradigms/algorithms that can be used (at least partially) in short contests for hard problems like reduction to multiple usual algorithms and they fit together in some complex way, etc

Like SANDWICH problem last time was good, I actually learned Wilson's Theorem, Lucas Theorem and bunch of other mathematical properties - they weren't enough to get full but still useful for other contests. To get full I had to get into generalized Lucas that paid off with 100 points.

Anyways just a suggestion, the problem set was good and challenging for my level.

On a side note, Is it just me that haven't seen a medium-hard DP problem in a top 7 - 8 most solved problems in Long recently ? :D

link

answered 12 Jun, 18:49

chiragjn's gravatar image

5★chiragjn
1113
accept rate: 28%

1

I think there are some ideas from ES that can be used in the short contests. I ever met a similar problem in short contests, which also calculates the sum but this time $e$ becomes a simple fraction, i.e. calculates the grid point in the triangle, and to solve this problem also needs such ideas.

After all, these problems are "projecteuler"-style problems.

And the same as you, I would like some medium DP problems in long challenge too~

(12 Jun, 19:03) liouzhou_101 ♦♦7★

This can't have a solution for cpp...wht's the use then? -_-

link

answered 12 Jun, 19:12

foxtron's gravatar image

3★foxtron
21313
accept rate: 0%

1

I also complain that there are no cpp solutions. However, I think the author's making the source code limit under 1000 bytes is to tell us there are no complex codes but cute ideas?

(12 Jun, 19:18) liouzhou_101 ♦♦7★

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 :)

link

answered 17 Jun, 17:17

hikarico's gravatar image

6★hikarico
1.7k414
accept rate: 26%

edited 17 Jun, 17:31

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 :) )

(17 Jun, 17:38) vijju123 ♦4★
1

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 :D

(17 Jun, 17:41) hikarico6★

Thanks!! :)

(17 Jun, 17:43) vijju123 ♦4★

Can someone explain why this problem cannot have a CPP solution?

link

answered 12 Jun, 18:33

ayushgupta321's gravatar image

1★ayushgupta321
1
accept rate: 0%

because of the limit of the length of source code.

(12 Jun, 18:41) liouzhou_101 ♦♦7★

@ayushgupta321 it has to do with the precision of $e$. In order to compute this Beatty sequence with $n \leqslant 10^{4000}$, $e$ must have a $4000$-digit precision at least. I think this is too much for cpp.

link

answered 12 Jun, 18:52

sysm's gravatar image

2★sysm
111
accept rate: 0%

I actually used the formula from Quick Explanation section but alas got only 50 pts. Decimal is too slow and generating e upto 4000 digits takes me 4.5s and N as large as 10^4000 takes about <= 2000 recursion depth to decay to zero

from sys import stdin, stdout
from decimal import Decimal as D, getcontext as gc, ROUND_FLOOR

def s(a, n):
    if n == 0:
        return 0
    _n = ((a - D(1)) * n).to_integral_exact()
    b = a / (a - D('1.0'))
    k = b.to_integral_exact() - D(1)
    b = b - k
    n_n = n + _n
    tmp = (n_n * n_n)
    tmp = tmp + n_n
    tmp = tmp - (k * (_n) * (_n + D(1)))
    tmp = tmp / D(2)
    tmp = tmp - s(b, _n)
    return tmp

m = stdin.readline()
gc().prec = min(len(m) * 2 + 3, 4003)
gc().rounding = ROUND_FLOOR

m = D(m)
e = D('1.5')
f = D('0.5')
for i in range(3, 1506):
    f = f / D(i)
    e = e + f

ans = ((D(m) * D(m + 1))/D(2)) + s(e, m)
stdout.write(str(ans))
link

answered 12 Jun, 18:54

chiragjn's gravatar image

5★chiragjn
1113
accept rate: 28%

I suggest you use just big integers instead of big decimals, which would cause a significant speed up.

(13 Jun, 07:22) liouzhou_101 ♦♦7★

Just one (lame, maybe) question, how is any codes' the size calculated?

link

answered 16 Jun, 16:23

dkp11's gravatar image

3★dkp11
11
accept rate: 0%

the count of ASCII chars, including '\n', ' ', etc.

(17 Jun, 14:30) liouzhou_101 ♦♦7★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,344
×872
×452
×148
×24

question asked: 12 Jun, 17:59

question was seen: 2,116 times

last updated: 17 Jun, 17:43