CHDIGER - EDITORIAL

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. :stuck_out_tongue:

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

Hi, could somebody will explain me where i am wrong, it worked correctly in all test cases assumed by me, may be some cases might be missing. This code is giving WA result.

My Approach -
first of all, i store all digits of the given number in a vector in same order with the help of stack.
then i found the iterator of minimum element using min_element(),
then print the digits, starting from earlier found iterator upto vecotr.end() only if value is less than d.
then print the value of d, upto vector.size()-number of times above condition in iterator loop is true.

Link to my code-
https://www.codechef.com/viewsolution/23493587

Hi, could somebody please explain me where do I go wrong, it worked correctly in all test cases assumed by me, I possibly missed on some cases. This code is giving WA result.

My Approach - I have reversed the number, stored it in a vector. Checked if the digit is to be sent for printing or not, and flagged them 0 or 1 for the same.

Thanks in advance.

Link to my code

Hi, could somebody please explain me where do I go wrong, it worked correctly in all test cases assumed by me, I possibly missed on some cases. This code is giving WA result.

My Approach - I have reversed the number, stored it in a vector. Checked if the digit is to be sent for printing or not, and flagged them 0 or 1 for the same.

Thanks in advance.

Link to my code

can anyone tell what’s wrong with my solution?
https://www.codechef.com/viewsolution/23397884

Hi, could somebody please explain me where do I go wrong, it worked correctly in all test cases assumed by me, I possibly missed on some cases. This code is giving WA result.

Link to my Solution

I removed the digits smaller than d and pushed the other digits to left and added the d at the end(as necessary)

@ashishburdak

1

223245 4

your ans - 223244

correct ans - 222444

Hope you understand what you are missing.

oo!! yes,
thank you.

I used a stack to implement the solution. Basically the stack maintains a non-decreasing sequence of characters found till now. It is maintained in amortized O(n) where n is the number of digits in the input. Then I print the stack followed by the digit for the remaining length.
Intuition is that the final output will always be a non-decreasing sequence as it is the minimum possible number.
Code can be found here: https://www.codechef.com/viewsolution/23758669

Can someone please explain the editorial solution in a easy way?