REMMAX - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Abdullah Aslam

Tester: Michael Nematollahi

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy.

PREREQUISITES:

Case-based Implementation.

PROBLEM:

Given a number N of at most 10000 digits, find 1 \leq X \leq N such that Reverse(X) is maximum possible for all 1 \leq X \leq N where Reverse(X) denotes the decimal number obtained by reversing the decimal representation of X (without leading zeroes).

EXPLANATION

Since after reversal, the least significant digits become most significant digits, to maximize reverse, our aim would be to maximize the lower digits first.

If d_0 denote the first digit of N, then one good candidate maximizing reverse is a number of form with the first digit being (d_0-1) and all subsequent digits being 9. We can see that the resulting number is smaller than or equal to N and its reverse has first (N-1) digits as 9, making it the maximum reverse value too.

See example, consider N = 3721, the optimal X shall be 2999 since its reverse is 9992, having first (N-1) digits maximum possible. It can be seen that There is no other value X \leq N which generates reverse greater than this value. Similarly, for N = 2998, the optimal answer is 1999.

But what if N = 2999, we need to take care not to turn it into 1999, since 1999 would generate reverse 9991 while 2999 will generate reverse 9992 which is better. The idea is, if the original number already contains 9 at all excluding the first digit, the original number is the answer too.

But, the author isn’t really satisfied with giving such an easy problem. He still proposed this problem, because he knew there is an edge case.

What if the first digit is 1. For example, consider N = 1911 our above idea would give answer X = 999 while there is X = 1899 which results in reverse being 9981, much better than 999. This happened because reducing the first digit to zero ending up removed) which reduces the number of the digit in reverse generated. So, our initial strategy is definitely not valid in this case.

The idea is, to skip the first digit then since we cannot afford to reduce it and find the first non-zero digit we can. Now, Even if this digit may be 1, we can reduce it, since it doesn’t reduce the number of digits in reverse generated. Consider N = 10128, the optimal X is 10099.

But, what if N = 10199. We are back in a similar situation where N itself generated the maximum reverse value. The optimal X in these case too is 10199, not 10099. Consider example N = 10007, it is best to keep X = 10007.

Now, after handling all these cases, it’s time for setter’s masterstroke test case where N = 1000000. The optimal answer for this case is X = 999999.

This finally puts an end to edge cases and edge cases of edge cases and you have finally solved the problem.

TIME COMPLEXITY

Time complexity is O(|N|) per test case where |N| denote the number of digits in the decimal notation of N.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define N 300101
#define SZ 3001
#define LB lower_bound
#define M 1000000007
#define UB upper_bound
#define MP make_pair
#define LD long double
#define F first
#define S second
 
int main()
{
	LL k,i,j,lt,tc,d,r,q,y,z,v,x,m,n;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>lt;
	while(lt--)
	{
	    string s;
	    cin>>s;
	    n=s.length();
	    assert(n>=1&&n<=1e4);
	    if(n==1)
	    {
	        cout<<s<<endl;
	        continue;
	    }
	    if(s[0]!='1')
	    {
	        k=0;
	        for(i=1;i<n;i++)
	        {
	            if(s[i]!='9')
	                k++;
	            s[i]='9';
	        }
	        if(k)
	            s[0]--;
	        cout<<s<<endl;
	    }
	    else
	    {
	        for(i=1;i<n;i++)
	            if(s[i]!='0')
	                break;
	        if(i==n)
	        {
	            for(i=1;i<n;i++)
	                cout<<9;
	            cout<<endl;
	        }
	        else
	        {
	            if(i!=n-1)
	            {
	                k=0;
	                for(j=i+1;j<n;j++)
	                {
	                    if(s[j]!='9')
	                        k++;
	                    s[j]='9';
	                }
	                if(k)
	                    s[i]--;
	            }
	            cout<<s<<endl;
	        }
	    }
	}
} 
Tester's Solution
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second

int n;
string s;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int te;	cin >> te;
	while (te--){
		cin >> s; 
		n = s.size();

		if (s.back() == '0'){
			s.back() = '9';
			for (int i = n-2; ~i; i--)
				if (s[i] != '0'){
					s[i]--;
					break;
				}
				else
					s[i] = '9';
			if (s[0] == '0')
				s.erase(s.begin()), n--;
		}

		for (int i = 0; i < n; i++)
			if (i == 0 && s[i] > '1' || i > 0 && s[i] > '0') {
				bool fl = false;
				for (int j = i+1; j < n; j++)
					if (s[j] != '9'){
						s[j] = '9';
						fl = true;
					}
				if (fl)
					s[i]--;
				break;
			}
		cout << s << endl;
	}
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class REMMAX{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    String s = n();
	    int n = s.length();
	    StringBuilder ans = new StringBuilder("");
	    if(s.charAt(0)=='1'){
	        boolean carry = false;
	        ans.append('1');
	        for(int i = 1; i< n; i++){
	            if(s.charAt(i)=='0')ans.append('0');
	            else {
	                carry = true;
	                boolean f = true;
	                for(int j = i+1; j< n; j++)f &= s.charAt(j)=='9';
	                
	                if(f)ans.append(s.charAt(i));
	                else ans.append((char)(s.charAt(i)-1));
	                
	                for(int j = i+1; j< n; j++)ans.append('9');
	                break;
	            }
	        }
	        if(!carry){
	            ans = new StringBuilder("");
	            for(int i = 1; i< n; i++)ans.append('9');
	        }
	        if(s.length()==1)ans = new StringBuilder("1");
	    }else{
	        boolean f = true;
	        for(int i = 1; i< n; i++)f &= s.charAt(i) == '9';
	        ans.append((char)(s.charAt(0)-1+(f?1:0)));
	        for(int i = 1; i< n; i++)ans.append(9);
	    }
	    pn(ans.toString());
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new REMMAX().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to Share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

7 Likes

my this solution is giving correct to all test cases except TEST CASE 0:
can anyone figure it out?? https://ideone.com/VNhxqJ

#include<bits/stdc++.h>
using namespace std;
int main()
{
// #ifndef ONLINE_JUDGE
// freopen(β€œinput.txt”,β€œr”,stdin);
// #endif
int t,n,count1,i,j,flag;
char ch[10001];
cin>>t;
while(t–)
{
cin>>ch;
n=strlen(ch);
//ch[n]=’\0’;
int ar[n]={};
if(n==1 || (n==2 &&ch[0]==β€˜1’) ||(n==2 &&ch[1]==β€˜9’))
{
cout<<ch<<"\n";
continue;
}
if(n==2)
{
//if(ch[1]==’’)
ch[0]=ch[0]-1;
ch[1]=β€˜9’;
cout<<ch<<"\n";
continue;
}
if(ch[0]==β€˜1’)
{
i=1;
while(ch[i]==β€˜0’)
++i;
if(i==n)
{
for(i=1;i<n;i++)
cout<<β€œ9”;
cout<<"\n";
continue;
}
}
if(ch[0]!=β€˜1’ && ch[1]!=β€˜0’)
{
i=1;
while(ch[i]==β€˜9’)
++i;
//cout<<i<<"?";
if(i==n)
{
cout<<ch<<"\n";
continue;
}
–ch[0];
for(i=1;i<n;i++)
ch[i]=β€˜9’;
cout<<ch<<"\n";
continue;
}
if(ch[0]!=β€˜1’ && ch[1]==β€˜0’)
{
–ch[0];
cout<<ch[0];
for(i=1;i<n;i++)
cout<<β€œ9”;
cout<<"\n";
continue;
}
if(ch[0]==β€˜1’ && ch[1]!=β€˜0’)
{
//cout<<β€œ1”;
i=2;
while(ch[i]==β€˜9’)
{
++i;
}
//cout<<i<<"?";
if(i==n)
{
cout<<ch<<"\n";
continue;
}
cout<<ch[0];
–ch[1];
cout<<ch[1];
for(i=2;i<n;i++)
cout<<β€œ9”;
cout<<"\n";
continue;
}
if(ch[0]==β€˜1’ && ch[1]==β€˜0’)
{
for(i=2;ch[i]==β€˜0’;++i);
flag=0;
while(ch[i]==β€˜1’)
{
flag=1;
++i;
}
while(ch[i]==β€˜9’)
{
flag+=1;
++i;
}
if(i==n && flag>2)
{
cout<<ch<<"\n";
continue;
}
}
i=1;
cout<<β€œ1”;
while(ch[i]==β€˜0’)
{
++i;
cout<<β€œ0”;
}
flag=0;j=i;
while(ch[j]==β€˜9’)
{
flag=1;
++j;
//cout<<β€œ9”;
}
if(j>=n && flag==1)
{
for(flag=i;flag<n;flag++)
cout<<ch[flag];
cout<<"\n";
continue;
}
if(i<n-1)
{
–ch[i];
cout<<ch[i];
for(j=i+1;j<n;j++)
cout<<β€œ9”;
cout<<"\n";
continue;
}
cout<<ch[i]<<"\n";
continue;
}
return 0;
}

It fails when u give an input 10.
It should output 9 but your code outputs 10.
I hope this helps. There may be a few more cases but this was what I could find in the first run.

thanks for your response. Got AC!! :slight_smile:

I have checked for all the above testcases given in editorial. But my submission (https://www.codechef.com/viewsolution/24400065) shows AC only in the last task. Can anyone tell me which testcases break my code?

NP. Its we who help each other grow.

1 Like

Try 2090, ur code outputs 2089 which is totally wrong. The answer should be 1999. For a moment i too almost thought ur code was right. Next time try less if and else. I hope this helps. There might be more errors but thats what i found. :slight_smile:

1 Like

Thanks, also you’re right for using too many if-else. I realized that one if block could be captured in another one and also, the order in which conditions were checked was wrong. Thanks again, I got AC.

My solution is giving AC in each TEST CASE except 1 & 2 (with 0 indexing):slight_smile:
Can anyone figure out the mistake with my code, please reply

#include <iostream>
#include <vector>

typedef long long int lld;

using namespace std;

void fast(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0); std::cout.tie(0);
}

bool allNine (string str, int start, int n){
    for (int i = start; i < n; i++) if (str[i] != '9') return false;
    return true;
}

bool allZero (string str, int n){
    for (int i = 1; i < n; i++) if (str[i] != '0') return false;
    return true;
}

int main(){
    // fast();
    int T, n, i;
    cin >> T;

    string str, ans;

    while(T--){
        // Code here
        cin >> str;
        n = str.size();

        ans.clear();

        if (str[0] > '1'){
            if (allNine(str, 1, n)){
                ans = str;
            }
            else{
                for(i = 0; i < n; i++) ans += '9';
                ans[0] = str[0] - 1;
            }
        }
        else if (str[0] == '1' && allZero(str, n)){
            for (int i = 1; i < n; i++){
                ans += '9';
            }
        }
        else {
            for (int i = 1; i < n; i++){
                if (str[i] != '0'){
                    if (allNine(str, i + 1, n)){
                        ans = str;
                        break;
                    };

                    str[i]--;
                    for (i = i + 1; i < n; i++){
                        str[i] = '9';
                    }
                    ans = str;
                    break;
                }
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

Disappointing for me! Did a few last minute submissions! I was pretty sure i would get AC after debugging for 1 hour! I got the verdict after the contest ended. Got WA on last case only! Sad and disappointing for me -_- You got me , β€œ10019”!

Nice problem BTW

My bad, It was giving WA for input N = 1 :smile:

Here is my solution:

#include <bits/stdc++.h>
using namespace std;

#define mod 1e9+7
typedef long long ll;
typedef unsigned long long ull;

bool allSame(string s, char ch) {
   if (s[0] == ch)
      return (s.find_first_not_of(s[0]) == string::npos);
   else
      return false;
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int t;
   cin >> t;
   while (t--) {
      string val;
      cin >> val;
      string dup_val = val;
      string rem;
      if (val.length() == 1)
         cout << val << '\n';
      else {
         if (val[0] == '1') {
            while (1) {
               rem += val[0];
               if (rem == dup_val) {
                  break;
               }
               val = val.substr(1);
               if (val[0] - '0' >= 1) {
                  break;
               }
            }
         }
         if (rem == dup_val) {
            fill(dup_val.begin(), dup_val.begin() + dup_val.length() - 1, '9');
            dup_val.pop_back();
            cout << dup_val << '\n';
         }
         else {
            cout << rem;
            if (allSame(val, '9') || val.length() == 1 || allSame(val.substr(1), '9'))
               cout << val << '\n';
            else {
               cout << val[0] - '0' - 1;
               val = val.substr(1);
               fill(val.begin(), val.begin() + val.length(), '9');
               cout << val << '\n';
            }
         }
      }
   }
   return 0;
}

My solution is giving AC in all cases except last one.
Can anyone tell the problem

#include<bits/stdc++.h>
#define ll long long
using namespace std;

main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
string n;
cin>>n;
if(n.size()==1)
{
cout<<n<<endl;
continue;
}
if(n[0]==β€˜1’)
{
ll ind=0;
for(ll i=1;i<n.size();i++)
{
if(n[i]!=β€˜0’)
{
ind=i;
break;
}
}
if(ind==0)
{
for(ll i=1;i<n.size();i++)
cout<<9;
cout<<endl;
continue;
}
if(ind==n.size()-1)
{
cout<<n<<endl;
continue;
}
int flag=0;
for(ll i=ind+1;i<n.size();i++)
{
if(n[i]!=β€˜9’)
{
flag=1;
break;
}
}
if(flag==0)
{
cout<<n<<endl;
}
else
{
int x=n[ind];
x=x-1;
n[ind]=(char)x;
for(ll i=ind+1;i<n.size();i++)
{
n[i]=β€˜9’;
}
cout<<n<<endl;
}

}
else
{
	ll j;
	for(j=1;j<n.size();j++)
	{
		if(n[j]!='9')
		break;
	}
	if(j==n.size())
	{
		cout<<n<<endl;
		continue;
	}
	
	int q=n[0]-'0';
	q=q-1;
	cout<<q;
	for(ll i=1;i<n.size();i++)
	cout<<9;
	cout<<endl;
}
	

}

}

Can someone help me with my solution ? Got 70 points, don’t know how 30 missed out even though subtask 1 is a subset of subtask 2 ( i.e. N< 10^4 cases would also be covered in subtask 2 )

Can Someone help to find the test cases which r getting wrong in my solution? I got half test cases AC. (http://Solution)
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second

using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--)
	{
	    string s;
	    cin >> s;
	    int n = s.length();
	    if(n==1)
	    {
	        cout << s << endl;
	        continue;
	    }
	    bool oneZero = true;
	    for(int i=0;i<n;i++)
	    {
	        if(s[i]!='0' && s[i]!='1')
	        {
	            oneZero = false;
	            break;
	        }
	    }
	    if(oneZero)
	    {
	    	//cout << "in oneZero" << endl;
	        if(s[n-1]=='1')
	        {
	        	//cout << "hi     "; 
	            cout << s << endl;
	            continue;
	        }
	        else
	        {
	            for(int i=n-1;i>=0;i--)
	            {
	                if(s[i]=='1')
	                {
	                    s[i]='0';
	                    break;
	                }
	                else
	                {
	                    s[i]='9';
	                }
	            }
	            int k = 0;
	            while(1)
	            {
	                if(s[k]!='0')
	                {
	                    break;
	                }
	                k++;
	            }
	            string temp = s.substr(k);
	            cout << temp << endl;
	            continue;
	        }
	    }
        else
        {
            int k = 0;
            while(1)
            {
                if(s[k]!='1' && s[k]!='0')
                {
                    break;
                }
                k++;
            }
            if(k==n-1)
            {
            	//cout << "hi  " ;
                cout << s << endl;
                continue;
            }
            else
            {
            	bool nine = true;
            	for(int i=k+1;i<n;i++)
            	{
            		if(s[i]!='9')
            		{
            			nine = false;
            			break;
            		}
            	}
            	if(nine)
            	{
            		cout << s << endl;
            		continue;
            	}
                int f = s[k]-'0';
                f--;
                s[k] = f+'0';
                for(int i=k+1;i<n;i++)
                {
                    s[i] = '9';
                }
                cout << s << endl;
                continue;
            }
        }
	}
	return 0;
}

this problem has more plot twists than game of thrones :tired_face:

5 Likes

I have checked for all the above testcases given in editorial. But my submission (https://www.codechef.com/viewsolution/24448181) shows AC only in the last task.
I have also tried with 2090 & the answer is correct…
Can anyone tell me which testcases break my code? :cry::cry:

@will_of_ken I found one mistake. for test cases like these:
10009999000
1000999000
100099000
Your output is incorrect:
10009998999
1000998999
100098999
whereas the output should have been:
10008999999
1000899999
100089999

1 Like

@gj15
Thanks a lot, brother…:heart_eyes: got AC… :heart_eyes:

https://www.codechef.com/viewsolution/24469756

Can you please tell me which of the test cases are failing for this solution ??
Also for some of the subtasks it shows runtime error. Any kind of help is appreciated.!