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
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.
If anyone has any idea how to solve it, or knows any similiar problem, please help.
try manipulating states with iterative dp
Wouldn't the dp be $$$n*n*m/2$$$ operations? Which is about $$$5e8$$$ operations which should pass.
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.
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.
"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)$$$?
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)$$$
Got it. Thanks
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.
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$$$Still couldn't get the solution,if anyone spares their time to solve it,thanks in advance (i couldn't )