Out of all the problems that were present in CodeChef Starters 44. I found this problem to be intriguing, the problem in itself is not difficult but the constraints require the solver to find a formula in O(1) time. So let's start with the problem link
To start with the problem it will be really easy if we think of the string like this 12233344445555... N is the length of the string, and before starting let's define some functions
- $$$ f1(N) = \dfrac{N.(N+1)}{2} $$$
- $$$ f2(N) = \dfrac{N.(N+1).(2N+1)}{6} $$$
- $$$ c(N) = $$$ No. of times N is present in the string
So the first step would be to find the smallest N' such that $$$ \dfrac{N'.(N'+1)}{2} > N $$$
We can use binary search to do this step.
For now, let's ignore the last number N' in the string because it will either be partially present or not present in the string, Something like this 12233344, N' = 4(partially present) and 122333, N' = 4(not present)
Step 1 — Observation
$$$ c(n) = n $$$, for all $$$ n < N' $$$ So, by excluding the last number N' we can find out the Beauty value of this string as $$$ B(S) = \sum\limits_{i = 1}^{N'-1}\sum\limits_{j = i+1}^{N'-1}c(i).c(j).(j-i) $$$
$$$ c(i) = i $$$ , $$$ c(j) = j $$$ as $$$ j < N' $$$ & $$$ i < N' $$$ , $$$ (j - i) $$$ is the value of the substring
for example, let's take the string 1223334444 So, if $$$ i = 2 $$$ , $$$ j = 4 $$$ we can cut the string in this way 1 | 2 | 2 3 3 3 4 | 4 | 4 | 4 |, if we can cut the string in this way the first char will be 2 and the last will be 4 and the value of that substring will be $$$ (j - i) $$$ , so no. of ways to make such a substring is $$$ i . j $$$ , and the total value that we will get by adding then up is $$$ i . j . (j - i) $$$ So the total value of the function will be found when $$$ i $$$ goes from $$$ 1 $$$ to $$$ N'-1 $$$ and $$$ j $$$ goes from $$$ i+1 $$$ to $$$ N'-1 $$$ and we do $$$ i . j . (j - i) $$$ , which is exactly $$$ B(S) $$$ .
But all this time we were ignoring the last digit $$$ N' $$$ , $$$ c(N') = N - f1(N'-1) $$$, and the value that we will get due to the presence of this last digit $$$ N' $$$ will be $$$ L(S) = \sum\limits_{i = 1}^{N'-1}c(N').i.(N'-i) $$$
By simplifying this formula we get
$$$ L(S) = c(N'). \left( N'.\sum\limits_{i = 1}^{N'-1}i - \sum\limits_{i = 1}^{N'-1}i^2 \right) $$$
$$$ L(S) = c(N'). \left( N'.f1(i) - f2(i) \right) $$$
This can be calculated using just the formula in O(1).
So redefining the Beauty value of the string as $$$ f_{beauty}(S) = B(S) + L(S) $$$.
$$$ f_{beauty}(S) = \sum\limits_{i = 1}^{N'-1}\sum\limits_{j = i+1}^{N'-1}c(i).c(j).(j-i) + c(N').\left( N'.f1(i) - f2(i) \right) $$$
Step 2 — Reducing the formula down
By now I guess all of you have noticed the $$$ B(S) $$$ can't be calculated in O(1) just yet, so let's solve that problem first $$$ B(S) = \sum\limits_{i = 1}^{N'-1}\sum\limits_{j = i+1}^{N'-1}c(i).c(j).(j-i) $$$
$$$ B(S) = \sum\limits_{i = 1}^{N'-1}\sum\limits_{j = i+1}^{N'-1}i.j.(j-i) $$$
$$$ B(S) = \sum\limits_{i = 1}^{N'-1}i\sum\limits_{j = i+1}^{N'-1}j^2 - \sum\limits_{i = 1}^{N'-1}i^2\sum\limits_{j = i+1}^{N'-1}j $$$
$$$ \sum\limits_{i = 1}^{N'-1}i\sum\limits_{j = i+1}^{N'-1}j^2 = \left(\sum\limits_{i = 1}^{N'-1}i\right)\left(\sum\limits_{j = 1}^{N'-1}j^2\right) - \sum\limits_{i = 1}^{N'-1}i\sum\limits_{j = 1}^{i}j^2 $$$
$$$ \sum\limits_{i = 1}^{N'-1}i\sum\limits_{j = i+1}^{N'-1}j^2 = \left(\sum\limits_{i = 1}^{N'-1}i\right)\left(\sum\limits_{j = 1}^{N'-1}j^2\right) - \sum\limits_{i = 1}^{N'-1}i.f2(i) $$$
Now we see that the 2nd part can be calculated in O(1) using prefix Sum.
$$$ \sum\limits_{i = 1}^{N'-1}i^2\sum\limits_{j = i+1}^{N'-1}j = \left(\sum\limits_{i = 1}^{N'-1}i^2\right)\left(\sum\limits_{j = 1}^{N'-1}j\right) - \sum\limits_{i = 1}^{N'-1}i^2\sum\limits_{j = 1}^{i}j $$$
$$$ \sum\limits_{i = 1}^{N'-1}i^2\sum\limits_{j = i+1}^{N'-1}j = \left(\sum\limits_{i = 1}^{N'-1}i^2\right)\left(\sum\limits_{j = 1}^{N'-1}j\right) - \sum\limits_{i = 1}^{N'-1}i^2.f1(i) $$$
Now we see that the 2nd part can be calculated in O(1) using prefix Sum.
Now, $$$ B(S) = - \sum\limits_{i = 1}^{N'-1}i.f2(i) - \left( - \sum\limits_{i = 1}^{N'-1}i^2.f1(i) \right) $$$
$$$ B(S) = \sum\limits_{i = 1}^{N'-1}i^2.f1(i) - \sum\limits_{i = 1}^{N'-1}i.f2(i) $$$
So this part can also be calculated in O(1).
Finally, the total beauty value of the string is $$$ f_{beauty}(S) = \sum\limits_{i = 1}^{N'-1}i^2.f1(i) - \sum\limits_{i = 1}^{N'-1}i.f2(i) + c(N').\left( N'.f1(i) - f2(i) \right) $$$
