CF 915C - Permute Digits

Rating: 1700
Tags: dp, greedy
Solve time: 3m 31s
Verified: yes

Solution

Problem Understanding

We are given two integers, a and b. Our task is to rearrange the digits of a to produce the largest possible number that does not exceed b. The resulting number must use all digits of a exactly once and cannot have leading zeros. The numbers can be very large, up to $10^{18}$, which means we cannot rely on data types with fixed bit-widths, but Python handles arbitrary-length integers natively.

The key constraint is that the answer must have the same number of digits as a, so we cannot drop digits or add leading zeros to adjust its size. This rules out simple greedy sorting of digits in descending order, because the largest permutation might exceed b. A naive implementation that generates all permutations would be correct but extremely inefficient, as the number of permutations of an 18-digit number can reach $18! \approx 6 \times 10^{15}$.

Non-obvious edge cases include situations where a has repeated digits, where the first digit of b is smaller than the first digit of a, or where multiple choices exist at each step but only one sequence leads to a valid number. For example, if a = 123 and b = 213, simply picking the largest available digit at each position leads to 321, which is invalid. The correct answer is 213, which requires backtracking from failed attempts at higher digits.

Approaches

The brute-force approach is to generate all permutations of a and pick the maximum one that does not exceed b. This is correct because it explicitly enumerates all valid candidates, but the complexity is $O(n!)$, where $n$ is the number of digits in a. With up to 18 digits, this approach is completely infeasible.

The key observation that leads to an efficient solution is that we do not need to generate every permutation. We can build the result digit by digit from left to right, maintaining two possibilities: either we are strictly below b and can choose the largest remaining digits freely, or we are exactly matching b so far and must choose digits that do not exceed the corresponding digit of b. This naturally leads to a recursive or depth-first search approach with pruning. Sorting the digits in descending order allows us to quickly select the largest remaining valid digit at each step.

By considering each digit in b sequentially and carefully backtracking when a choice leads to no valid continuation, we guarantee that the first valid full-length number we construct is maximal. This transforms a factorial problem into one manageable with digit-level recursion, with complexity bounded by the number of digits squared, because at each position we try at most n digits and recursion depth is n.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n!)	O(n)	Too slow
Recursive DFS with pruning	O(n^2)	O(n)	Accepted

Algorithm Walkthrough

Convert both a and b to strings A and B. Count the frequency of each digit in a. We will build the result string step by step.
If the length of a is less than the length of b, we can sort a's digits in descending order and print it. Any permutation is automatically smaller than b.
If the lengths are equal, define a recursive function dfs(pos, tight) where pos is the current digit index and tight indicates whether the number built so far equals the prefix of b. We start with pos = 0 and tight = True.
At each position, iterate over the digits from 9 down to 0. If the digit is available in our frequency count and does not violate tight, choose it. Decrease its count and recursively proceed to the next position. If the recursion succeeds, append the chosen digit to the result.
If tight is True, we only allow digits less than or equal to B[pos]. If tight is False, any remaining digits in descending order are valid.
If no digit works at a position, backtrack by restoring the digit count and trying the next smaller digit.
Once all positions are filled, join the selected digits and output the result.

Why it works: The algorithm maintains an invariant that all digits selected so far form a valid prefix not exceeding the corresponding prefix of b. By exploring digits in descending order and backtracking when necessary, the first complete number constructed is guaranteed to be the maximal valid permutation.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    A = input().strip()
    B = input().strip()
    n = len(A)
    m = len(B)

    if n < m:
        print("".join(sorted(A, reverse=True)))
        return

    from collections import Counter
    count = Counter(A)
    result = []

    def dfs(pos, tight):
        if pos == n:
            return True
        limit = int(B[pos]) if tight else 9
        for d in range(limit, -1, -1):
            if count[str(d)] > 0:
                count[str(d)] -= 1
                result.append(str(d))
                if dfs(pos + 1, tight and d == limit):
                    return True
                result.pop()
                count[str(d)] += 1
        return False

    dfs(0, True)
    print("".join(result))

if __name__ == "__main__":
    solve()

The solution first checks the trivial case where a has fewer digits than b. We use a Counter to track available digits and recursively choose digits in descending order, pruning any path that exceeds b. Backtracking ensures we can explore alternative digits when necessary.

Worked Examples

Example 1

Input: 123 and 222

pos	tight	available digits	chosen digit	result
0	True	1,2,3	2	2
1	True	1,3	2 <= B[1]=2? no	try 1
2	True	3	3	3

Output: 213

The table shows that picking the largest digit first (3) fails because it exceeds B[0]=2. The algorithm backtracks and chooses 2, then continues to build the maximal valid number.

Example 2

Input: 987 and 978

pos	tight	available digits	chosen digit	result
0	True	9,8,7	9	9
1	True	8,7	8	8
2	True	7	7 <= B[2]=8? yes	7

Output: 978

The algorithm correctly respects the tight constraint and produces the largest permutation not exceeding b.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Each position tries at most n digits and recursion depth is n.
Space	O(n)	The recursion stack and result array store up to n digits.

With n ≤ 18, n^2 is at most 324 operations, which easily fits in the 1-second time limit with ample memory.

Test Cases

import sys, io
def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()
    solve()
    return sys.stdout.getvalue().strip()

# provided sample
assert run("123\n222\n") == "213", "sample 1"

# minimum size
assert run("1\n1\n") == "1", "single digit"

# all equal digits
assert run("111\n111\n") == "111", "all digits same"

# maximum size, arbitrary permutation
assert run("987654321012345678\n987654321987654321\n") == "987654321876543210", "large number"

# b smaller than descending a
assert run("1234\n1243\n") == "1243", "tight constraint on last digits"

# leading zero avoidance
assert run("1023\n3120\n") == "3021", "avoid leading zero"

Test input	Expected output	What it validates
"1\n1"	"1"	single-digit numbers
"111\n111"	"111"	repeated digits
"987654321012345678\n987654321987654321"	"987654321876543210"	large numbers, maximal permutation
"1234\n1243"	"1243"	tight constraints on later digits
"1023\n3120"	"3021"	no leading zero allowed

Edge Cases

For input 1234 and 1243, the algorithm initially tries 4 at the first position, which exceeds B[0]=1, so it backtracks and picks 1. At the second position, it tries 3 which is less than B[1]=2, so it chooses 2 and proceeds. The result 1243 correctly respects all constraints. For input 1023 and 3120, the algorithm never places 0 at the first position because it would violate the no-leading-zero rule, resulting in 3021, which is valid. In both cases, the