You are given an array arr of size n and an integer k. Score of an array is defined as number of its non-empty subarrays with sum = k. Your task is to find sum of scores of all the subsequences of arr. Since the answer can be very large print its modulo 1e9+7.
Input format :
First line contains T , the number of testcases. Each testcase has two lines. First line contains two integers n and k. Second line contains n integers describing arr.
Output Format :
For each testcase, print a single integer denoting sum of scores of all the subsequences of arr modulo 1e9+7
Constraints :
1<=T<=1000 1<=n<=1000 1<=k<=1000 1<=arr[i]<=1e5 Sum of n over all the testcases will not exceed 1000 Sum of k over all the testcases will not exceed 1000.
First Test Case
2
10 1
5 1 4 5 4 5 3 3 2 2
10 2
2 2 5 1 2 3 2 1 2 4
Output:
512
2592
Dry run:
For 1st tc, for subarray [1] there are 9-left out elements, possibility of taking-not-taking = 2^9 = 512 no other subarray possible, hence ans = 512
For 2nd tc, for subarray [2], there are 5 such subarrays, possibility of other 9 elements = 2 ^ 9 = 512 (for each) there are 5 such, hence ans for subarray [2] = 5 x 512 = 2560 now there is one more possible subarray [1,1], to make this as a subarray we need to exclude all the elements in between, hence new array = [2,2,5,1,1,2,4], now keeping [1,1] aside, we are left with 5 other element, possibility = 2 ^ 5 = 32 no other subarray possible
hence ans = 2560 + 32 = 2592
:)
Isn't Time complexity should be n * k * n because we have 3 nested loops. Can you Please explain on it ?
Thanks for pointing the mistake out. I had miscalculated the third loop to be of O(n) on summation over all k, but on closer inspection it looks like it will be O(n^2) over all k. This does indeed make the complexity O(n^2 * k). A better approach might be storing only the current indices and backtracking when k is achieved, which'd probably increase the complexity of the code a bit.
This is what I came up with can't guarantee it's credibility of the code because I have not tested on many cases, but the idea is that we find a subsequence with the given sum and we treat it like an subarray and the total subsequence we can form will be extra elements we can take on left and right (all of there combinations i.e. 2 ^ (left + right))
Do in the code dp[ i ][ j ][ k ] represents the ith element, j is 1 when we haven't taken any previous element, otherwise 0 and k is the sum left.
Please correct me if I'm wrong.
1 10 3 1 2 1 3 2 2 1 1 1 4
what is the answer you are getting for this testcase?
first three are t, n, k rest are numbers
2146
please explain your solution, what is the two array?
Note that values above 1000 are useless
Also see that we can deal with count of values instead of values
So maximum number of values we have to deal with is 1+2+3...t=1000
t=50
So for any subsequence we can fix its end points and count its contribution by 2^(i-1)*2^(n-j)*x
Where x is number of subsequences having sum k-a[i]-a[j] from i+1 to j-1
we can take dp(i,k) as number of subseq which make up a sum of k as a some prefix and once we fill this table we can simply multiply with the ways to chose the remaining elements from the start which is 2^i for each dp[i][k]
1 10 3 1 2 1 3 2 2 1 1 1 4
what is the answer you are getting for this testcase?
first three are t, n, k rest are numbers
int f(int ind, int sum, vector &v, int k) {
int n = v.size(); if(sum == k) { return (1ll<<(ind+1)); } if(ind == -1 || sum > k) return INT_MIN; int pick = 1, nopick = 0; if(sum == 0ll) pick = (1ll<<(n-1ll-ind)); pick *= f(ind - 1, sum + v[ind], v, k); nopick = f(ind - 1, sum, v, k); int ans = 0; if(pick > 0) ans += pick; if(nopick > 0) ans += nopick; return ans;}
signed main() { init_code(); int t; cin>>t; while(t--) { int n, k; cin>>n>>k; vector v(n); for(auto &it : v) cin>>it; cout<<f(n-1, 0, v, k)<<endl; } }
How is this solution only utilising sum and index as a 2d dp not sure it will work, still have to memoise it this is just the recursive code, please guide me regarding the above.
Orz
t=1 n=5 k=3 [3,3,3,3,3] Answer for this testcase??
80
Is this a "MEET-IN-THE-MIDDLE" problem, since the constraints are large so is it possible to solve it through DP?
no it is dp the constraints are only 10^3 * 10^3 so u can use dp to solve it.
If a subarray $$$a[l..r]$$$ has a subsequence with the sum $$$k$$$, and the subsequence includes both $$$l$$$ and $$$r$$$, then the sum increases by $$$2^l \cdot 2^{n - r - 1}$$$.
Initialize $$$dp[n + 1][k + 1]$$$ as a 2-d array of lists.
Let $$$dp[i][j]$$$ be the list of the indices in $$$[0..i]$$$ such that a subsequence having sum $$$j$$$ can be started from those indices.
$$$Transition:$$$
Case 1: The subsequence includes $$$a[i]$$$.
$$$dp[i][j] = dp[i - 1][j - a[i]]$$$
If $$$a[i] == j$$$: Add $$$i$$$ in $$$dp[i][j]$$$
Case 2: The subsequence need not include $$$a[i]$$$.
Add $$$dp[i - 1][j]$$$ in $$$dp[i][j]$$$
$$$To$$$ $$$update$$$ $$$the$$$ $$$sum:$$$
During the transition, after Case 1:
If $$$j == k$$$:
For each index $$$l$$$ in $$$dp[i][j]$$$, $$$a[l..i]$$$ follows our main idea, so increase the answer by $$$2^l \cdot 2^{n - i - 1}$$$.
$$$\sum\limits_{l \in dp[i][j]}2^l \cdot 2^{n - i - 1} = 2^{n - i - 1} \cdot \sum\limits_{l \in dp[i][j]}2^l$$$
So we can directly store the sum $$$\sum\limits_{l \in dp[i][j]}2^l$$$ in $$$dp[i][j]$$$ instead of each $$$l$$$.
My implementation (it is passing the samples)
Can't we just bruteforce all $$$[l, r]$$$ pairs and add $$$2^{l-1} \times 2^{n-r}$$$ to the answer if a[l:r] sums to k?
The problem statement says
"Your task is to find sum of scores of all the subsequences of arr."
So the entire subarray $$$a[l..r]$$$ need not be considered.
In the second test case, $$$[1,2,3,2,1]$$$ is a valid case, because we can choose $$$[1,1]$$$ which has the sum of $$$2$$$.
Thanks
Yeah I was wondering the same thing.
consider 0 as the numbers we do not take and 1 as the numbers we take
assume that for achieving sum = k: our take not take looks something like this
0 0 1 0 1 1 0 1 0 0 0
now this subsequence has sum=k, and this subsequence will be the subarray for all combinations of take — not take of 0s before first occurrence of 1 and after that last occurrence of 1
so this subsequence will act as subarray for 2^5=(32) subsequence
we can easily handle this using dp[1001][1001][2]
the last state determines whether we have selected our first 1 or not
dp states->
f(0,0,0)->we are at index 0 and until now our sum=0 and we have not selected our first 1
dp transition ->
f(i,s,0)=f(i+1,s+a[i],1)+2*f(i+1,s,0)
f(i,s,1)=f(i+1,s+a[i],1)+f(i+1,s,1)
base case ->
if before all the elements are exhausted we achieve sum=k, return 2^(rem elements)
otherwise return 0
i really think this should work
It won't work ... due wrong transitions, check my comment below on why it's wrong.
I feel like the below solution is an optimized solution for this. It uses O(n) space for dp.
I have a dp solution to it, i saw many dp solutions but some of them seemed wrong, actually this question can be done in O(n*n*k) time complexity and can be optimised further using prefix sum to O(n*k) :-
DP States-> i X j X flag ---> till index i, sum of score of all subsequences with k=j, flag= 0/1
dp[i][j][1] means that ending at index i, sum of score of all subsequences with k=j such that element at ith index is included in the sum .
so it's transition can be :- dp[i][j][1] += dp[h][j-a[i]][1] , such that 0 <= h < i ( Now optimise that using prefix sum )
dp[i][j][0] means that ending at index i, sum of score of all subsequences with k=j such that element at ith index is not included in the sum. But it can or can not be included in the subsequence. In both the cases whether it's included or not included in subsequence it's value is going to be the same dp[i-1][j][0] + dp[i-1][j][1].
Add that 2 times because of the dual possibilities of including or not including the subsequence
Here is my C++ implementation