PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
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.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.