CIELNUM3 - Editorial

anton_lunyov · July 23, 2012, 12:11am

PROBLEM LINK

DIFFICULTY

MEDIUM

PREREQUISITES

PROBLEM

You need to find the largest x-pseudo Ciel number less than or equal to N. Definition of x-pseudo Ciel number is rather cumbersome. See QUICK EXPLANATION for equivalent simple definition. Here we recall only that the number K is called Ciel number if and only if d(K, 8) >= d(K, 5) >= d(K, 3), where d(K, i) is the number of digits i in decimal representation of K.

OVERVIEW

The problem brought to us enormous number of wrong solutions. Most of the contestants had wrong logic with function D(d3, d5, d8, L) defined below or assumed that the answer will always have the same length as N. We provide some popular tests on which most of the solutions failed:

Input:
4
3 553533553553
2 33338888
0 1
0 10

Correct output:
553533553548
33338888
-1
8

QUICK EXPLANATION

For positive integer K with L digits in decimal representation denote by D(K) the minimal number of digits that should be replaced in K to get the Ciel number with L digits. We will also call D(K) as a distance from K to Ciel numbers. The number K is x-pseudo Ciel number if and only if D(K) = x (see paragraph 1 in EXPLANATION for proof).

Clearly D(K) depends only on d(K, 3), d(K, 5), d(K, 8) and len(K), where len(K) is the number of digits in decimal representation of K. Denote by D(d3, d5, d8, L) the distance to Ciel numbers from the number with L digits having d3 digits 3, d5 digits 5 and d8 digits 8.

Let’s show how D(d3, d5, d8, L) can be calculated in O(1) time. Assume that the Ciel number which we want to obtain from the given number has a3 digits 3, a5 digits 5 and a8 digits 8, where a3 + a5 + a8 = L and a3 <= a5 <= a8. Then the minimum number of replacements is max{a3 - d3, 0} + max{a5 - d5, 0} + max{a8 - d8, 0} (see paragraph 2 in EXPLANATION for proof). We need to find the minimum of this sum over all appropriate triples (a3, a5, a8). In fact this minimum achieves on one of the following 4 triples (see paragraph 3 in EXPLANATION for proof):

(d3, L – d3 – d8, d8) - replacement of all non-Ciel digits by 5.
(d3, floor((L – d3) / 2), floor((L – d3 + 1) / 2)) - nearly equal a5 and a8 with a3 = d3.
(floor((L – d8) / 2), floor((L – d8 + 1) / 2), d8) - nearly equal a3 and a5 with a8 = d8.
(floor(L / 3), floor((L + 1) / 3), floor((L + 2) / 3)) - nearly equal a3, a5 and a8.

To solve the problem we need to be able to solve quickly the following sub problem. Does there exist the number K with len(K) = L and fixed prefix of length k which has n3 digits 3, n5 digits 5 and n8 digits 8, for which D(K) = x? Denote the answer to this question by exist(n3, n5, n8, k, L, x). Then exist(n3, n5, n8, k, L, x) = true if and only if D(n3, n5, n8, L) – L + k <= x <= D(n3, n5, n8, L). We left this as an exercise to the reader.

It is convenient to increase N by 1 and search for strictly smaller than N x-pseudo Ciel numbers. Let N = A₁A₂…A_L be decimal representation of N. At first let’s try to find the largest x-pseudo Ciel number less than N with exactly L digits. For this we need to find at first the largest 1 <= k <= L and for this k the largest 0 <= y < A_k such that there exists x-pseudo Ciel number of length L starting at A₁…A_k-1y. This can be made by iterating k from L to 1 and iterating y from A_k - 1 to 0 for each k using function exist. If such k and y exist we can restore the whole answer trying for each of the remaining positions digits in decreasing order using exist routine. If such k does not exist then for L > 1 and x < L the answer has length L-1 and composed of x digits 9 and L – x digits 8, otherwise the answer is -1.

EXPLANATION

1. Why K is x-pseudo Ciel number if and only if D(K) = x?

Recall the definition of x-pseudo Ciel numbers.

A positive integer K is a 0-pseudo Ciel number if and only if K is a Ciel number.
For x >= 1, a positive integer K is x-pseudo Ciel number if and only if K is not y-pseudo Ciel number for all 0 <= y < x, and there exists (x-1)-pseudo Ciel number S such that len(S) = len(K) and S has exactly one digit differ from K in their decimal representations.

Let’s prove our assertion using induction by x. For x = 0 all is clear since only Ciel numbers have distance 0 to Ciel numbers. Now let x >= 1 be fixed and assume that for all 0 <= y < x it is already proved that K is y-pseudo Ciel number if and only if D(K) = y.

At first consider some number K for which D(K) = x. Then clearly K is not y-pseudo Ciel number for all 0 <= y < x by the induction hypothesis. On the other hand making one appropriate replacement of digit in K we can get some number S such that D(S) = x – 1 (and so S is (x-1)-pseudo Ciel number) and S has exactly one digit differ from K in their decimal representations. Hence by definition of x-pseudo Ciel number K is x-pseudo Ciel number.

Now consider some x-pseudo Ciel number K. Clearly D(K) >= x since otherwise K is y-pseudo Ciel number for some 0 <= y < x (namely for y = D(K)). On the other hand taking number S from the definition of x-Ciel number we get D(S) = x – 1 and |D(K) – D(S)| <= 1 since S and K differ in exactly one digit in their decimal representations. Hence D(K) = (D(K) - D(S)) + D(S) <= |D(K) - D(S)| + D(S) <= 1 + (x - 1) = x. Thus D(K) <= x and D(K) >= x. Hence D(K) = x which proves our assertion.

2. Why distance between (d3, d5, d8, L) and (a3, a5, a8, L) is max{a3 - d3, 0} + max{a5 - d5, 0} + max{a8 - d8, 0}?

Note that if a8 > d8 then we definitely need to do at least a8 – d8 replacements of some digits other than 8 in order to get a8 digits 8 in the end. Similarly we need to do at least a5 – d5 replacements if a5 > d5 to get the required number of digits 5 and the same for digit 3. Clearly all these replacements are different so we need at least max{a3 - d3, 0} + max{a5 - d5, 0} + max{a8 - d8, 0} replacements to get (a3, a5, a8, L) from (d3, d5, d8, L). Proof of the fact that this number of replacements is sufficient is left as an exercise to the reader.

3. Why minimum of max{a3 - d3, 0} + max{a5 - d5, 0} + max{a8 - d8, 0} always achieves on one of the 4 mentioned triples?

Consider the triple (a3, a5, a8) that gives minimum to the function max{a3 - d3, 0} + max{a5 - d5, 0} + max{a8 - d8, 0} subject to the conditions 0 <= a3 <= a5 <= a8 and a3 + a5 + a8 = L.

At first note that there is no sense to transform digits into digit 3. Indeed, if we replace some digit i by 3 then we can safely replace it by 8 with saving inequalities 0 <= a3 <= a5 <= a8. Hence we can assume that a3 <= d3 for our triple (a3, a5, a8).

Let’s prove that we can additionally assume that for our triple either a3 = d3 or a5 <= a3 + 1. If a3 = d3 then it is already true. Let a3 != d3. Since a3 <= d3 then a3 < d3. If additionally a3 + 2 <= a5 let’s replace our triple (a3, a5, a8) by (a3 + 1, a5 - 1, a8). The new triple is a correct one since 0 <= a3 +1 <= a5 - 1 <= a8 and (a3 + 1) + (a5 - 1) + a8 = a3 + a5 + a8 = L. Moreover, since a3 < d3 then max{(a3 + 1) – d3, 0} = max{a3 – d3, 0} = 0, max{(a5 - 1) – d5, 0} <= max{a5 – d5, 0} and hence

max{(a3+1)-d3, 0} + max{(a5-1)-d5, 0} + max{a8-d8, 0} <= max{a3-d3, 0} + max{a5-d5, 0} + max{a8 -d8, 0}.

Thus for the triple (a3 + 1, a5 - 1, a8) the goal function is not greater then for the triple (a3, a5, a8). Repeating this process we always reach a triple that gives minimum for the goal function for which either a3 = d3 or a5 <= a3 + 1, which proves our assertion.

Another observation that can be made is that there is no sense to transform existing digits 8 to other digits. Indeed, the only case when this can be needed is when d3 > d5 and there is not enough other digits to get sufficient number of digits 5 so we need to transform digits 8 to digits 5. But clearly it is advantageous to replace digits 3 instead. There exists a formal proof of this fact using expression max{a3 - d3, 0} + max{a5 - d5, 0} + max{a8 - d8, 0}. We leave this as an exercise to the reader. Hence we can assume that a8 >= d8 for our triple (a3, a5, a8).

Let’s prove that we can additionally assume that for our triple either a8 = d8 or a8 <= a5 + 1. The arguments will be very similar to the above but for the readers’ convenient we give them completely. If a8 = d8 then it is already true. Let a8 != d8. Since a8 >= d8 then a8 > d8. If additionally a5 + 2 <= a8 let’s replace our triple (a3, a5, a8) by (a3, a5 + 1, a8 - 1). The new triple is a correct one since 0 <= a3 <= a5 + 1 <= a8 – 1 and a3 + (a5 + 1) + (a8 - 1) = a3 + a5 + a8 = L. Moreover, since a8 > d8 then max{(a8 - 1) – d8, 0} = max{a8 – d8, 0} - 1, max{(a5 + 1) – d5, 0} <= max{a5 – d5, 0} + 1 and hence

max{a3-d3, 0} + max{(a5+1)-d5, 0} + max{(a8-1)-d8, 0} <= max{a3-d3, 0} + max{a5-d5, 0} + max{a8-d8, 0}.

Thus for the triple (a3, a5 +1, a8 - 1) the goal function is not greater then for the triple (a3, a5, a8). Repeating this process we always reach a triple that gives minimum for the goal function for which either a8 = d8 or a8 <= a5 + 1, which proves our assertion.

Note that both transformations on triples described above decrease difference a8 – a3 by 1. Hence after the finite number of steps we reach the triple (a3, a5, a8) for which both of the following conditions are satisfied:

either a3 = d3 or a5 <= a3 + 1.
either a8 = d8 or a8 <= a5 + 1.

Now it is left to consider 4 cases:

a3 = d3 and a8 = d8. Then a5 = L – a3 – a8 = L – d3 – d8. So the corresponding triple has the form (d3, L – d3 – d8, d8) and coincides with the first one in the above list of 4 triples.
a3 = d3 and a8 <= a5 + 1. Conditions a5 + a8 = L – d3 and a5 <= a8 <= a5 + 1 imply a5 = floor((L – d3) / 2) and a8 = floor((L – d3 + 1) / 2). So the corresponding triple coincides with the second triple from the above list.
a5 <= a3 + 1 and a8 = d8. Similarly to the previous case we get that a3 = floor((L – d8) / 2) and a5 = floor((L – d8 + 1) / 2). So we get the third triple from the above list.
a5 <= a3 + 1 and a8 <= a5 + 1. Since a3 <= a5 <= a8 it means that numbers a3, a5, a8 are nearly equal. It is left as an exercise to the reader to prove that in this case minimum is achieved on the 4th triple from the above list.

SETTER’S SOLUTION

Can be found here.
Setter used the approach described above with some small differences in notation.

TESTER’S SOLUTION

It coincides with the setter’s solution.

EDITORIALIST’S SOLUTION

Can be found here.
It is an exact implementation of the described approach with very minor notation differences.