nitin12384's blog

Need help in a 1700-ish DP problem
By nitin12384, 10 months ago, In English

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.

If anyone has any idea how to solve it, or knows any similiar problem, please help.

Tags dp, easy
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

try manipulating states with iterative dp

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wouldn't the dp be $$$n*n*m/2$$$ operations? Which is about $$$5e8$$$ operations which should pass.

my code
→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "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)$$$?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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)$$$

      → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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$$$

      → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Still couldn't get the solution,if anyone spares their time to solve it,thanks in advance (i couldn't )

→ Reply