PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Let make some observations. First of all, the resulting strings will contain no more than k digits, where k equals to the minimal length through all input strings. Sure, k*n is not greater than 100000. Consider some CNS. In common case, it contains some positive number of leading digits 4 followed by some number of digits 7. Let i - the number of digits 4 in our result (1 <= i <= k). Now we can start binary search by the number of digits 7 in the result (considering that there is exactly i digits 4) in order to find greatest number of digits 7 (let it be some j). (and then just add to the result integer j+1 for each i.) To do so we need to handle some function F(a, b) - what is the minimal number of changes needed to have CNS of set equals to string which contains exactly a digits 4 and b digits 7.
Imagine that you already have function F(a, b) written! And you can handle each query in time O(n*log(n)). This gives you total complexity O(knlog^2(n)). But you can use method of two pointers: if you are iterating i from k downto 1, then greatest j for each iteration is not less than prevision one. This simple observation gives you complexity O(knlog(n)). Pretty good!
Wait, this is not the end. You forgot about function F(a, b). Hm, try to think about it. Imagine some string s. You need to find the minimal number of replacings of characters ‘?’ by either 4 or 7 in order to make CNS of single string s equal to string of exactly a digits 4 and b digits 7. Let some character indexed i to be the last digit 4 of resulting string. This means that substring s[1…i] must contain no less number of non-7 digits (i. e. digits 4 or ?) than a, as well as substring s[i+1; |s|] must contain no less number of non-4 digits than b. For example, let s = 47477?7??7. We need to find F(3, 2):
| 4 | 7 | 4 | 7 | 7 | ? | 7 | ? | ? | 7 |
| x | x | x | x | x | . | . | . | x | x |
. denotes good i-positions, x - bad. You can notice that the set of good positions is represented as some segment [l; r], which you can find using binary search. Now you have some function in range [l; r], let it be f(i). f(i) = max(a-c4(i), 0) + max(b-c7(i), 0). c4(i) - the number of digits 4 in substrings s[1; i]. c7(i) - the number of digits 7 in substring s[i+1; |s|]. F(a, b) for s will be equal to minimum f(x), l <= x <= r. How to find it? f(i) is the sum of two functions. Function g(i) = max(a-c4(i), 0) is special - it decreases to some point c and then becomes always 0. On the other hand, g(i) = max(b-c7(i), 0) is equal to zero to some point d and then increases. What this gives to us? If c <= d, then F(a, b) is equal to zero (really, you can find position that already contains necessary string). In other case it is equal to minimum a-c4(i)+b-c7(i), d <= i <= c. Rewrite it: a+b-(c4(i)+c7(i)). Wow! Just find maximal c4(i)+c7(i) for all d <= i <= c. Thats can be done using RMQ. F(a, b) for all set is equal to sum of all F(a, b) for all n strings. That’s it.
So the final complexity is O(knlog(n)). In this problem there is a lot of corner cases - be careful in calculations of all segments and so.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.