You are not logged in. Please login at www.codechef.com to post your questions!

×

ALETHIO - Editorial

5
4

Problem Link:

Practice
Contest

Difficulty:

Easy

Pre-requisites:

ad-hoc

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

asked 24 Jun '13, 00:11

prad_adm's gravatar image

0★prad_adm
1067915
accept rate: 0%

edited 24 Jun '13, 00:26

admin's gravatar image

0★admin ♦♦
19.7k350498541

3

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

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

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

(24 Jun '13, 00:17) xpertcoder4★

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) prakashydv2★

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

link

answered 28 Jun '13, 12:25

laxman94's gravatar image

3★laxman94
1.2k31515
accept rate: 6%

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.

link

answered 24 Jun '13, 05:13

bodmas's gravatar image

5★bodmas
16127
accept rate: 0%

edited 24 Jun '13, 20:46

will you please explain your approach in short.. thanks in advance.

(24 Jun '13, 11:10) aravind1592★

@bodmas... C23DB34 will your code works for this test case.

(26 Jun '13, 07:48) aravind1592★

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) madhur134902★

I have modified your code to handle cases like C23DB34. http://www.codechef.com/viewsolution/2312243

(04 Jul '13, 16:25) prakhs1234★

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.

link

answered 24 Jun '13, 00:17

prad_adm's gravatar image

0★prad_adm
1067915
accept rate: 0%

had taken care of that still..:(

(24 Jun '13, 00:21) kunal3614★

Please provide a case for which this code fails i tried a lot of cases but failed to find 1....LINK...thanks in advance..:)

link

answered 24 Jun '13, 00:12

kunal361's gravatar image

4★kunal361
6.0k133272
accept rate: 21%

edited 24 Jun '13, 00:13

1

burrrh.... I tested all the corner cases I could guess.... hard luck bro......

(24 Jun '13, 00:34) devanshug4★

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) malaykeshav4★

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

spot on! my test case failed for case 2. O(n) algo is also easy. Finally got accepted in practise :P with the hint.

link

answered 24 Jun '13, 00:25

arnabbcs08's gravatar image

4★arnabbcs08
99359
accept rate: 0%

BigInteger to the rescue!!!Forgot the case where no can be as large as 999 digits!!!

link

answered 24 Jun '13, 02:07

jaythegenius's gravatar image

3★jaythegenius
4253717
accept rate: 4%

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

link

answered 24 Jun '13, 10:28

xnon's gravatar image

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★

http://www.codechef.com/viewsolution/2291512 why do I get WA? please help

link

answered 24 Jun '13, 11:52

himanshujaju's gravatar image

6★himanshujaju
251310
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) himanshujaju6★
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★

I used DP to solve it in O(n). Missed handling leading zeros, I guess using python would have saved me!

link

answered 24 Jun '13, 11:55

iceman_w's gravatar image

2★iceman_w
1224
accept rate: 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

link

answered 24 Jun '13, 12:02

dush22's gravatar image

3★dush22
614
accept rate: 0%

edited 24 Jun '13, 16:29

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) himanshujaju6★

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) himanshujaju6★

7028544864737656560892 i'm also getting it's correct but getting TLE in python code :(

(24 Jun '13, 12:56) piyushchauhan2★

i'm also getting 7028544864737656560892 but it shows wa

(24 Jun '13, 14:50) satya80812★
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) prabhpreet2★

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

plz tell me why am i getting NZEC error in this code..http://www.codechef.com/viewsolution/2292156

link

answered 24 Jun '13, 17:40

d27v's gravatar image

2★d27v
11
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★

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

link

answered 24 Jun '13, 21:04

viaan's gravatar image

2★viaan
7362918
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

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

link

answered 25 Jun '13, 10:51

d1p0's gravatar image

2★d1p0
11
accept rate: 0%

edited 25 Jun '13, 10:55

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★

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

link

answered 26 Jun '13, 10:09

architsmat38's gravatar image

3★architsmat38
1111
accept rate: 0%

getting WA.. plzz help !! all of the inputs given in editorial givin correct answers..

ideone link : http://ideone.com/S6AwdE

link

answered 26 Jun '13, 12:50

sid_iiita's gravatar image

2★sid_iiita
16113
accept rate: 0%

edited 26 Jun '13, 12:51

@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) kashish554★

@kashish55 thanxx for help :D silly of me

(27 Jun '13, 12:41) sid_iiita2★

Changed my code. Now getting NZEC. Not understanding why. Please help. http://www.codechef.com/viewsolution/2312588

link

answered 04 Jul '13, 15:41

guptakeshav's gravatar image

5★guptakeshav
1222
accept rate: 0%

edited 04 Jul '13, 20:37

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,477
×3,704
×921
×7
×5

question asked: 24 Jun '13, 00:11

question was seen: 17,443 times

last updated: 04 Jul '13, 20:37