### nitin12384's blog

By nitin12384, 5 months ago,

Problem Name — Separate It

### Statement

You are given an array $a$ containing $n$ elements and another array $b$ containing $m$ elements. ( Both are 0 indexed ) You want to separate $a$ into $m$ non-empty contiguous subarrays, such that each element belongs to exactly one subarray.

Also, the sum of elements of $r$th subarray ( $0 \le r < m$ ) should be divisible by $b_r$.

Find the total number of way to seperate $a$ into $m$ subarrays fulfilling the given conditions, modulo $10^9 + 7$

### Input Format

$n$ $m$
$a_0 \; a_1 ... a_{n-1}$
$b_0 \; b_1 ... b_{m-1}$

First line contains two space separated integers $n$ and $m$.
Second line contains $n$ space separated integers denoting array $a$.
Third line contains $m$ space separated integers denoting array $b$.

### Constraints

$1 \le n \le 10^3$
$1 \le m \le 10^3$
$1 \le a_i \le 10^9$, where $0 \le i < n-1$
$1 \le b_i \le 10^9$, where $0 \le i < m-1$

### Examples

Sample Input Output

Source — Infosys Coding Round on 21st Jan.

I have tried a lot and I was only able to come up with a $O(n \cdot n \cdot m)$ approach using DP, but couldn't optimize further.

• +13

 » 5 months ago, # |   0 try manipulating states with iterative dp
 » 5 months ago, # |   0 Wouldn't the dp be $n*n*m/2$ operations? Which is about $5e8$ operations which should pass. my code#include using namespace std; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n, m; cin >> n >> m; int a[n], b[m]; for (int i = 0; i < n; i++) { cin >> a[i]; if (i) a[i] += a[i - 1]; } for (int i = 0; i < m; i++) { cin >> b[i]; } int dp[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp[i][j] = 0; } } for (int i = 0; i < n; i++) { for (int k = i - 1; k >= 0; k--) { int sum = a[i] - a[k]; for (int j = 1; j < m; j++) { if (sum % b[j] == 0) { dp[i][j] += dp[k][j - 1]; } } } if (a[i] % b[0] == 0) { dp[i][0]++; } } int ans = 0; cout << dp[n - 1][m - 1]; } 
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I tried exact same approach. This was TLE. Plus this solution is a little easier to come up with, and I believe this is not the intended solution.
»
5 months ago, # |
+7

Let $dp_{i, j}$ be the number of ways to distribute the elements up to but excluding $i$ into the first $j$ subarrays. We will iterate with $j$. We want the sum of this subarray to be divisible with $b_{j-1}$. That means that the sum must be congruent to $0$ mod $b_{j-1}$. That means that the prefix sums that define the subarray must be congruent modulo $b_{j-1}$. Then we can get an increase from $dp_{x, j-1}$ to $dp_{i, j}$ iff $\sum_{k=0}^x a_k \equiv \sum_{k=0}^i a_k \mod{b_{j-1}}$. You can hold the sum of $dp_{x, j-1}$ such that the prefix sum is the same in a map (you could do a simmilar thing if the values were small with an array). Now just tranzition.

### Note:

Time complexity $O(N\cdot M\cdot log N)$ and memory complexity $O(N\cdot M)$. The memory can be improved by noticing that we only use 2 colums of the dp at any given time, thus just storing 2 and reusing.

If you don't understand I will try to post some source code.

•  » » 5 months ago, # ^ |   0 "You can hold the sum of $dp_{x,j-1}$ such that the prefix sum is the same in a map" Won't we have to do this for all $b_i$ which would make it $O(nm^2)$?
•  » » » 5 months ago, # ^ |   +3 You have to use modulo $b_j$ at the $j$-th iteration. Since you do $N$ dp calculations per iteration and each calculation takes $O(logN)$ at most we end up with $O(N \cdot M \cdot logN)$
•  » » » » 5 months ago, # ^ |   0 Got it. Thanks
•  » » 5 months ago, # ^ |   0 Sorry, but didn't understand the following line. "You can hold the sum of $dp_{x,j-1}$ such that the prefix sum is the same in a map" Lets assume $s_{idx} = \sum_{i=0}^{idx-1} a_i$ I understand that, When calculating $dp_{i,j}$, I need to check for each $x$ in range $0 \le x < i$ if, $s_x$ and $s_i$ are congruent mod $b_j$. If its true we do $dp_{i,j} += dp_{x,j}$ .By storing prefix sums, we can do calculation of $dp_{i,j}$ in $O(i)$.I dont understand what map you are implying and how will I use this to find $dp_{i,j}$ in $O(log(n))$ time.
•  » » » 5 months ago, # ^ |   0 Sorry for the late reply.The map will store the sum of all $dp_{x, j-1}$ such that $s_x \equiv s_i \mod{b_j}$. Thus instead of doing a full $O(i)$ to see which $dp_{x, j-1}$ you need to add, you just add mp[s[i]%b[j]]. The idea is that you want to do all the additions at once, rather than one at a time.After you calculate $dp_{i, j}$ you will also add $dp_{i, j-1}$ to mp[s[i]%b[j]]. This has the effect of propagating the individual term $dp_{i, j-1}$ to all the $dp_{y, j}$ such that $s_y \equiv s_i \mod{b_j}$ with $y>i$
 » 5 months ago, # |   0 Still couldn't get the solution,if anyone spares their time to solve it,thanks in advance (i couldn't )