Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

viking37236's blog

By viking37236, history, 10 days ago,

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

• +3

 » 10 days ago, # |   -7 Sliding window. Left window first , right second. From 1 to n. Choose best.
•  » » 10 days ago, # ^ |   +2 bs, if you dont know dont spread misinformation.
 » 10 days ago, # |   +8 I believe you can apply a dynamic programming approach to this problem. Let $dp[i][l][r_1][r_2]$ be $true$ if and only if there exists a division of $A[:i]$ into two disjoint subsequences $(X,Y)$ (maybe empty) such that $Len(X)=l$ $Conc(X)\ mod\ M_1=r_1$ $Conc(Y)\ mod\ M_2=r_2$. The base for this dynamic programming would be that for an empty prefix of $A$ the only $true$ value corresponds to $l=0$, $r_1=0$ and $r_2=0$. To compute values for $A[:i+1]$ you can take consider all $dp[i][l][r_1][r_2]$ and then there will be two cases: $A[i+1]$ belongs to $X$ or to $Y$. So $dp[i+1][l+1][(r_1\cdot 10+A[i+1])\ mod\ M_1][r_2]$ and $dp[i+1][l][r_1][(r_2\cdot 10+A[i+1])\ mod\ M_2]$ are $true$ if $dp[i][l][r_1][r_2]$ is $true$.To obtain the answer it is enough to find all $l$, such that $dp[Len(A)][l][0][0]$ is $true$, and choose the one closest to the $\frac{Len(A)}{2}$.The solution will work in $O(N^2 \cdot M_1 \cdot M_2)$, which should be good enough for given constraints.
•  » » 10 days ago, # ^ |   +1 Great Solution! Thank you.