help in https://www.codechef.com/problems/DIVSUBS

i have read the editorial and had understood how to do it but in comments @midhul wrote that for (m > n) we can solve the problem using DP in O(N^2). can someone please tell me how to do this using dp for m > n!

Let dp[i][j] = true if there is a subset of the first ‘i’ elements whose sum modulo ‘m’ is ‘j’. The recurrence for this is similar to the one for subset sum, you check if there is a subset of i-1 elements that gives modulo ‘j’ or if the 'i’th element combined with some other modulo can give you ‘j’. Let ‘k’ be the remainder when the 'i’th number is divided by ‘m’. This combined with some other modulo must give you modulo ‘j’, ie., you need to find ‘y’ such that k + y = j mod m. So, y = j-k. So, dp[i][j] = dp[i-1][j] | dp[i-1][j-k]. Your answer will be dp[N][0]. Also, the complexity for this solution is O(m*n), I don’t know how to do it in O(n^2).

1 Like

can we find the elements of the subset?

Take another array prev[i][j]. If dp[i][j] is true, then it must have been because either dp[i][j-1] is true or dp[i-1][j-k] is true. Set prev[i][j] equal to 1 or 2 depending on which of one of the two is true (you can set it to either in case both are true). Basically, these values will allow you to go back one step, to the partial solution on top of which dp[i][j] was built. Each time you ‘go back’, the first dimension ‘i’ decreases by 1, and at some point you’ll reach dp[0][0]. While going back, if you see a ‘2’ in prev[x][y] for some dp[x][y], then the 'x’th element is in the subset.

1 Like

You can do this for any dynamic programming problem, where you also have to give the actual solution along with the answer.

1 Like

thanks a lot @hemanth_1