Alternating Strings CodeChef Starters 44

Правка en5, от shadow_47, 2022-06-23 09:20:21

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

Formula Image Solution

Теги mathematics, codechef, starters

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский shadow_47 2022-06-23 09:32:34 14 Tiny change: 'echef.com/submit/ALT7STR)\' -> 'echef.com/problems-old/ALT7STR)\'
en6 Английский shadow_47 2022-06-23 09:22:15 6
en5 Английский shadow_47 2022-06-23 09:20:21 63
en4 Английский shadow_47 2022-06-23 09:18:35 8 Tiny change: 'tal value we will get but adding th' -> 'tal value that we will get by adding th'
en3 Английский shadow_47 2022-06-23 09:17:22 4 Tiny change: 'if we can the strin' -> 'if we can cut the strin'
en2 Английский shadow_47 2022-06-23 05:19:43 101
en1 Английский shadow_47 2022-06-23 05:14:16 4544 Initial revision (published)