PROBLEM LINK:
Contest
Practice link
Setter: Aneesh D H
Tester: Rahul Sawantdesai
PRE-REQUISITE:
Digit DP
PROBLEM:
Given some integers A, B and K, find the smallest valid integer x \in [A, B].
An integer is considered valid if and only if:
- x \; \% \; K = 0
- For every digit x_i except the least significant digit, there is another digit x_j to the right of x_i (j > i), which is a factor of x_i. x_0 is the most significant digit and x_{len(x)-1} is the least significant digit.
EXPLANATION:
To solve subtask 1, it is enough to check every multiple of K in the range [A, B]. The time complexity of this approach is O(B)
Iterating over every possible integer is not enough to solve subtask 2. We need to find something better.
This can be done using digit DP. If you are new to digit DP, please go through this blog at Codeforces.
Let us reverse the notation used in condition 2 - x_0 is the least significant digit and x_{len(x)-1} is the most significant digit.
DP Parameters
What parameters will uniquely describe a state? Clearly we need:
- pos - the current digit position being considered.
- rem - the remainder with respect to K so far.
- digmask - the digits that have been used so far for which condition 2 is not satisfied yet.
Apart from the above, we need two more parameters - fa and fb that will tell us if the number is guaranteed to be >=A or <=B respectively.
Combining all the parameters, we define two 5-D dp tables prod[pos][rem][digmask][fa][fb] and num[pos][rem][digmask][fa][fb].
The table prod maintains the maximum possible digit product and the table num maintains the corresponding integer.
For example, let us say A = 11100, B = 99900 and K = 9. Let the digits used so far be x_4 = 4, x_3 = 2, x_2 = 5, with x_1 and x_0 yet to be explored. This state would have:
pos = 1 as the digit to be chosen next is x_1.
rem = (4*10^{4} + 2*10^{3} + 5*10^{2}) % 9 = 2
digmask = (0000100100)_{b} = 36 - since d_3 = 2 and d_2 = 5 are the two digits for whom condition 2 is yet to be satisfied. For d_4, the condition is satisfied because of d_3.
fa = 1
fb = 1
Base Case
When pos = -1, if rem = 0 and digmask has exactly 1 bit set, the integer x that was constructed leading to this state is valid. Otherwise it is invalid.
DP Recurrence
Let the problem that we are solving be (pos, rem, digmask, fa, fb).
Let the digits that can be used be p to q. Let us say, initially p = max(A_{pos}, 1) and q = max(B_{pos}, 1). It is clear to see that we can always use max(A_{pos}, 1) to max(B_{pos}, 1).
It is easy to see that if fa = 1, we can also use digits [1, A_{pos}-1] and if fb = 1, we can also use digits [B_{pos}+1, 9]. Based on these if conditions, we update p and q.
Note that p <= q is always true. B_{pos} < A_{pos} implies that at least one of fa or fb is 1, since A <= B.
Let us see what subproblem would need to be solved if we choose the digit d for pos.
The new position would be pos - 1.
The new remainder would be (rem + d * 10^{pos})\%K.
The new fa would be fa \; | \; (d > A_{pos}).
The new fb would be fb \; | \; (d < B_{pos}), where | is bitwise OR.
We also update digmask by setting all bits which are multiples of d to 0, and setting bit d to 1 - let us call this function find\_new\_mask.
We need to find the least digit d \in [p, q] that maximises prod[pos-1][(rem + d * 10^{pos})\%K][find\_new\_mask(digmask, d)][fa \; | \; (d > A_{pos})][fb \; | \; (d < B_{pos})].
Now based on the digit d found above we update the tables prod and num.
The minimum number of digits that x can have is A_{len} and the maximum number of digits that x can have is B_{len}.
The recurrence we used above doesn’t use digit 0 in the answer. So if we solve only the subproblem with pos = B_{len}, it is not enough as that would only account for x with exactly B_{len} non-zero digits.
So we find the best answer among the subproblems (A_{len}, 0, 0, fa, fb), (A_{len + 1}, 0, 0, fa, fb) … (B_{len}, 0, 0, fa, fb).
Here fa = 0 only for pos = A_{len}. If pos > A_{len}, then it is guaranteed that x > A.
Similarly fb = 0 only for pos = B_{len}. If pos < B_{len}, then it is guaranteed that x < B.
An alternative would be to use a flag for leading zeroes just like the flags fa and fb. Then it is enough to solve for only pos = B_{len}.
Setter's Code
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define adj_list vector<vi>
#define endl "\n"
#define INF_INT 2e9
#define INF_LL 2e18
#define matmax 25
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define pl pair<ll, ll>
#define pll pair<ll, pair<ll, ll> >
#define vi vector<int>
#define vl vector<ll>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long int ll;
ll a, b, k, dp[2][2][20][110][1024], number[2][2][20][110][1024], mult[21], mult2[21], t;
vi aDigs, bDigs;
void getDigits(ll num, vi *arr) {
while (num > 0) {
arr->pb(num%10);
num /= 10;
}
}
pl solve(int f1, int f2, int pos, int rem, int mask) {
if (pos == -1 and __builtin_popcount(mask) <= 1 and rem == 0) {
return mp(1, 0);
} else if (pos == -1) {
return mp(0, -1);
}
if (dp[f1][f2][pos][rem][mask] != -1) {
return mp(dp[f1][f2][pos][rem][mask], number[f1][f2][pos][rem][mask]);
}
dp[f1][f2][pos][rem][mask] = 0;
number[f1][f2][pos][rem][mask] = -1;
int beg = 0, end = 9;
if (f1 == 0) {
beg = aDigs[pos];
}
if (f2 == 0) {
end = bDigs[pos];
}
beg = max(beg, 1);
for (int i = beg; i <= end; i++) {
int newf1 = f1 | (i > aDigs[pos]);
int newf2 = f2 | (i < bDigs[pos]);
int newrem = (rem + mult[pos]*i)%k;
int newmask = mask;
for (int j = i; j <= 9 and i != 0; j += i) {
if (newmask & (1<<j)) {
newmask ^= (1<<j);
}
}
newmask |= (1<<i);
pl curr = solve(newf1, newf2, pos-1, newrem, newmask);
if (curr.first * ll(i) > dp[f1][f2][pos][rem][mask]) {
dp[f1][f2][pos][rem][mask] = curr.first * ll(i);
number[f1][f2][pos][rem][mask] = ll(i)*mult2[pos] + curr.second;
}
}
return mp(dp[f1][f2][pos][rem][mask], number[f1][f2][pos][rem][mask]);
}
int main() {
fastio;
cin>>t;
while (t--) {
memset(dp, -1, sizeof(dp));
memset(number, -1, sizeof(number));
aDigs.clear();
bDigs.clear();
cin>>a>>b>>k;
assert(1 <= a and a <= 1e18);
assert(1 <= b and b <= 1e18);
assert(1 <= k and k <= 100);
assert(a <= b);
getDigits(a, &aDigs);
getDigits(b, &bDigs);
int ad = aDigs.size(), bd = bDigs.size();
while (aDigs.size() < bDigs.size()) {
aDigs.pb(0);
}
mult[0] = 1;
mult2[0] = 1;
for (int i = 1; i <= 19; i++) {
mult[i] = (mult[i-1] * 10ll)%k;
mult2[i] = (mult2[i-1] * 10ll);
}
pl ans = mp(0, -1);
for (int i = ad; i <= bd; i++) {
int f1 = 1, f2 = 1;
if (i == bd)
f2 = 0;
if (i == ad)
f1 = 0;
pl curr = solve(f1, f2, i-1, 0, 0);
if (curr.first > ans.first and (a <= curr.second and b >= curr.second)) {
ans = curr;
}
}
if (ans.first == 0) {
cout<<-1<<endl;
} else {
cout<<ans.first<<" "<<ans.second<<endl;
}
}
return 0;
}
Time Complexity: O(log_{10}B * K * 2^{10})
It is possible to optimize the solution above considerably by maintaining the GCD of the digits for which condition 2 is not satisfied, in place of digmask. This brings down the time complexity to O(log_{10}B * K * 10). Refer to submission for implementation.
PS: I tried to explain it as properly as I could. Please let me know if there are any mistakes or if something is unclear.