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*. It will always be in our interest to make S* = 9. The reason is, if S* were modified to anything else, and if that digit was used in our final number, then it would be <= number formed by making S* = 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

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

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.

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* denote the maximum length of contiguous digits that end with with c*.

And let s* denote the maximum length of contiguous characters, containing at most 1 uppercase letter, that end with c*.

The trick is to update these values at each index i and store the index of i that leads to s* 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 is a digit*

We increment d* 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* 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* = d[i-1] + 1

else{

if (c* is not equal to ‘0’)

d* = 1

}

The exact same analogy applies to s*.

Case 2: c is not a digit. We assert that c is an uppercase letter.**

Here, since c* is an uppercase character, d* must be zero.
Also, at this point, we append c* to the existing maximum length of digits at index (i-1) i.e. d[i-1]. Hence s* = 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

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

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

@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 : http://ideone.com/S6AwdE

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