p420.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t l_val, r_val;
int64_t answer;
vector<int64_t> candidates;

int64_t next_perm(int64_t x) {
    string s = to_string(x);
    if(next_permutation(s.begin(), s.end())) {
        return stoll(s);
    }
    return 1e18;
}

int64_t prev_perm(int64_t x) {
    string s = to_string(x);
    if(prev_permutation(s.begin(), s.end())) {
        if(s[0] == '0') {
            return 0;
        }
        return stoll(s);
    }
    return 0;
}

bool is_inside(int64_t x) { return x >= l_val && x <= r_val; }

bool has_one_similar(int64_t x) {
    if(!is_inside(x)) {
        return false;
    }

    int64_t next1 = next_perm(x);
    int64_t next2 = next_perm(next1);

    int64_t prev1 = prev_perm(x);
    int64_t prev2 = prev_perm(prev1);

    bool has_prev1 = is_inside(prev1);
    bool has_prev2 = is_inside(prev2);
    bool has_next1 = is_inside(next1);
    bool has_next2 = is_inside(next2);

    if(has_prev1) {
        return !has_prev2 && !has_next1;
    }
    if(has_next1) {
        return !has_next2;
    }
    return false;
}

void create_candidates(int64_t base, int64_t offset) {
    if(base < l_val || base > r_val) {
        return;
    }

    candidates.push_back(base);

    int64_t next = next_perm(base);
    if(next < 1e18) {
        candidates.push_back(next);
    }

    int64_t prev = prev_perm(base);
    if(prev > 0) {
        candidates.push_back(prev);
    }

    for(int digit = 0; digit < 10; digit++) {
        int64_t suff = offset;
        int64_t pow10 = 1000;

        for(int len = 0; len < 15; len++) {
            suff = suff * 10 + digit;
            pow10 *= 10;
            if(suff > r_val) {
                break;
            }

            int64_t pref = base - (base % pow10);
            int64_t extended = suff + pref;

            candidates.push_back(extended);

            int64_t next_ext = next_perm(extended);
            if(next_ext < 1e18) {
                candidates.push_back(next_ext);
            }

            int64_t prev_ext = prev_perm(extended);
            if(prev_ext > 0) {
                candidates.push_back(prev_ext);
            }
        }
    }
}

void read() { cin >> l_val >> r_val; }

void solve() {
    // We can make a few observations:
    //
    //     1) A number of the form 100...00 can't be similar.
    //
    //     2) Say we have some l,r and the most significant digit where they
    //        don't agree is i. If 10^i >= 1000 and r_i > l_i + 1, or there is
    //        at least one digit gap between l and r at position i, all the
    //        numbers that disagree with either l_i or r_i at position i can't
    //        be similar, unless all of the digits after i are the same. This
    //        might not be immediately clear, but we have the i >= 3 meaning at
    //        least 3 digits before that that can be permuted in any way. Say we
    //        end with ...abc (a != b != c), then all of the permutations will
    //        also be inside. Even for the case ...baa, we will have the aba and
    //        aab suffix options. The only uncovered option is that all digits
    //        are the same. But there are only (r_i - l_i - 1) * 9 such options.
    //
    //    3) l,r <= 10^15, where this 15 is a bit suspicious. The previous
    //       observation gave us a way to effectively prune the search space
    //       into either agreeing with l_i or r_i, which is two options. Each of
    //       them yields a new l/r of ...0...0 or ...9...9, but more
    //       importantly, we have only 2 branches and we can take them at most
    //       15 times (technically even less). 2^15 is fairly small so this
    //       might be a good direction.
    //
    //    4) We will solve in this recursive way and get candidates. Whenever we
    //       reach the last 3 digits left, we can simply enumerate all numbers
    //       without the pruning. That would be ~1000 candidates in worst case,
    //       and the double decision branching is then only 12. We also
    //       shouldn't forget the additional candidates from point (2).
    //
    //    5) After all of this, we would like to check if all these candidates
    //       are actually similar. One simple approach is to do next_perm(x),
    //       next_perm(next_perm(x)), x, prev_perm(x), prev_perm(prev_perm(x)).
    //       If more than 2 of these are within [l; r] the current candidate is
    //       not similar.
    //
    //    6) We notice that instead of the full recursion, we can combine
    //       arguments 2 and 4 and get that most branches end up being pointless
    //       when we stop matching a prefix of l or r, unless we have <= 3
    //       different characters after that, and we finish with the same
    //       sequence of the same character. This reduces the candidates
    //       significantly, as we can iterate through all 1000 x 10 x 15
    //       possible splits of this sort. We should be careful about these
    //       potentially not including the other numbers in the pair.

    answer = 0;
    candidates.clear();

    for(int64_t delta = 0; delta < 1000; delta++) {
        create_candidates(l_val, delta);
        create_candidates(r_val, delta);
    }

    sort(candidates.begin(), candidates.end());
    candidates.erase(
        unique(candidates.begin(), candidates.end()), candidates.end()
    );

    for(int64_t x: candidates) {
        if(has_one_similar(x)) {
            answer++;
        }
    }

    cout << answer << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p420.in1
======================
10 99

=================
statement.txt
======================
420. Number Permutations
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Two distinct positive integer numbers with decimal notations of the same length are called similar, if their decimal notations can be obtained from each other by permuting the digits.

How many numbers from the segment [l, r] have exactly one similar number in that segment?

Input
The input file contains two integer numbers l and r (1 ≤ l ≤ r ≤ 1015).

Output
Output one integer number — the sought amount.

Example(s)
sample input
sample output
10 99
72

=================
p420.ans1
======================
72

=================
