×

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.

This question is marked "community wiki".

16345853
accept rate: 0%

For a line like this

value    707496
max    10257511

why the answer "10089998" is wrong? Your test give me "10099989", but the last "6" cannot become "9".

(11 Feb '13, 04:09) 0★

we add the empty slot after 707496:


707496
10257511

Then we can get 10099989.

(11 Feb '13, 04:31)

 3 Correction: for d = 9; d ≤ 0; d--:  should be for d = 9; d >= 0; d--:  answered 21 Jan '13, 02:27 8.7k●19●48●98 accept rate: 9% Fixed. Thanks. (21 Jan '13, 09:06)
 1 @syker, you have to perform all the IO from/to stdin/stdout. Just like the normal way you code. You can check few samples by going on anyone's profile page and then hitting any problem and then the corresponding solution. answered 26 Feb '13, 00:54 8.7k●19●48●98 accept rate: 9%
 0 Correction#2: else if max_less != -1:  should be else if prefix_less != -1:  answered 21 Jan '13, 02:31 8.7k●19●48●98 accept rate: 9% Fixed. Thanks. (21 Jan '13, 09:06)
 0 "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. answered 21 Jan '13, 04:45 105●1●4 accept rate: 0% 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. (21 Jan '13, 08:22) sameer474★ 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. (21 Jan '13, 09:04)
 0 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 answered 21 Jan '13, 08:28 4★sameer47 61●5 accept rate: 0% You print nothing for this test: 0 6 (21 Jan '13, 13:34) 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 (21 Jan '13, 15:17) sameer474★ 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. (21 Jan '13, 22:50) 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 (22 Jan '13, 10:10) sameer474★
 0 It would be nice if you could post the input set used to validate the solutions... answered 21 Jan '13, 08:55 1●1 accept rate: 0% Refer to this: http://discuss.codechef.com/answer_link/5641/ (21 Jan '13, 13:59)
 0 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  with the corresponding answers 4883499 268343 558870 10989 0 8 200543 9989989 1098898  Will be updated regularly ;) answered 21 Jan '13, 13:58 6.7k●62●119●138 accept rate: 12%
 0 Let's add another constraint to make it harder: the chef can perform the defacing operation at most K times. Share your solution. answered 21 Jan '13, 21:39 1●1●1 accept rate: 0% where K and M should be prime to each other. :P (22 Jan '13, 07:58)
 0 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][0] = -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! answered 23 Jan '13, 00:52 8.7k●19●48●98 accept rate: 9% 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 :) (23 Jan '13, 01:09) @anton_lunyov >> I got what you have written, but I took too much time to understand :( Thats why I was in the phase of sadness as to when will I be able to write such a code :D (23 Jan '13, 02:42)
 0 Can anybody tell me why my code is resulting in Wrong Answer ? I have used the same approach as described in the editorial. answered 23 Jan '13, 15:01 3★iceman91 1 accept rate: 0% Try this test: 4987565 14398964 Your answer is 9989889, while the correct one is 9989989. (23 Jan '13, 15:05)
 0 My code is resulting in wrong answer ..... http://www.codechef.com/viewsolution/1775055 I have tried every test case given in posts and problem.... working correctly... what is that I am missing ? answered 02 Feb '13, 13:30 4★saj1919 91●5●5●11 accept rate: 0% Your program fails at the very first test from here. Did you write this just for fun: "I have tried every test case given in posts and problem...." ? (02 Feb '13, 16:50) words are encouraging !!!! Still I stand to my words... "it satisfies the cases that you gave...." (not fun this time !!!) run it with gcc compiler... and see (02 Feb '13, 20:01) saj19194★ is there a problem with "memset()" ... because locally it is working fine !!! (02 Feb '13, 20:04) saj19194★ Haha. Very funny. You've fixed the bug and changed the submission ID to that passing posted test cases. Now the failing test is 1042216 1815366 The answer is 1098898 while your answer is 1798898, which is completely impossible since we can't make 7 from 0. I've also added it to the above post with tricky test cases. (02 Feb '13, 20:47)
 0 what is with initial values of prefix_equal and prefix_less?? answered 03 Feb '13, 14:20 0●1 accept rate: 0%
 0 http://ideone.com/VRvkWc this is my code for the problem.It is returning correct solution for every test case(mentioned). Someone please tell me what is wrong with this because every time I submit it shows wrong answer The only correct solution posted by me is copied. answered 03 Feb '13, 23:46 0●1 accept rate: 0% 1 7347946 12524098 --> 10999998 (04 Feb '13, 03:09) I think this is correct. If wrong what is correct solution?? (04 Feb '13, 12:15) 1 You last submission return different answer. You should indicate the submission ID at codechef instead of pasting the code to outside resources. (04 Feb '13, 13:02) http://www.codechef.com/viewsolution/1790134 This code is producing right result on my machine(for the above mentioned case as well). Sorry to sound cynical but it is truth (04 Feb '13, 22:48) 1 19 hours the last submission was 1784916 and it produces wrong answer. The test for the new version is 2926618 18735670. The answer is 12988898. (04 Feb '13, 23:06)
 0 I have written my code for this problem. Can you please tell me whats the format of the program. I mean it is not specified how the input will be taken and how the output should. My code read the file which is in the folder of compiler and gives output in a file. But tester going to know this. He have to change the name of the file according to his testing computer. So please help me out. How the submission is done. Thanks in advance. answered 26 Feb '13, 00:43 2★syker 1●2●2●4 accept rate: 0%
 0 @anton_lunyov Excellent problem..my first attempt at codechef and I am enjoying every bit of it. :) This is the latest version of solution I have developed: http://www.codechef.com/viewsolution/1864293 It gives a correct output for all the 12 test cases given in problem, 9 tricky cases added by you plus two more given in other comments. I know, it doesnt mean it is a correct solution but I am unable to understand why I am still getting wrong answer. I have used my own logic, havent looked at your solution yet, I want to figure out the entire solution on my own. Can you can provide some more test cases, which will help me in figuring out the bug on my own. I tried to create test cases on my own, by using random number generator and all, but got correct answers for all of them. So, if you have some more test cases, it will be great P.S. : I dont expect you to go through my code as it can be tricky to understand the logic :P answered 26 Feb '13, 16:47 1●1 accept rate: 0% 1 Your WA is actually RE. It seems that for this test 2454 211622 the following happens Error:-1 Error:java.lang.ArrayIndexOutOfBoundsException: -1 Error:java.lang.Exception: java.lang.ArrayIndexOutOfBoundsException: -1  (26 Feb '13, 21:43) Ohhh You are right, thanks for the input, I'll work on the bug (27 Feb '13, 18:09)
 0 @syker >> Try these tests: 8 13 8 24 Correct Answer: 8 and 18 respectively Your answer: 89 and 89 UPD. Your code gives correct answer for the above tests when they are performed initially, but gives 89 when they are written after some tests like 10 100. That might be because of faulty/misplaced initialization of some check arrays. answered 28 Feb '13, 12:46 8.7k●19●48●98 accept rate: 9%
 0 @anton_lunyov I am now struggling with TLE issue for this problem. What I find odd is: time limit is the same irrespective of platform. Isn't some languages faster as compared to others? And I haven't seen a single successful submission for JAVA for this problem. I know, it could be a mere coincidence but it still makes me wonder. I have tried many optimization techniques but none of them are giving any improvements. On my system I see lot of improvements with every major optimization(I have simulated huge inputs, as per given constraints, using random number generators)but when I submit here, I don't see any improvement at all in time, every time i just get 4.04 seconds, not even slightest improvement. Moreover, some optimization techniques which definitely should have worked have actually deteriorated the performance, e.g. if you compare the submissions: http://www.codechef.com/viewsolution/1877893 and http://www.codechef.com/viewsolution/1883458 the only change is in the function convertToNumber(), where instead of using String object, to append digits one by one, I used StringBuilder and append() function, which according to me should give better performance, but instead the time deteriorated to 10 seconds from 4 seconds. Any pointers in this regard? answered 03 Mar '13, 12:53 1●1 accept rate: 0% 3.7k●11●32●49 Actually there were several AC in Java even during live contest: http://www.codechef.com/submissions?language=10&status=15&pcode=DEFACING But AFAIK EgorK invent an O(lg(M)) solution in order to solve the problem while having TLE with O(lg(M) * lg(S)) solution. So probably for Java TL is a bit strict, though it is twice as usual TL. (03 Mar '13, 23:18)
 0 Why is the answer for 25, 100 is 89 but not 98 ? 025 ---> 089 ---> 89 250 ---> 098 ---> 98 Somebody please clarify, I'm struggling..... answered 05 Nov '13, 00:26 1●1 accept rate: 0%
 0 I posted my code on Ideone: http://ideone.com/tJKTyy I am getting a WA. I think it is passing the test cases given in the question and the comments here (as well as some ones I made myself), but I might simply be misreading. Can someone help me find my problem? Or at least a test case where my program is returning the wrong answer? answered 04 Mar '14, 00:24 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×1,024
×8
×1

question asked: 21 Jan '13, 00:29

question was seen: 26,346 times

last updated: 04 Mar '14, 00:24