KFUNC - Editorial

PROBLEM LINK:

Practice
Contest

Author: Eugene Kazmin
Tester: Istvan Nagy
Editorialist: Xellos

DIFFICULTY:

CAKEWALK

PREREQUISITES:

none

PROBLEM:

You’re given a function F(n) and many queries of the form: find \sum_{k=L}^{R} F(A_1+kD). Answer the queries.

QUICK EXPLANATION:

Notice that F(n)=n%9. That means you only need the sum of any 9 consecutive terms and at most 9 other terms of the given arithmetic sequence to compute the answer.

EXPLANATION:

We can split the sum for a range [L,R] into sums for 2 ranges [L,M] and [M+1,R] for any M between L and R.

In order to solve this problem, we need one simple observation: F(x+9)=F(x). Yes, the function F is periodic with period 9, even though it’s defined in a complicated way! It’s actually quite easy to notice if you implement F(x) as described in the statement and print its values for some small ranges of consecutive numbers. When you have trouble solving a problem and 10 days to spend, it’s not a bad idea to play with it, print some values and try to see some useful property in them.

Note that the sum of digits of a number n can be computed in O(\log{n}) time and is usually much smaller than n, so there won’t be many iterations n \rightarrow digit\_sum(n) and even this implementation by definition is really fast. Still, since F(x)=x for x < 10 and F(x) is periodic, we can find a formula for it: F(x)=(x-1)\% 9 +1. This allows us to compute F(x) in O(1) time.

How to use periodicity in our problem, then? The key is that if we have 9 terms in our arithmetic sequence (R-L+1=9), then the answer is always the same for the same A_1,D (since the sum of a range [L+1,L+9] differs from the sum of the range [L,L+8] by F(A_1+D(L+9))-F(A_1+DL)=F(A_1+DL+9D)-F(A_1+DL)=0) and can be computed easily. Let’s denote this answer for a given A_1,D by ans_0. If R-L+1 is divisible by 9, then the answer is ans_0\frac{R+1-L}{9} - we split the range [L,R] into \frac{R+1-L}{9} ranges of 9 consecutive elements and the answer for each of them is the same. If R-L+1 < 9, we can simply bruteforce the answer. And if it’s not divisible by 9, but large enough, then we can split the range [L,R] into ranges [L,R-m] and [R-m+1,R] for m=(R+1-L)\% 9; the first range has the number of elements divisible by 9, so we know how to calculate the answer for it, and the second one has just m elements, so the answer for it can be bruteforced as well.

This means we can compute the answer in O(1) time and memory.

How large can the answers get? If D=0, A_1=9, L=1, R=10^{18}, then it’s 9\cdot 10^{18}, which fits into 64-bit signed integer types; since F(n) \le 9, that’s also the maximum. However, any relevant A_k can easily exceed this type’s range if D and L are large. Therefore, we have to carefully use modulos - or just stick to Python with its arbitrarily large integers (of course, with this size of data, we need fast I/O).

One more thing: we haven’t proved why F(x)=(x-1)\% 9+1. Let’s use mathematical induction. Let’s suppose that it holds for x < a; at the beginning, we know that it’s true for a=10. Now we want to prove it for x=a. It’s well-known that the sum of digits of a gives the same remainder mod 9 as a, since 10^j\% 9=1 \% 9 for any j and so

a \% 9 = \sum \left(d_j 10^j \% 9\right) =\left( \sum (d_j\% 9)\cdot(10^j \% 9)\right)\% 9 = \left(\sum d_j\right) \% 9

(d_j are the digits of a). If a \ge 10, we know that its sum of digits s is < a, so F(s)=(s-1)\% 9+1 and F(a)=F(s)=(s-1)\% 9 +1= (a-1)\% 9+1. Now we know that F(x)=(x-1)\% 9+1 holds for x \le a, so by induction, it holds for any x.

AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.

RELATED PROBLEMS:

2 Likes

I think

F(x)=9 iff x%9=0
1 Like

I prefer (x-1)%9+1, since it’s symmetric: F(x)-1=(x-1)\%9. Edited.

I tried to follow the same footsteps as I came across the repeating pattern much later but can anyone tell me why this code throws SIGBART https://www.codechef.com/viewsolution/8796320.
Also @author @admin @tester , I don’t know and neither I am very sure but the sum of the first 9 terms always ended up with 45. Is it a mere coincidence or there can be some proof behind this ? I tried to prove it with some 10’s complement arithmetic but no good.

-regards

Let D=3,A_1=1. The sum of the first 9 terms is 36. The sum of F of the first 9 terms depends on D and for some D also on A_1, but otherwise, it’s not constant. However, as mentioned in the editorial, it’s the same as the sum of F of any 9 consecutive terms for a given A_1,D.

Seems to be working fine with all the cases i tried including the sample ones. But showing WA on submitting in 3 test cases out of 10.
Link to my code: https://www.codechef.com/viewsolution/8806243
Help me out with it, thanks!

@namo21395 InYour Solution you are finding out the term a+=(l-1)*d which exceeds the range because (l-1)*d exceeds the range of the datatype you have declared. Instead try an alternating method to reduce the value of the nth term using %9.

https://www.codechef.com/viewsolution/8793763. why this code is giving only 40 pts??

Example case 2.
A = {14, 21, 28, 35, 42, 49, 56, 63, 70, 77, …}
A2 = 21
A3 = 28
A4 = 35
F(A2) = 3
F(A3) = 1
F(A4) = 8
3+1+8=12

How come F(A3) end up giving 1?
28>=10 so F(28)=10 ! Right?