 # DEFACING - Editorial

Practice

Contest

EASY

## PREREQUISITES

Brute force, Greedy

## PROBLEM

We are given an integer S represented in a 7-segment display. Add some segments or digits into it to create the as large number as possible not larger than M.

## QUICK EXPLANATION

Since we want to maximize the number, it is always optimal to make S contain the same number of digits as M (assume that we allow leading zeros). Hence, there are two steps in the solution:

• Add some digits before S and some digits after S in such a way that the resulting length is equal to M's length.
• Add some segments in such a way to maximize the resulting number.

We can perform all possible ways of the first step using brute force. For each intermediate result after the first step, the second step can be performed using greedy. Finally, we output the largest resulting number over all ways.

## EXPLANATION

First, let’s introduce a compatibility matrix valid[i][j] = whether digit i can be transformed into digit j by adding some segments. The value of each cell of the matrix can be computed by hand. Here are the values:

```\ 0123456789
+----------
0|1000000010
1|1101100111
2|0010000010
3|0001000011
4|0000100011
5|0000011011
6|0000001010
7|1001000111
8|0000000010
9|0000000011
```

Let’s go through the steps in more details.

### Step 1

Let |X| be the number of digits of X. As mentioned before, in an optimal solution the number of digits of M and S must be equal. There are exactly |M| - |S| + 1 possible ways to add new digits. For example, suppose S = 89375 and M = 9247529. Then, there are 3 ways:

• Add 0 digits before S and 2 digits after S: 89375XX
• Add 1 digits before S and 1 digits after S: X89375X
• Add 2 digits before S and 0 digits after S: XX89375

Here, the new digits are represented by X’s for convenience. Let’s call the new integer after adding some digits as S*.

### Step 2

Note that the restriction that the resulting number must not have leading zeros is so that we cannot have the length resulting number is greater than |M| but that difference of length consists of all leading zeros. If that is allowed, then for test case like S = 0, M = 9 we can have 09 as the resulting number, hence making the problem trickier. Since we have in our solution that |S| = |M|, we can safely ignore that restriction.

For each possible intermediate result of Step 1, we must replace each X by an actual digit and optionally add some segments to the existing digits. We can use a greedy method here. We will iterate S* from the most significant digit through the least significant digit. For each digit, we try to transform it into the largest digit, while maintaining that the final result is not greater than M. This way, it can be proved that the result is the largest possible.

When iterating the digits from the most significant digit through the least significant digit, the choice of the current digit depends on the current prefixes of M and S*. Suppose we are now considering the i-th most significant digit. The current state would be like this:

```M  = Pp...
S* = Qq...
^
i-th most significant digit
```

where p and q are M anp S*'s i-th most significant digits, respectively, while P and Q are M and S*'s current prefixes, respectively. The (i+1)-th through the |M|-th digits are not considered yet. For example, let M = 9247529, the currently built S* = 89375XX, and i = 4, then the current state is:

```M  = 9247...
S* = 8937...
^
4-th most significant digit
```

where P = 924, Q = 893, p = 7, and q = 7.

For each state, i.e. for each step in the iteration, there are 2 possibilities to maintain that the resulting number is not greater than M:

q > p. Here, Q must be strictly less than P because otherwise the resulting number would be greater than M.

q ≤ p. Here, Q must be less than or equal to P.

From the above explanation, let’s maintain two values while iterating the digits:

• prefix_less = the maximum prefix of S* that is strictly less than the corresponding prefix of M, or -1 if there is no such prefix
• prefix_equal = the corresponding prefix of M, or -1 if we cannot have equal prefix for M and S*

We update the two values after each step in the iteration. In the end, we choose the iteration that yields the maximum value. Please consult the following pseudocode for more details. The time complexity of this solution is O(|M|^2).

```// returns the maximum possible resulting number
// if we align the first digit of S with the k-th digit of M
// or -1 if it is impossible.
function solve(M, S, k):
prefix_less = -1
prefix_equal = 0
for i = 1; i ≤ |M|; i++:
// if the resulting number must be greater than M, then impossible
if prefix_less == -1 and prefix_equal = -1
return -1
// update prefix_less
for d = 9; d ≥ 0; d--:
// if we cannot transform the digit, continue.
if i ≥ k and i ≤ k + |S| - 1 and not valid[S[i - k + 1]][d]:
continue
// found the largest valid digit.
// if the new digit is greater than the current digit, use prefix_less
if d > M[i]:
if prefix_less != -1:
prefix_less = prefix_less * 10 + d
// if the new digit is not greater than the current digit, use either prefix_less or prefix_equal
else if prefix_less != -1:
if max(prefix_less, prefix_equal) != -1:
prefix_less = max(prefix_less, prefix_equal) * 10 + d
break
// update prefix_equal
if i ≥ k and i ≤ k + |S| - 1 and not valid[S*[i - k + 1]][M[i]]:
prefix_equal = -1
else
prefix_equal = prefix_equal * 10 + M[i]
return max(prefix_less, prefix_equal)

// the main code

best = 0
for k = 1; k ≤ |M| - |S| + 1; k++:
best = max(best, solve(M, S, k))
print(best)```

## SETTER’S SOLUTION

Can be found here.

## TESTER’S SOLUTION

Can be found here.

3 Likes

Correction:

``````for d = 9; d ≤ 0; d--:
``````

should be

``for d = 9; d >= 0; d--:``
3 Likes

Correction#2:

``````else if max_less != -1:
``````

should be

``else if prefix_less != -1:``

"Since we want to maximize the number, it is always optimal to make S contain the same number of digits as M. "

This is very, very wrong and a really bad starting point.

What if, for example, M=100 and S=25, like in the example used in the task itself? There is no way to make S have as many digits as M, without it being larger than M.

Here there can be leading zeroes in the answer to make S contain the same number of digits as M.
So S can be 089 and the 0 can be removed while printing.

can you please tell me where my code is failing, i used the same approach as described in the editorial

http://www.codechef.com/viewsolution/1741764

It would be nice if you could post the input set used to validate the solutions…

Yes, sameer47 is correct. Here I allowed leading zeros in the solution as the length of the resulting number is not greater than |M|, so it is safe. But thanks I will update the statement.

Fixed. Thanks.

Fixed. Thanks.

You print nothing for this test: 0 6

Some of the tricky test cases:

```9
274 4883530
5 268343
2 558870
10381 16146
0 6
0 9
2 200543
4987565 14398964
1042216 1815366
```

```4883499
268343
558870
10989
0
8
200543
9989989
1098898
```

Will be updated regularly Refer to this:

http://ideone.com/qgYrei

you can check the link. My program prints 0 for this test case.
and it is giving correct answers for all the test cases posted below

Let’s add another constraint to make it harder: the chef can perform the defacing operation at most K times.

Yes, your bug is quite tricky. It is a big luck that our test data was managed to cover it. Try this test:
2
10381 16146
0 6
I know the reason but I guess you will have a lot of fun by figuring it out the bug by yourself.

Just to make sure that this time I am correct I ideoned your code against this test and it indeed prints nothing for 0 6 now.

where K and M should be prime to each other. I just want to kick myself.
had the fastest solution but could not find the mistake after spending 2 hours on it during the contest

They say this is an easy problem. It took me 2 days to understand Anton’s code snippet

``````// some kind of dp
max_smaller_digit[d1] = -1;
for (int d2 = 1; d2 < 10; ++d2) {
if (mark_digits[d1][d2-1]) {
max_smaller_digit[d1][d2] = d2-1;
} else {
max_smaller_digit[d1][d2] = max_smaller_digit[d1][d2-1];
}
}
``````

WTH! From where do you come up with these tricks, Anton? I finish the 2.5 hours time only thinking how to solve a problem…God knows when the hell am I gonna actually write more than one solutions in a Cook-Off or a Long Contest as well. God bless me!

Hm… I thought it should be clear.
`max_smaller_digit[d1][d2]` is either `d2-1` if we can obtain `d2-1` from `d1` or it is smaller than `d2-1`,
and in this case it is obviously coincide with `max_smaller_digit[d1][d2-1]`.
Of course, instead someone could write the trivial method:
for each pair `(d1, d2)` simply loop over digits starting from `d2-1`.
But why not code all optimally if it is possible //