PROBLEM LINK:
Author: Vitaliy Herasymiv
Tester: Anton Lunyov
Editorialist: Anton Lunyov
DIFFICULTY:
SIMPLE - EASY
PREREQUISITES:
PROBLEM:
You are given two strings of digits A and B. You can arbitrary reorder digits in A and in B. Then the string C with C[i] = max(A[i], B[i]) is created and all digits except 4 and 7 are removed from C. The goal is to find the lexicographically largest possible C.
EXPLANATION:
Since we can arbitrary reorder digits in A and B we can always achieve the final string C having all sevens in the beginning and all fours in the end. Hence we should maximize the total number of sevens in C and among strings with maximal number of sevens choose the string with maximal number of fours.
It is also clear that digits 8 and 9 do not influence on the answer. So we can remove them from A and B. If we replace some digit 5 by 6 or vice versa in one of the numbers answer also remains the same (max(d, 5) = 4 or 7 is equivalent to max(d, 6) = 4 or 7). Hence we can replace all digits 6 by digits 5 in both strings. Similarly we can replace all 1, 2, 3 by 0. So we obtain strings containing only digits 0, 4, 5 and 7, but possibly of different lengths.
Now at each step we will take some digit in A, some digit in B and put their maximum at the end of the answer string. We will assign some priority to each pair (d1, d2) of digits, where d1 and d2 are digits from the set {0, 4, 5, 7} such that max(d1, d2) equals to either 4 or 7 (there is no sense to consider other pairs). At each step we will consider the pairs according to their priorities. If for some pair (d1, d2) we can find d1 in A and d2 in B we remove d1 from A, d2 from B, put their maximum max(d1, d2) at the end of the answer string and proceed to the next step. If for all pairs we can’t find the corresponding digits in A and in B we finish the process. The answer in this moment will be the final answer. The pairs of digits are sorted by priorities in the following way: (7, 5), (5, 7), (7, 0), (0, 7), (7, 4), (4, 7), (7, 7), (4, 0), (0, 4), (4, 4).
The formal proof that this is correct is left as an exercise to the reader. Here we mention only intuitive reasoning that justifies this strategy.
-
If at some step we have 7 in A and 0 and 5 in B then it is better to form pair (7, 5) since 0 may help to form additional 4 in the future. Hence (7, 5) > (7, 0) in our priority list.
-
By the same reason (7, 0) > (7, 4).
-
If at some step we have 7 in A and 4 and 7 in B then it is better to form pair (7, 4) since 7 may help to form additional 7 in the future. Hence (7, 4) > (7, 7).
-
So we get (7, 5) > (7, 0) > (7, 4) > (7, 7).
-
Similarly we get (5, 7) > (0, 7) > (4, 7) > (7, 7).
-
If at some step we have 4 in A and 7 and 0 in B then it is better to form pair (4, 7) since pairing (4, 0) may decrease the total number of 7 in the answer. Hence (4, 7) > (4, 0).
-
If at some step we have 4 in A and 0 and 4 in B then it is better to form pair (4, 0) since 4 may help to form additional 4 in the future. Hence (4, 0) > (4, 4).
-
So we get (4, 7) > (4, 0) > (4, 4).
-
Similarly we get (7, 4) > (0, 4) > (4, 4).
-
In fact, any priority list that satisfies these 4 inequality chains is correct.
Now let’s analyze described above process and obtain more explicit algorithm. Denote by a[d] the number of digits d in A and by b[d] the number of digits d in B. Then to perform the described above process we simply need for each pair (d1, d2) in the priority list put k = min(a[d1], b[d2]) digits d to the end of the answer, where d = max(d1, d2) (and is equal either to 4 or to 7), and decrease both a[d1] and b[d2] by k. This approach is implemented in tester’s solution. Another way to perform this process is implemented in author’s solution.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Tester edition of author’s solution can be found here
