RJBIAS - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: still_me
Testers: the_hyp0cr1t3, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given an integer K in base P, find the smallest integer X \geq 0 such that K+X contains all the digits 0, 1, 2, \ldots, P-1 in base P.

EXPLANATION:

This is more of an implementation task than anything else, but being a bit careful can lead to a relatively short and clean implementation.

Instead of finding the smallest value of X, let’s find the smallest possible value of K+X; in the end, we can obtain X by subtracting K from it.

First, note that K+X will contain either P or P+1 digits: at least P since we need P distinct digits, and at most P+1 because N \leq P means we never need to go any higher.
In particular, for the answer to have P digits, all of its digits need to be distinct.

Now let’s get rid of a couple of simple edge cases:

  • If N \lt P, then the optimal value of K+X is [1, 0, 2, 3, 4, \ldots, P-1]; this is the smallest integer with all the digits.
  • Now we’re left with N = P always.
  • The largest possible P-digit number with distinct digits is [P-1, P-2, \ldots, 2, 1, 0]. If the given number is larger than this (which can be checked by comparing them lexicographically), then we must use P+1 digits, and the answer is [1, 0, 0, 2, 3, 4, \ldots, P-1]; this is the smallest P+1-digit number containing all digits.

Once those cases are out of the way, we know that it’s always possible to achieve a P-digit answer; so our task is to make all the digits distinct.

To minimize K+X, we’d like to keep as large a prefix of K unchanged as possible.
So, let’s iterate i from 1 to P.

  • if A_i hasn’t appeared before, we don’t need to increase this index right now
  • If A_i has appeared before, we must change some index \leq i in order to not have repeated digits.

Let x be the first time we meet a repeated digit (if there are no repeated digits, the answer is obviously 0 so we only focus on the case when a valid x exists).

We have to increase some digit at a position \leq x. So, let’s do the following:

  • Let’s check if we can replace A_x with something higher than it. This is only possible if there exists a digit \gt A_x that has not appeared before position x (recall that our aim is distinct digits).
  • If we can’t replace A_x with something larger than it, instead check for position x-1, then position x-2, and so on. One of these will definitely satisfy the condition since we know a P-digit answer is possible.
    • One simple way of quickly checking whether replacement is possible is to maintain a set of unseen values and find its maximum. When moving from x to x-1, insert A_{x-1} into this set of unseen elements.
    • This allows each position to be processed in \mathcal{O}(\log N) time, for \mathcal{O}(N\log N) overall. You can also maintain a boolean mark array and a pointer to it for \mathcal{O}(N) time.
  • Suppose we’ve found the position y that needs to be increased. Do the following:
    • Set A_y to the smallest unseen element larger than it
    • Then, fill positions y+1 to P with the remaining unseen elements in ascending order.

Now we have the array representing K+X, so we need to compute X = (K+X) - K.
Notice that we only need X modulo 10^9 + 7.

So, compute both K and K+X modulo 10^9 + 7 (for example, using binary exponentiation to quickly compute powers modulo the mod), and subtract one from the other to obtain the final answer.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Setter's code (C++)
// Code by Reyaan Jagnani
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define scanit(a,n) for(ll indexaa=0; indexaa<n; indexaa++) cin>>a[indexaa];
#define printit(a,n) for(ll indexaa=0; indexaa<n; indexaa++) cout<<a[indexaa]<<" "; cout<<endl;
#define pb push_back
#define precision(a) cout<<fixed<<setprecision(a)
#define testcase ll t; cin>>t; while(t--)
#define endl "\n"
#define iendl "\n", cout<<flush // FOR INTERACTIVE PROBLEMS
#define quick ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define timetaken cerr<<fixed<<setprecision(10); cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl
using namespace std;
const ll M = 1000000007;
const ll maxN = 200001;
ll fact[maxN] = {}, smallestPrimeFactor[maxN] = {}, isPrimeSieve[maxN] = {};
mt19937_64 my_rand(chrono::steady_clock::now().time_since_epoch().count());
inline bool comp(ll x,ll y) { return x<y; } // INITIALLY IN DEFAULT INCREASING ORDER (SMALL TO BIG)
inline ll mod(ll x) {ll a1=(x%M); if(a1<0){a1+=M;} return a1;}
inline ll power(ll x, unsigned ll y, ll p = LLONG_MAX) {ll res=1; x=x%p; if(x==0) {return 0;} while(y>0){ if(y&1){res=(res*x)%p;} y=y>>1; x=(x*x)%p;} return res;} // CALCULATING POWER IN LOG(Y) TIME COMPLEXITY
inline ll inversePrimeModular(ll a, ll p) {return power(a,p-2,p);}
inline void calcFact(ll n = maxN-1) { fact[0] = 1; for(ll i=1; i<=n; i++){ fact[i] = fact[i-1]*i; fact[i] = mod(fact[i]); }}
inline ll ncr(ll n, ll r) { if(n<r) return 0; return mod(inversePrimeModular(mod(fact[n-r]*fact[r]),M)*fact[n]); }
inline ll ceil(ll a, ll b) { if(b==0) return LLONG_MAX; ll ans = (a+b-1)/b; return ans; }
struct custom_hash { static uint64_t splitmix64(uint64_t x)  { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); }};
void sieve(ll n = maxN-1) { for(ll i=1; i<=n; i++) smallestPrimeFactor[i] = i; for(ll i=2; (i*i)<=n; i++) { if(smallestPrimeFactor[i]==i) { for(ll j=(i*i); j<=n; j+=i) { smallestPrimeFactor[j] = min(smallestPrimeFactor[j], i); } } } for(ll i=2; i<=n; i++) { if(smallestPrimeFactor[i]==i) isPrimeSieve[i] = 1; } }
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x << " : "; _print_(x);cerr << endl;
#else
#define dbg(x)
#endif
void _print_(ll t) {cerr << t;}
void _print_(int t) {cerr << t;}
void _print_(string t) {cerr << t;}
void _print_(char t) {cerr << t;}
void _print_(ld t) {cerr << t;}
void _print_(double t) {cerr << t;}
template <class T, class V> void _print_(pair <T, V> p);
template <class T> void _print_(vector <T> v);
template <class T> void _print_(set <T> v);
template <class T, class V> void _print_(map <T, V> v);
template <class T> void _print_(multiset <T> v);
template <class T, class V> void _print_(pair <T, V> p) {cerr << "{"; _print_(p.ff); cerr << ","; _print_(p.ss); cerr << "}";}
template <class T> void _print_(vector <T> v) {cerr << "[ "; for (T i : v) {_print_(i); cerr << " ";} cerr << "]";}
template <class T> void _print_(set <T> v) {cerr << "[ "; for (T i : v) {_print_(i); cerr << " ";} cerr << "]";}
template <class T> void _print_(multiset <T> v) {cerr << "[ "; for (T i : v) {_print_(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print_(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print_(i); cerr << " ";} cerr << "]";}
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
            
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void case2(vector<ll> &vect, vector<ll> &final, vector<ll> &m, ll n, ll i, ll large)
{
    for(ll j=0; j<i; j++)
        final.pb(vect[j]);
    for(ll j=large-1; j>vect[i]; j--)
    {
        if(!m[j])
            large = j;
    }
    final.pb(large);
    m[large] = 1;
    for(ll i=0; i<m.size(); i++)
    {
        if(!m[i])
            final.pb(i);
    }
}
ll solve(vector<ll> &vect, vector<ll> &final, ll p)
{
    ll ans = 0;
    reverse(all(vect));
    reverse(all(final));
    while(final.size() > vect.size())
        vect.pb(0);
    while(final.size() < vect.size())
        final.pb(0);
    for(ll i=0; i<vect.size(); i++)
    {
        ll temp1 = mod(final[i]*power(p,i,M));
        ll temp2 = mod(vect[i]*power(p,i,M));
        ans += mod(temp1 - temp2);
        ans = mod(ans);
    }
    return ans;
}
int main()
{
    quick;
#ifndef ONLINE_JUDGE
    freopen("edge.in", "r", stdin);
    freopen("edge.out", "w", stdout);
    // freopen("error.txt", "w", stderr);
#endif
    ll sum = 0, k = 2;
    ll T = readIntLn(1,1e4);
    while(T--)
    {
        // dbg(k);
        k+=2;
        ll n = readIntSp(1,1e6);
        ll p = readIntLn(1,1e6);
        sum += p;
        assert(n<=p);
        vector<ll> vect(n);
        for(ll i=0; i<n-1; i++)
            vect[i] = readIntSp(0,p-1);
        vect[n-1] = readIntLn(0,p-1);
        assert(vect[0]!=0);
        vector<ll> m(p), final;
        if(n<p)
        {
            final.pb(1);
            final.pb(0);
            for(ll i=2; i<=p-1; i++)
                final.pb(i);
            cout<<solve(vect, final, p)<<endl;
            continue;
        }
        ll large = p-1, i = 0;
        bool check = 1;
        while(i<n)
        {
            if(m[vect[i]])
            {
                while(large>=0 && m[large])
                    large--;
                if(large < vect[i])
                {
                    i--;
                    while(i>=0 && large < vect[i])
                    {
                        m[vect[i]] = 0;
                        large = max(large, vect[i]);
                        i--;
                    }
                    if(i<0)
                    {
                        final.pb(1);
                        final.pb(0);
                        final.pb(0);
                        for(ll j=2; j<p; j++)
                            final.pb(j);
                    }
                    else
                    {
                        m[vect[i]] = 0;
                        case2(vect, final, m, n, i, large);
                    }
                }
                else
                    case2(vect, final, m, n, i, large);
                check = 0;
                break;
            }
            else
                m[vect[i]] = 1;
            i++;
        }
        if(check)
            cout<<"0"<<endl;
        else
            cout<<solve(vect, final, p)<<endl;
    }
    assert(sum<=1e6);
    assert(getchar()==-1); // Ensures that there are no extra characters at the end.
    cerr<<"SUCCESS\n"; // You should see this on the http://campus.codechef.com/files/stderr/SUBMISSION_ID page, at the bottom.
    timetaken;
    return 0;
}
/*


1. Binary Search / Binary Search on Answer
2. Bit
3. Parity (Odd / Even)
4. DP / Greedy
5. Graph / Bi-Partite
*/  
Tester's code (C++)
/**
 * the_hyp0cr1t3
 * 04.01.2023 16:18:06
**/
#ifdef W
    #include <k_II.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
#endif

// -------------------- Input Validator Start --------------------

#define read_int_sp(x, L, R) val.read_int(x, L, R, ' ', __LINE__, #x)
#define read_int_ln(x, L, R) val.read_int(x, L, R, '\n', __LINE__, #x)

#define read_vec(vec, N, L, R) val.read_vector(vec, N, L, R, __LINE__, #vec)

#define read_str_sp(x, L, R, chset) val.read_string(x, L, R, chset, ' ', __LINE__, #x)
#define read_str_ln(x, L, R, chset) val.read_string(x, L, R, chset, '\n', __LINE__, #x)

constexpr int max_digits = 19;

enum test_type { single_test, multi_tests };
enum char_set { alpha, binary, digit, gridwalls };

template <test_type T = single_test> class validator {
    int tests, current_test {0}, input_line_no {1}, input_col_no {0};

   public:
    template <test_type U = T,
      std::enable_if_t<
        std::is_same<validator<U>, validator<single_test>>::value> * = nullptr>
    validator() : tests {1} {}

    template <test_type U = T,
      std::enable_if_t<
        std::is_same<validator<U>, validator<multi_tests>>::value> * = nullptr>
    validator(int tests_lb, int tests_ub) {
        read_int(tests, tests_lb, tests_ub, '\n', -1, "tests");
    }

#define FAIL(cond, msg)                                                             \
    if (cond) {                                                                     \
        std::cerr << msg "while reading\n"                                          \
                  << "> symbol \"" << label << "\" (line " << line << ")\n"         \
                  << "> in test " << current_test << '\n'                           \
                  << "> at pos " << input_line_no << ':' << input_col_no << '\n';   \
        abort();                                                                    \
    }

    template <typename U = int, typename = std::enable_if_t<std::is_integral<U>::value>>
    void read_int(
      U &x, int64_t L, int64_t R, char delim, int line = -1, const char *label = "") {
        int64_t res = 0;
        int len = 0, leading = -1;
        bool is_negative = false;
        while (true) {
            char c = std::getchar();
            ++input_col_no;

            if (c == '-') {
                FAIL(len > 0, "error: found invalid symbol \'-\'\n")
                is_negative = true;

            } else if ('0' <= c and c <= '9') {
                res = res * 10 + c - '0';
                if (++len == 1)
                    leading = c - '0';

                FAIL(leading == 0 and len > 1, "error: found leading zeroes\n")
                FAIL(leading == 0 and is_negative, "error: found negative zero\n")
                FAIL(len > max_digits or len == max_digits and leading > 1,
                  "error: value will overflow in64_t\n")
            } else if (c == delim) {
                if (is_negative)
                    res *= -1;

                if (res < L or R < res) {
                    std::cerr << "error: found value " << res
                              << " expected to be in range [" << L << ", " << R << "]\n";
                    FAIL(true, "")
                }

                x = res;

                if (delim == '\n') ++input_line_no, input_col_no = 0;

                return;

            } else {
                const char *cc = c == '\n' ? "\n" : &c;
                std::cerr << "error: found invalid character \'" << cc << "\'\n";
                FAIL(true, "")
            }
        }
    }

    int read_string(std::string &s,
      int L, int R, char_set chset, char delim, int line = -1, const char *label = "") {
        std::string res;
        char c;
        while (res.size() <= R) {
            c = std::getchar();
            if (c == EOF or c == delim)
                break;
            res += c;
            if (chset == binary) {
                if (c != '0' and c != '1') {
                    const char *cc = c == '\n' ? "\n" : &c;
                    std::cerr << "error: found invalid character \'" << cc << "\'\n";
                    FAIL(true, "")
                }
            } else if (chset == alpha) {
                if (c < 'a' or 'z' < c) {
                    const char *cc = c == '\n' ? "\n" : &c;
                    std::cerr << "error: found invalid character \'" << cc << "\'\n";
                    FAIL(true, "")
                }
            } else if (chset == digit) {
                if (c < '0' or '9' < c) {
                    const char *cc = c == '\n' ? "\n" : &c;
                    std::cerr << "error: found invalid character \'" << cc << "\'\n";
                    FAIL(true, "")
                }
            } else if (chset == gridwalls) {
                if (c != '.' and c != '#') {
                    const char *cc = c == '\n' ? "\n" : &c;
                    std::cerr << "error: found invalid character \'" << cc << "\'\n";
                    FAIL(true, "")
                }
            }
        }

        FAIL(c == EOF, "Unexpected EOF\n")

        if (res.length() < L or R < res.length()) {
            std::cerr << "error: found string of length " << res.length()
                      << " expected to be in range [" << L << ", " << R << "]\n";
            FAIL(true, "")
        }

        s = res;
        return res.length();
    }

    template <typename U = int, typename = std::enable_if_t<std::is_integral<U>::value>>
    void read_vector(
      std::vector<U> &vec, int N, int L, int R, int line = -1, const char *label = "") {
        vec.resize(N);
        for (int i = 0; i < N - 1; i++)
            read_int(vec[i], L, R, ' ', line, label);
        read_int(vec[N - 1], L, R, '\n', line, label);
    }

    bool do_test() { return ++current_test <= tests; }

    ~validator() {
#ifndef W
        if (std::getchar() != EOF) {
            std::cerr << "error: expected EOF\n";
            abort();
        }
#endif
    }
};

// -------------------- Input Validator End --------------------

int main() {
#if __cplusplus > 201703L
    namespace R = ranges;
#endif
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    constexpr int MOD = 1'000'000'000 + 7;
    int64_t sum_b = 0, sum_b2 = 0, case1 = 0, case2 = 0, case3 = 0;

    validator<multi_tests> val(1, 10'000);

    auto eval = [](const vector<int> &p, int b) {
        int64_t ans = 0;
        for (auto x: p)
            ans = (ans * b + x) % MOD;
        return ans;
    };

    while (val.do_test()) {
        int n, b;
        read_int_sp(n, 1, 1e6);
        read_int_ln(b, 2, 1e6);
        assert(n <= b);
        sum_b += b;
        sum_b2 += 1LL * b * b;

        vector<int> A, B(b);
        read_vec(A, n, 0, b - 1);
        assert(A[0] > 0);

        // case 1: make it [1, 0, 2, 3, 4...]
        if (n < b) {
            iota(B.begin(), B.end(), 0);
            swap(B[0], B[1]);
            ++case1;
        } else {
            iota(B.begin(), B.end(), 0);
            reverse(B.begin(), B.end());

            // case 2: make it [1, 0, 0, 2, 3, 4...]
            if (A > B) {
                B.push_back(1);
                reverse(B.begin(), B.end());
                B[2] = 0;
                ++case2;
            } else {

                B = A;
                vector<bool> used(n);
                int can_inc = -1, top = n - 1;
                for (int i = 0; i < n; i++) {
                    while (top >= 0 and used[top]) top--;
                    if (top > A[i])
                        can_inc = i;

                    if (used[A[i]])
                        break;

                    used[A[i]] = true;
                }

                if (count(used.begin(), used.end(), true) < n) {
                    used.assign(n, 0);
                    int i = 0;
                    while (i < can_inc) {
                        used[A[i]] = true;
                        ++i;
                    }

                    ++B[i];
                    while (used[B[i]]) ++B[i];
                    used[B[i]] = true;

                    top = 0;
                    while (++i < n) {
                        while (used[top]) top++;
                        B[i] = top++;
                    }

                    ++case3;
                } // else A is already good
            }

        }

        cout << (eval(B, b) - eval(A, b) + MOD) % MOD << '\n';
    }

    cerr << "Sum B: " << sum_b << '\n';
    cerr << "Sum B^2: " << sum_b2 << '\n';
    cerr << "10234...  cnt: " << case1 << '\n';
    cerr << "100234... cnt: " << case2 << '\n';
    cerr << "other cnt:     " << case3 << '\n';

} // ~W
Tester's code (C++)
// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

// -------------------- Input Checker Start --------------------
 
long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}
 
string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
 
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }
 
vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}
 
// -------------------- Input Checker End --------------------

const int MOD = hell;
 
struct mod_int {
    int val;
 
    mod_int(long long v = 0) {
        if (v < 0)
            v = v % MOD + MOD;
 
        if (v >= MOD)
            v %= MOD;
 
        val = v;
    }
 
    static int mod_inv(int a, int m = MOD) {
        int g = m, r = a, x = 0, y = 1;
 
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }
 
        return x < 0 ? x + m : x;
    }
 
    explicit operator int() const {
        return val;
    }
 
    mod_int& operator+=(const mod_int &other) {
        val += other.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
 
    mod_int& operator-=(const mod_int &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
           #if !defined(_WIN32) || defined(_WIN64)
                return x % m;
           #endif
           unsigned x_high = x >> 32, x_low = (unsigned) x;
           unsigned quot, rem;
           asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (m));
           return rem;
    }
 
    mod_int& operator*=(const mod_int &other) {
        val = fast_mod((uint64_t) val * other.val);
        return *this;
    }
 
    mod_int& operator/=(const mod_int &other) {
        return *this *= other.inv();
    }
 
    friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
    friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
    friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
    friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
 
    mod_int& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
 
    mod_int& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
 
    mod_int operator++(int32_t) { mod_int before = *this; ++*this; return before; }
    mod_int operator--(int32_t) { mod_int before = *this; --*this; return before; }
 
    mod_int operator-() const {
        return val == 0 ? 0 : MOD - val;
    }
 
    bool operator==(const mod_int &other) const { return val == other.val; }
    bool operator!=(const mod_int &other) const { return val != other.val; }
 
    mod_int inv() const {
        return mod_inv(val);
    }
 
    mod_int pow(long long p) const {
        assert(p >= 0);
        mod_int a = *this, result = 1;
 
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            a *= a;
            p >>= 1;
        }
 
        return result;
    }
 
    friend ostream& operator<<(ostream &stream, const mod_int &m) {
        return stream << m.val;
    }
    friend istream& operator >> (istream &stream, mod_int &m) {
        return stream>>m.val;   
    }
};

int solve(){
 		int n = readIntSp(1,1e6);
 		static int sum_n = 0;
 		sum_n += n;
 		assert(sum_n <= 1e6);
 		int b = readIntLn(max(2LL,n),1e6);
 		vector<int> a = readVectorInt(n,0,b - 1);
 		assert(a[0] != 0);
 		mod_int temp = 0;
 		set<int> st;
 		for(auto i:a){
 			st.insert(i);
 			temp = temp*b + i;
 		}
 		if(st.size() == b){
 			cout << 0 << endl;
 			return 0;
 		}
 		if(n < b){
 			mod_int val = b; 
 			for(int i = 2; i < b; i++){
 				val = val*b + i;
 			}
 			cout << val - temp << endl;
 			return 0;
 		}
 		vector<int> mx;
 		for(int i = b - 1; i >= 0; i--) mx.push_back(i);
 		if(a > mx){
 			mod_int val = b*b;
 			for(int i = 2; i < b; i++){
 				val = val*b + i;
 			}
 			cout << val - temp << endl;
 			return 0;
 		}
 		set<int> rem;
 		for(int i = 0; i <= b - 1; i++) rem.insert(i);
 		mod_int val = 0;
 		bool inv = false;

 		int pos = -1;
 		int cnt = 0;
 		for(auto i:a){
 			auto it = rem.upper_bound(i);
 			if(it != rem.end()){
 				pos = cnt;
 			}	

 			if(rem.count(i) == 0) break;
 			rem.erase(i);
 			cnt++;
 		}
 		rem.clear();
 		for(int i = 0; i <= b - 1; i++) rem.insert(i);
 		for(int i = 0; i < pos; i++){
 			val = val*b + a[i];
 			rem.erase(a[i]);
 		}
 		auto it = rem.upper_bound(a[pos]);
 		val = val*b + *it;
 		rem.erase(it);
 		for(auto i: rem){
 			val = val*b + i;
 		}

 		cout << val - temp << endl;

 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t = readIntLn(1,10000);
    while(t--){
        solve();
    }
    return 0;
}
Editorialist's code (Python)
mod = 10**9 + 7

def solve(n, b, a):
	if n < b: return [1, 0] + list(range(2, b))
	for i in range(n):
		if a[i] < b-1-i: break
		if a[i] > b-1-i: return [1, 0, 0] + list(range(2, b))
	mark = [0]*b
	for i in range(n):
		if mark[a[i]] == 0:
			mark[a[i]] = 1
			continue
		digit = b-1
		while mark[digit] == 1: digit -= 1
		pos = i
		while pos >= 0:
			if pos < i:
				mark[a[pos]] = 0
				digit = max(digit, a[pos])
			if digit > a[pos]: break
			pos -= 1
		prv = digit
		digit -= 1
		while digit >= 0:
			if digit <= a[pos]: break
			if mark[digit] == 0: prv = digit
			digit -= 1
		mark[prv] = 1
		a[pos] = prv
		digit = 0
		for j in range(pos+1, n):
			while mark[digit] == 1: digit += 1
			mark[digit] = 1
			a[j] = digit
		break
	return a

def convert(a, base):
	num = 0
	for i in range(len(a)):
		num = num*base + a[i]
		num %= mod
	return num

for _ in range(int(input())):
	n, b = map(int, input().split())
	a = list(map(int, input().split()))
	acopy = a[:]
	ans = solve(n, b, a)
	print((convert(ans, b) - convert(acopy, b))%mod)

One can just write the brute force recursive solution to pass the problem, as the number of possible cases (if chosen greedily) will be very less.

My approach was to keep a variable tlo, which will tell whether it’s still matching with the given number or not, if not then greedily we should place the remaining digits in order from left to right, if yes then either we should place the same digit or the next possible digit which is not repeated yet. Just recursively do these steps.

If you still did not get the answer then the final value of X+k will be having b+1 digits and will look like 1002345…

My submission : Solution: 84434800 | CodeChef