Given an array A of N digits, and numbers M1, M2.
Let Conc(A) be the number formed by concatenating the digits in array A. Let Len(A) be the number of digits in A.
Example: for A = [1,3,2], Conc(A) = 132 and Len(A) = 3
Your task is to divide array A into two disjoint non-empty subsequences (X, Y) such that following conditions hold true
Conc(X) is a multiple of M1
Conc(Y) is a multiple of M2
Of all possible divisions, find the minimum value of abs( Len(X) — Len(Y) ), if there is no such possible division then print "-1".
Constraints: 1 <= N, M1, M2 <= 40 1 <= A[i] <= 9
My thoughts: I am really clueless over here. The best approach I could come up with is brute force where we iterate over all possible X and thus corresponding Y (time complexity = O(2^N)) I thought that for each iteration, one could calculate the integers Conc(X), Conc(Y) and check for divisibility with M1, M2. But considering that the size of A can be 40, Conc(X) would not fit in any data type even for the case when len(X) is >20.
Any help would be great, please!
Let $$$a$$$ track $$$conc(X)$$$ $$$mod$$$ $$$M1$$$ and $$$b$$$ $$$conc(Y)$$$ $$$mod$$$ $$$M2$$$, let $$$dp1_{i, a, b}$$$ be the minimum non-negative difference of $$$len(X)$$$-$$$len(Y)$$$ when the first $$$i$$$ first digits have been processed and $$$dp2_{i, a, b}$$$ the same but for $$$len(Y)$$$-$$$len(X)$$$. The answer is $$$min$$$($$$dp1_{n, 0, 0}$$$,$$$dp2_{n, 0, 0}$$$) transitions are easy but both base cases are a little bit tricky since you must track whether $$$a$$$ is a multiple of 0 or just 0, adding some flags will be easy but perhaps you can find a cleaner implementation. Complexity is $$$O(nM1M2)$$$.
How do you write the recursive equation for this DP?
Just think in the relation between $$$dp1_{i, a, b}$$$ and $$$dp1_{i+1, a, b}$$$ when adding the $$$(i+1)$$$-th element to the first subsequence or the second subsequence, same for $$$dp2$$$.
Similar problem
This can be solved using the meet in the middle technique. Divide the 40 size array into two 20 sized arrays. You need a set<array<int, 3>> lf and a map<pair<int, int>, vector> rt. In lf store all {conc(msk) % m1, conc(((1<<20) — 1)^msk) % m2, setbits(msk)} for first and in rt store for second array mp[{conc(msk) % m1, conc(((1<<20) — 1)^msk) % m2}].push_back(setbits(msk)). Then iterate on lf and if currently you are looking at {x, y, l} then in rt you must query 1. if l > n / 2: rt[{(m1 — x) % m1, (m2 — y) % m2}][0] 2. else rt[{(m1 — x) % m1, (m2 — y) % m2, n / 2 —}].lower_bound(n / 2 — l) (look at two elements just less and just greater than n / 2 — l). Also if x == 0 and y == 0 in either half, abs(n — 2*l) is a potential answer.