import java.io.; import java.util.; public clas...

Question

import java.io.;
import java.util.;

public class Main {
static String L, R;
static int N;
// memo[pos][tightLow?1:0][tightHigh?1:0]
static int[][][] memo;
static int[] lDigits, rDigits;

text
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    int t = Integer.parseInt(br.readLine().trim());
    while (t-- > 0) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        L = st.nextToken();
        R = st.nextToken();
        N = L.length();
        lDigits = new int[N];
        rDigits = new int[N];
        for (int i = 0; i < N; i++) {
            lDigits[i] = L.charAt(i) - '0';
            rDigits[i] = R.charAt(i) - '0';
        }
        memo = new int[N][2][2];
        for (int i = 0; i < N; i++) {
            for (int a = 0; a < 2; a++) {
                for (int b = 0; b < 2; b++) {
                    memo[i][a][b] = -1;
                }
            }
        }
        int answer = dp(0, 1, 1);
        out.println(answer);
    }
    out.flush();
}

// pos: current digit position [0..N)
// tightLow: if prefix so far equals L's prefix (1=true, 0=false)
// tightHigh: if prefix so far equals R's prefix (1=true, 0=false)
static int dp(int pos, int tightLow, int tightHigh) {
    if (pos == N) {
        return 0;
    }
    if (memo[pos][tightLow][tightHigh] != -1) {
        return memo[pos][tightLow][tightHigh];
    }
    int res = Integer.MAX_VALUE;
    int low = tightLow == 1 ? lDigits[pos] : 0;
    int high = tightHigh == 1 ? rDigits[pos] : 9;
    for (int d = low; d <= high; d++) {
        int nextTightLow = (tightLow == 1 && d == lDigits[pos]) ? 1 : 0;
        int nextTightHigh = (tightHigh == 1 && d == rDigits[pos]) ? 1 : 0;
        int cost = 0;
        if (d == lDigits[pos]) cost++;
        if (d == rDigits[pos]) cost++;
        int sub = dp(pos + 1, nextTightLow, nextTightHigh);
        res = Math.min(res, cost + sub);
    }
    memo[pos][tightLow][tightHigh] = res;
    return res;
}

}
can't we solve it in more simple way
For two integers a
and b
, we define f(a,b)
as the number of positions in the decimal representation of the numbers a
and b
where their digits are the same. For example, f(12,21)=0
, f(31,37)=1
, f(19891,18981)=2
, f(54321,24361)=3
.

You are given two integers l
and r
of the same length in decimal representation. Consider all integers l≤x≤r
. Your task is to find the minimum value of f(l,x)+f(x,r)
.

Input
Each test consists of multiple test cases. The first line contains a single integer t
(1≤t≤104
) — the number of test cases. The description of the test cases follows.

Each test case consists of a single line containing two integers l
and r
(1≤l≤r<109
).

It is guaranteed that the numbers l
and r
have the same length in decimal representation and do not have leading zeros.

Output
For each test case, output the minimum value of f(l,x)+f(x,r)
among all integer values l≤x≤r
.

Example
InputCopy
14
1 1
2 3
4 6
15 16
17 19
199 201
899 999
1990 2001
6309 6409
12345 12501
19987 20093
746814 747932
900990999 900991010
999999999 999999999
OutputCopy
2
1
0
3
2
2
1
3
3
4
3
5
12
18

Answer 1

Yes – you can turn that three-dimensional DP into a simple O(N) “find the first divergence” + “break as soon as you can” scan. Here’s the idea:

Find the first index k where L[k] != R[k].
- If there is no such k (i.e. L == R), then the only choice is X = L, so $\min f(L,X)+f(X,R) \;=\; f(L,L)+f(L,L)=2N.$
Otherwise, look at the gap
$\Delta \;=\; R[k] - L[k].$
- If $\Delta \ge 2$ , you can pick some digit strictly between L[k] and R[k] at position k, pay 0 there, and thereafter you’re completely free to avoid any further matches.
  ⇒ Answer = $2\,k$ .
- If $\Delta = 1$ , there is no “middle” digit at k, so you must choose either
  - Branch L: $X[k]=L[k]$ , cost = 1 at k, but your lower bound stays tight until you pick some suffix digit > L[j]; every time you see an ’9’ you can’t break (since you can’t go > 9) and so must match (cost = 2) — but as soon as you hit a digit < 9 you pick L[j]+1 and you’re done.
  - Branch R: $X[k]=R[k]$ , cost = 1 at k, and symmetrically every ’0’ in the suffix forces you to match (cost = 1) until you hit a digit > 0 and pick R[j]−1, then you’re free.
Concretely:
```
text
// count how many consecutive 9’s in L after k:
c9 = 0
for j = k+1 .. N-1:
  if L[j] == '9': c9++
  else: break

// count how many consecutive 0’s in R after k:
c0 = 0
for j = k+1 .. N-1:
  if R[j] == '0': c0++
  else: break

cost_branch_L =  2*k     // positions 0..k-1 must match both → 2 each
                + 1      // at k you match L[k]
                + 2*c9   // each forced 9 in suffix costs 2
cost_branch_R =  2*k
                + 1     // at k you match R[k]
                +   c0  // each forced 0 in suffix costs 1

answer = min(cost_branch_L, cost_branch_R)
```

That is O(N) per test and far simpler than a full DP.

import java.io.; import java.util.; public clas...

Question

Thought

Proposing a simpler solution

Considering a greedy approach

Recomputing prefix and suffix costs

Answer

Share this Q&A