PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Alexey Filinovich
Tester: Encho Mishinev
Editorialist: Taranpreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
Basic Math and Implementation.
PROBLEM:
Given a number N not containing zeroes and a non-zero digit d, we have to find out the minimum number we can obtain by applying following operation any number of times.
In an operation, you can remove any digit of N and append d to the decimal representation of N as the least significant digit.
QUICK EXPLANATION
- If we consider the decimal representation of N, we can see, that by applying an operation at ith digit (counting from least significant to most significant digit), all digits lesser significant than ith digit moves to one more significant place and d becomes the least significant digit.
- If applying operation at ith significant digit, N increases by (S_{pos-1} - S_{pos})*10^{pos} + (S_{pos-2} - S_{pos-1})*10^{pos-1} + \ldots + (D - S_0 ). Applying a bit of math, this reduction is maximum when we apply operation at the most significant position such that S_{pos} > S_{pos-1}. We can apply this operation at all such positions. S denoting the decimal representation of N.
- Now, We can also remove digits greater than d present in N (in the least significant positions). After applying all these operations, we obtain the minimum possible number required here.
EXPLANATION
First of all, Let S be the decimal representation of N, Starting from Most significant digit from the left till the least significant digit and ith significant digit denote ith digit while counting from least significant digit to most significant digit.
Let us analyze how much N increases when we apply operation at ith position. Ith digit gets replaced by (i-1)th digit, (i-1)th digit gets replaced by (i-2)th digit and so on and the last digit is replaced by digit D.
Writing down mathematically, N increases by f(pos) = (S_{pos-1}-S_{pos})*10^{pos} + (S_{pos-2}-S_{pos-1})*10^{pos-1} + \ldots +(S_0-S_1)*10^1 + (D-S_0). To minimize N, we need to choose all positions pos such that f(pos) is negative.
Important to note is that f(x) is negative if S_x > S_{x-1} for position x > 0 or if x ==0, S_0 > D holds. The reason is that Sum of all terms (of function) cannot exceed 10^x which is less than xth term (S_{x-1}-S_x)*10^x.
After understanding all this, only the implementation is left. We can iterate over every position from the most significant position to the least significant digit and check the above condition. If f(pos) is negative, we apply the operation, otherwise, we do not apply the operation.
Problem to try
Let us solve the same problem, but the number of operations are limited and are given in input. You can apply operation any number of times up to that specified limit. Also, N is now a large decimal integer of say 1000 digits. Or say 100000 digits. 
Time Complexity
Time complexity here is O(log_{10}(N)) per test case (Constant factor may vary depending upon implementation).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Click to view
#include
using namespace std;
int main()
{
int T;
cin >> T;
while (T --> 0) {
string s; cin >> s;
char d; cin >> d;
int n = s.size();
if(s[n-1] > d) {
s[n-1] = d;
}
for(int i = 0; i < n-1; ++i) {
if(s[i] > s[i+1]) {
s.erase(i, 1);
s += d;
i -= 2;
}
}
cout << s << '\n';
}
return 0;
}
Tester’s solution
Click to view
#include
#include
#include
using namespace std;
typedef long long llong;
llong n;
int d;
int digs[21];
int L = 0;
int main()
{
int t,test;
int i,j,in;
scanf("%d",&t);
for (test=1;test<=t;test++)
{
L = 0;
scanf("%lld %d",&n,&d);
while(n > 0LL)
{
L++;
digs[L] = n % 10LL;
n /= 10LL;
}
reverse(digs+1,digs+1+L);
int cur = 1;
int curd = 1;
while(curd < d)
{
for (j=cur;j<=L;j++)
{
if (digs[j] == curd)
{
int remLen = j - cur;
for (in=cur;in<=L-remLen;in++)
{
digs[in] = digs[in + remLen];
}
for (in=L-remLen+1;in<=L;in++)
{
digs[in] = d;
}
cur++;
break;
}
}
if (j > L)
curd++;
}
for (i=1;i<=L;i++)
{
if (digs[i] >= d)
digs[i] = d;
}
for (i=1;i<=L;i++)
{
printf("%d",digs[i]);
}
printf("\n");
}
return 0;
}
Editorialist’s solution
Click to view
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
// long n = nl();d = ni();
// s = ""+n;
// int[] a = new int[s.length()];
// for(int i = 0; i< s.length(); i++)a[i] = i;
// permute(a, 0);
String s = n();int d = ni();
boolean flag = true;long ans = Long.parseLong(s);
while(flag){
flag = false;
int pos = -1;
for(int i = 0; i< s.length()-1; i++)if(s.charAt(i)>s.charAt(i+1)){pos=i;break;}
if(pos==-1 && s.charAt(s.length()-1)-'0'>d){
s = s.substring(0, s.length()-1)+d;
flag = true;
}else if(pos!=-1){
s = s.substring(0, pos)+s.substring(pos+1)+d;
flag = true;
}
ans = Math.min(ans, Long.parseLong(s));
}
pn(ans);
}
String s;
int d;
void check(int[] p){
for(int i:p)p(i+" ");pn("");
long ans = Long.parseLong(s);
String t = s;
int[] a = Arrays.copyOfRange(p, 0, p.length);
for(int i = 0; i< a.length; i++){
t = t.substring(0, a[i])+t.substring(a[i]+1)+d;
pn(Long.parseLong(t));
ans = Math.min(ans, Long.parseLong(t));
for(int j = i+1; j< a.length; j++)if(a[j]>a[i])a[j]--;
}
pn("Min for this permutation "+ans);
}
void permute(int[] a, int x){
if(x==a.length)check(a);
else for(int i = x; i< a.length; i++){
int tmp = a[i];
a[i] = a[x];
a[x] = tmp;
permute(a, x+1);
tmp=a[i];
a[i] = a[x];
a[x] = tmp;
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e3+1;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
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 it differs. Suggestions are always welcomed. 