LUCKYSWP - Editorial






If the result is of form 444…444 or 777…777 then any operation will not change the result, so we can try these cases separetely.

We can iterate integer x from 1 to n, for which s[x] = 4. We assume that digit in position x will be the last digit 4 of the result. If we do not want to make operation, the result for current x will be c4[x]+c7[x], where c4[x] is the number of digits 4 in s[1…x] and c7[x] is the number of digits 7 in s[x+1…n]. But we can try to improve that result by making a single operation. Let pair of integers (l, r) to be the chosen string before operation. We’ll consider that l <= x (other case is the simmetrical to current). In this case there are also two cases.

First is if r < x: if we choose such substring (l, r), of course, we need to transfer it to the right of x (because in other case we’ll not improve the result). Let d4 be the number of digits 4 the s[l…r] and d7 be the number of 7 in s[l…r]. After transfering s[l…r] exactly d4 will be subtracted from result for x, and exactly d7 will be added. So we just need to find such pair (l, r), 1 <= l <= r < x that d7-d4 is maximum possible.

Second case is if r >= x, i. e. current x will be at the substring that we choose (because l <= x and r >= x). You can notice that this case is actually the same like the first one. For example: let we have string 474474474777 and we choose the substring 474474[4747]77 and move it to 47[4747]447477. You can see that it is the same like to choose 47[4474]474777 and move it to 474747[4474]77. So we do not need to consider this case at all.

Now the problem is to find for all x maximum d7-d4 of all pairs (l, r), 1 <= l <= r < x, call it F[x]. Since we are iterating x from left to right, F[x] >= F[x-1], i. e. before x-th iteration we consider F[x] = F[x-1], but there may be better segment for which r = x. To find it we define t7[i] as the number of digits 7 in s[1…i] and t4[i] as the number of digits 4 in s [1…i]. We need to maximize d7-d4, rewrite it as (t7[x]-t7[l])-(t4[x]-t4[l]) => t7[x]-t7[l]-t4[x]+t4[l] => t7[x]-t4[x] - t7[l]+t4[l]. Since x is fixed we need to find such l that t4[l]-t7[l] is maximized. We can just keep it as a global parametr and refresh after each iteration of x.


Can be found here.


Can be found here.

Very bad explanation of the question and its solution