PROBLEM LINK:
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 
) . Suggestions are welcomed as always had been. 
got AC⌠