LUCKY10 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vitaliy Herasymiv
Tester: Anton Lunyov
Editorialist: Anton Lunyov

DIFFICULTY:

SIMPLE - EASY

PREREQUISITES:

Greedy algorithm

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.

  1. 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.

  2. By the same reason (7, 0) > (7, 4).

  3. 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).

  4. So we get (7, 5) > (7, 0) > (7, 4) > (7, 7).

  5. Similarly we get (5, 7) > (0, 7) > (4, 7) > (7, 7).

  6. 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).

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

  8. So we get (4, 7) > (4, 0) > (4, 4).

  9. Similarly we get (7, 4) > (0, 4) > (4, 4).

  10. 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

RELATED PROBLEMS:

LUCKY5
SPOJ - 416. Divisibility by 15 - DIV15

We need make sure that maximum 7’s are in string C so for that we need make sure following…
For every 7 in a string we has to remove a number < 7 the counter string prioritizing (5,6),(1,2,3,0),(4) this assure as that maximum number of 7’s are in string c with minimum removal of 4’s(in worst case)
next for every remaining 4 in a string we has to remove a number < 4 the counter string prioritizing (1,2,3,0)
Additionally we need make sure that count of 7’s += min(remaining 7’s in A , remaining 7’s in B).
Finally we need make sure that count of 4’s += min(remaining 4’s in A , remaining 4’s in B)
As the following one solution

2 Likes

When I tried to translate what you wrote, instead of pairs from editorial

(7, 5), (5, 7), (7, 0), (0, 7), (7, 4), (4, 7), (7, 7), (4, 0), (0, 4), (4, 4)

your priorities were

(7, 5), (7, 0), (7, 4), (5, 7), (0, 7), (4, 7), (4, 0), (0, 4), (4, 4), (7, 7)

is there something else?

In my solution (http://www.codechef.com/viewsolution/1440012) I used

(7, 5), (7, 0), (7, 4), (5, 7), (0, 7), (4, 7), (7, 7), (4, 0), (0, 4), (4, 4)

and it worked too :wink:

1 Like

The only condition that priority list should satisfy are the following:
(7,5) > (7,0) > (7,4) > (7,7)
(5,7) > (0,7) > (4,7) > (7,7)
(7,4) > (0,4) > (4,4)
(4,7) > (4,0) > (4,4)
“>” means higher priority.
So, any priority list with these inequalities will be fine.

@betlista The end of your list should be: (4, 0), (0, 4), (4, 4). And it is really so in your solution.

2 Likes

@anton_lunyov Thanks for correction :wink: (fixed)