BigInteger to the rescue!!!Forgot the case where no can be as large as 999 digits!!!
I’ve got a very simple O(n) solution to this problem. See CodeChef: Practical coding for everyone
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.
4 Likes
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
I used DP to solve it in O(n). Missed handling leading zeros, I guess using python would have saved me!
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
@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.
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…
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…
getting WA… plzz help !! all of the inputs given in editorial givin correct answers…
ideone link : S6AwdE - Online C++ Compiler & Debugging Tool - Ideone.com
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…
5 Likes
Changed my code. Now getting NZEC. Not understanding why. Please help.
http://www.codechef.com/viewsolution/2312588
feeling really bad after ignoring that the age of universe can be zero! :’(.
3 Likes
OMG!!! Leading Zeros :-(…Nxt tym will be carefull…
had taken care of that still…
burrrh… I tested all the corner cases I could guess… hard luck bro…
1 Like
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…!!!
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.
i m not getting ne case for which my code fails…still getting WA…