Can someone explain why this problem cannot have a CPP solution?
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 ? 
2 Likes
@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.
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))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.
It ran in 0.38s on python :
https://www.codechef.com/viewsolution/14167966
3 Likes
This can’t have a solution for cpp…wht’s the use then? -_-
1 Like
Just one (lame, maybe) question, how is any codes’ the size calculated?
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 
1 Like
Indeed, the forum latex preview is inconsistent with the real thing. You can try changing \floor{} to \lfloor\rfloor
Any C++ soln of this problem??
because of the limit of the length of source code.
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~
1 Like
It looks cool! Could you please give us a brief idea about it?
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?
1 Like
I suggest you use just big integers instead of big decimals, which would cause a
significant speed up.
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.
2 Likes
the count of ASCII chars, including ‘\n’, ’ ', etc.
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 
)