×

Easy

# Problem:

You are given a string of digits 0-9, and uppercase letters 'A'-'Z'. Given that you are allowed to modify atmost one letter to any digit, what is the largest number you can get as a contiguous substring of the modified string.

# Quick Explanation:

Given the string S, lets say we choose to modify the letter S[i]. It will always be in our interest to make S[i] = 9. The reason is, if S[i] were modified to anything else, and if that digit was used in our final number, then it would be <= number formed by making S[i] = 9.

So take each letter, modify it to the number '9', and check if you get a larger number than your currently formed best. This approach takes O(|S|^2) time and if implemented correctly, is good enough to pass.

At the same time, one catch was that since the number of digits can be pretty large, actually storing the number as an int / long long would not work. You would have to compare numbers as strings. Here, care should be taken that merely comparing lengths and then for the same length doing lexicographic comparison would fail for cases of comparison with a longer string have leading zeros.

High level pseudocode for the entire program: string ans = findBest(S) for each character c in S if(c is a letter) change c to 9 string cons = findBest(S) if(compare(cons, and) gives cons larger) ans = cons output ans

("detailed") Pseudocode for the compare function:

rawcomplt(string A, string B):
if(A.length() < B.length())
return true;
else if(A.length() > B.length())
return false;
else return A < B;

compare(string A, string B)
int startA, startB
for(startA = 0; startA < A.length(); startA++)
if(A[startA] != '0')
break;
for(startB = 0; startB < B.length(); startB++)
if(B[startB] != '0')
break;
return rawcomplt(A.subtr(startA, A.length()), B.substr(startB, B.length()));


# Setter's Solution:

Can be found here

# Tester's Solution:

Can be found here

1067915
accept rate: 0%

19.8k350498541

3

feeling really bad after ignoring that the age of universe can be zero! :'(.

(24 Jun '13, 00:13) 3★

OMG!!! Leading Zeros :-(....Nxt tym will be carefull...

(24 Jun '13, 00:17)

i think my approach was simpler than many described here ; I did'nt realise the case of leading zeros until i read this editorial ... my approach was to convert contiguous numbers and look for max and in case of letters look nearby for contiguous numbers and compare the newly formed number (with the letter as number 9) with standing maximum. Python takes good care of large numbers/inputs ...so yay to python!

(27 Jun '13, 13:24)

 5 http://www.codechef.com/viewsolution/2300014 Getting wrong answer.. Even checked all the cases described above. Took care of leading zeroes. Used BigInteger to achieve the length of answer. Still can not figure it out why am i getting WA. :( CAn any1 provide me some test cases... answered 28 Jun '13, 12:25 3★laxman94 1.2k●3●15●15 accept rate: 6%
 4 I've got a very simple O(n) solution to this problem. See http://www.codechef.com/viewsolution/2292946 Approach: Let c[] be the input character array. Let d[i] denote the maximum length of contiguous digits that end with with c[i]. And let s[i] denote the maximum length of contiguous characters, containing at most 1 uppercase letter, that end with c[i]. The trick is to update these values at each index i and store the index of i that leads to s[i] having a maximum value. Now, how do we go about filling s[] and d[]? Clearly, there are two cases to be considered. Case 1: c[i] is a digit We increment d[i] only if there's an existing sequence of digits. This allows us to avoid leading zeroes. On the other hand, if there's no existing sequence of digits and c[i] is a non-zero digit, then we have a running sequence of digits whose length is 1. At this point, the code looks like this: if (d[i-1] is not equal to zero) d[i] = d[i-1] + 1  else{ if (c[i] is not equal to '0') d[i] = 1  } The exact same analogy applies to s[i]. Case 2: c[i] is not a digit. We assert that c[i] is an uppercase letter. Here, since c[i] is an uppercase character, d[i] must be zero. Also, at this point, we append c[i] to the existing maximum length of digits at index (i-1) i.e. d[i-1]. Hence s[i] = d[i-1] + 1. The rest is cakewalk from here and I do hope the logic is clear up to this point. You should be able to read and understand the code now :) Regards, Essiennta. answered 24 Jun '13, 05:13 5★bodmas 161●2●7 accept rate: 0% will you please explain your approach in short.. thanks in advance. (24 Jun '13, 11:10) @bodmas... C23DB34 will your code works for this test case. (26 Jun '13, 07:48) wow, you got me on that! The code doesn't handle that scenario, though it managed to get an AC :) (27 Jun '13, 12:25) bodmas5★ I think this solution is much better than editorial, and this is he way we should do it..nice bodmas.. (30 Jun '13, 00:41) I have modified your code to handle cases like C23DB34. http://www.codechef.com/viewsolution/2312243 (04 Jul '13, 16:25)
 2 A couple of boundary cases where people failed: (1) Bad comparison without allowing for leading zeroes (described in Editorial). (2) Taking care of leading 0, but when the final answer actually is "0", outputting "". (3) Searching for a letter to change, but the string consisting only of digits. If your code is getting WA, check with these cases first. answered 24 Jun '13, 00:17 0★prad_adm 106●7●9●15 accept rate: 0% had taken care of that still..:( (24 Jun '13, 00:21) kunal3614★
 0 Please provide a case for which this code fails i tried a lot of cases but failed to find 1....LINK...thanks in advance..:) answered 24 Jun '13, 00:12 4★kunal361 6.0k●13●32●72 accept rate: 21% 1 burrrh.... I tested all the corner cases I could guess.... hard luck bro...... (24 Jun '13, 00:34) i saw them..all were giving correct ans...thanks for trying :) @prad_adm...pls give cases that my code is failing to give correct ans...!!! (24 Jun '13, 00:39) kunal3614★ thanks kunal361 .. i didn't tried for no input ant inputs having all 0's.. got it correct... sad that i wasn't able to figure this out while contest was running. (24 Jun '13, 10:32) himank774★ i m not getting ne case for which my code fails...still getting WA...:( (24 Jun '13, 10:39) kunal3614★ 3 Try this : 0A000B99 (24 Jun '13, 12:31) thanks a lot...!!! (24 Jun '13, 12:36) kunal3614★ @malaykeshav finally got AC..thanks a ton dude!!! (24 Jun '13, 12:42) kunal3614★ @malaykeshav does your input gives output 9000..??? (25 Jun '13, 12:14) d27v2★ yes...9000 is correct!!! (25 Jun '13, 12:25) kunal3614★ then why am i getting WA...??..:(....plz check my solution..http://www.codechef.com/viewsolution/2295232 (25 Jun '13, 14:24) d27v2★ showing 5 of 10 show all
 0 spot on! my test case failed for case 2. O(n) algo is also easy. Finally got accepted in practise :P with the hint. answered 24 Jun '13, 00:25 99●3●5●9 accept rate: 0%
 0 BigInteger to the rescue!!!Forgot the case where no can be as large as 999 digits!!! answered 24 Jun '13, 02:07 425●3●7●17 accept rate: 4%
 0 Please provide a case for which this code fails i tried a lot of cases but failed to find 1.......thanks in advance..:) My code http://ideone.com/OowTkQ answered 24 Jun '13, 10:28 1★xnon 1 accept rate: 0% @xnon Your code doesn't produce any output for all zeroes. Try 00000 or 0000000000 (any string of 0's), there is no output. (24 Jun '13, 21:15) viaan2★ @viaan i m also getting wrong answer...even my solution gives 0 for a string consist of all zero's plz check my solution http://www.codechef.com/viewsolution/2295232 (25 Jun '13, 12:10) d27v2★
 0 http://www.codechef.com/viewsolution/2291512 why do I get WA? please help answered 24 Jun '13, 11:52 251●3●10 accept rate: 0% Your atoi() cannot handle digits with a length of 1000. Find some other mechanism for comparison. (24 Jun '13, 12:31) dush223★ string can do it? (24 Jun '13, 12:38) 1 In C/C++ I guess thats the only way to do it. Java provides you with BigInteger. And python is the king in such cases.... (24 Jun '13, 12:41) dush223★
 0 I used DP to solve it in O(n). Missed handling leading zeros, I guess using python would have saved me! answered 24 Jun '13, 11:55 2★iceman_w 1●2●2●4 accept rate: 0%
 0 L51B5556786881505146D55221CY4X52740A22676OH8K817G02L56W7Q6I406LP3564J1A307465242A118656V048538X3K36278573N2M6WW1P2VU70285448647376565608N2N07W7RBN8E27O66454X53W1X8R12223048UKC4UU22YTR3586G18Z524647236Y6U16131853BP6ZC8LD4808578P832H757H342267PHUN6S65830368561205I6Y00Z6PV2E5CU0X50G7E61688J80TR0052E1P7P57T66IR57J080841382U37JY0L365206257V430WZ6OY8Y8UC2081V73E724053ZK2660111CD2005R5S0 For The Above Input String, I checked the answers from two of the submissions and they gave 5556786881505146955221 But My Solution gave 7028544864737656560892 What should be the correct solution?? My Solution http://www.codechef.com/viewsolution/2293812 Somebody Help me with the test cases answered 24 Jun '13, 12:02 3★dush22 61●4 accept rate: 0% Sorry for the long String...:P (24 Jun '13, 12:06) dush223★ what matters is whether it was in the test case! (24 Jun '13, 12:18) No but my question is that an algorithm has to be generic and valid for all kinds of test cases.What the test cases are is an altogether different thing. (24 Jun '13, 12:22) dush223★ i m getting 7028544864737656560892..and apparently it is correct...but still m not getting AC..:( (24 Jun '13, 12:22) kunal3614★ both have the same digits and so logically yours is right @dush22 (24 Jun '13, 12:25) 7028544864737656560892 i'm also getting it's correct but getting TLE in python code :( (24 Jun '13, 12:56) i'm also getting 7028544864737656560892 but it shows wa (24 Jun '13, 14:50) 1 try 0 or 000 there is no output!!! see this link http://ideone.com/acvoy8 (24 Jun '13, 16:08) kunal3614★ Ohhh..I added the wrong link. I've changed that. And corrected for the above cases as well..Still not working. And Now the code is less generic and more of test case driven...:-/ (24 Jun '13, 16:28) dush223★ I have the same output for the string. Make sure your output is zero when there is no input- that thing got me stuck the whole time! (25 Jun '13, 15:19) What exactly do you mean by no input?? The Problem says 1<=|S|<=1000 (25 Jun '13, 15:50) dush223★ showing 5 of 11 show all
 0 plz tell me why am i getting NZEC error in this code..http://www.codechef.com/viewsolution/2292156 answered 24 Jun '13, 17:40 2★d27v 1●1 accept rate: 0% the ans can have upto 1000 digits...you can not store it using an int and also the NZEC is due to number format exception!!! (24 Jun '13, 18:36) kunal3614★ @kunal361 thanx .... but when i used biginteger then i got wrong answer...:( (24 Jun '13, 18:40) d27v2★ @d27v then you must be missing some corner cases. Have you checked the points @prad_adm has posted above. (24 Jun '13, 20:58) viaan2★ yeah i have checked all those cases...but still getting WA..http://www.codechef.com/viewsolution/2295232 (25 Jun '13, 14:41) d27v2★
 0 @prad_adm : Here is link to my submission, which got AC : http://www.codechef.com/viewplaintext/2290226 I had used long double to store the maximum. Was it due to the test cases or long double is sufficient to store values upto 10^1000. Was really surprised at AC. Initially I started with long long int, but got WA. Then I switched to long double. Just curious to know. answered 24 Jun '13, 21:04 2★viaan 736●2●9●18 accept rate: 0% long double can store huge numbers....but sometimes the precision may be lost!!! (24 Jun '13, 21:16) kunal3614★ @kunal361 So long double is capable enough to store numbers of range 10^1000. This is "woww". So in cases where precision is not of that importance we can use long doubles. Right ?? (24 Jun '13, 21:19) viaan2★ see this...http://ideone.com/SIZSbF also for a functional code using double for a problem in the long contest u can have a look at this code...http://www.codechef.com/viewsolution/2129134 ...this is 1 of my friends code he used 2D matrix of double to store the pascals triangle...!!! (24 Jun '13, 21:28) kunal3614★ interestingly it stored all values with adequate precision...!!! (24 Jun '13, 21:31) kunal3614★ @kunal361 is that link http://ideone.com/SIZSbF broken, nothing is displayed. Maybe it's due to user's privacy control. (24 Jun '13, 21:35) viaan2★ oops sorry...changed it!!! (24 Jun '13, 21:41) kunal3614★ showing 5 of 6 show all
 0 Getting WA ... have checked for all the corner cases and getting correct result. Help me in figuring out what is it that I am doing wrong... need help with the test cases... http://ideone.com/wSVEHg answered 25 Jun '13, 10:51 2★d1p0 1●1 accept rate: 0% you dont print nething when ans in "0"...pls check that case...!!! (25 Jun '13, 11:35) kunal3614★ thanks.. I did change the code to print "0" ... Strange thing i noticed for my program it is giving no output if i have to print single zero. : http://ideone.com/R0mFoG Also for this simple code to no out put: http://ideone.com/zTR0YP Please help (25 Jun '13, 12:50) d1p02★ print a "\n" after 0...i think it will solve the issue!!! (25 Jun '13, 12:59) kunal3614★ thanks ... it solved the issue... but still getting WA !! (25 Jun '13, 15:32) d1p02★
 0 Plz tell me why am i getting NZEC error in this code.. http://www.codechef.com/viewsolution/2296875 I am using String rather than integer and i have checked all the points @prad_adm has posted above... answered 26 Jun '13, 10:09 1●1●1●1 accept rate: 0%
 0 getting WA.. plzz help !! all of the inputs given in editorial givin correct answers.. ideone link : http://ideone.com/S6AwdE answered 26 Jun '13, 12:50 16●1●1●3 accept rate: 0% @sid_iiita - yu are using long long.. yu shuld change your algo.. to keep it in string.. otherwise your ans will overflow.. check this input.. DDDDDDDDDDD66666666666666666666666666666UYIWUYRR yu are getting WA (27 Jun '13, 00:45) @kashish55 thanxx for help :D silly of me (27 Jun '13, 12:41)
 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
×968
×7
×5

question asked: 24 Jun '13, 00:11

question was seen: 17,488 times

last updated: 04 Jul '13, 20:37