ALETHIO - Editorial

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

5 Likes

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

1 Like

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

3 Likes

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.

2 Likes

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

had taken care of that still…:frowning:

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

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 :slight_smile:

@prad_adm…pls give cases that my code is failing to give correct ans…!!!

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 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 :slight_smile:

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…:slight_smile:

My code http://ideone.com/OowTkQ

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…:frowning:

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

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

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

Sorry for the long String…:stuck_out_tongue:

what matters is whether it was in the test case!

//