Omar_Hafez's blog

Explanation for the mathematical solution of atcoder problem E — Σ[k=0..10^100]floor(X／10^k)
By Omar_Hafez, history, 2 years ago, In English

Hello codeforces, I solved This problem from atcoder with the "Obvious" brute-force solution which is O(N). But when I take a look at the editorial I found a Beautiful mathematical solution that solves it in O(1) O(N) but with a lower constant factor, use lower memory and easy beautiful code. But unfortunately, I didn't understand it so Can anyone please explain it to me?

I really appreciate any help you can provide.

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I will just try to explain where the 9 comes from, without getting to the full solution. Let 

y = x + x/10 + x/100 + x/1000

Note there are only these 4 terms. Then, 

y = (1000x + 100x + 10x + x) / 1000
y = 1111x/1000
y = 9999x/9000
y = (10000x-x) / 9000
y = 10x/9 - x/9000
→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

And how exactly are you going to divide the number by 9 in O(1)?

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Will try to explain 2nd and 3rd rows of editorial.

For example, X=257 and answer is 257+25+2.

Let switch from integer to real and write formula to get an answer. It is:

(257-0)+(25.7-0.7)+(2.57-0.57)+(0.257-0.257)+(0.0257-0.0257)+... or

(257+25.7+2.57+0.257+0.0257+..) — (0+0.7+0.57+0.257+0.0257+..)

Rewrite the 2nd numbers as:

  • 0.7 = 7/10

  • 0.57 = 5/10 + 7/100

  • 0.257 = 2/10 + 5/100 + 7/1000

  • 0.0257 = 0 + 2/100 + 5/1000 + 7/10000

or

sumofdigits/10 + sumofdigits/100 + sumofdigits/1000 + ....

Taking into account the 1st comment we get the formula:

(10*X-sumofdigits)/9 — (10*X-sumofdigits)/(9*10^inf)

The 2nd member become to zero, so finally:

(10*X-sumofdigits)/9

Note, that it is exact answer, always integer :).

→ Reply