### Nilesh_'s blog

By Nilesh_, 4 weeks ago,

The special value of sequence of integers is defined as the number of non empty subsequences where the sum of elements is equal to k. Given an array arr of n integers and an integer k. Find the sum of special values of all non empty subsequences of arr. Since the sum can be large. Report it modulo 1e9 + 7.

Constraints:

1 <= N <= 2000

1 <= arr[i] <= 1e9

1 <= k <= 2e12

Example: n = 4, k = 3, arr = [3, 1, 4] ans is 6.

ans = 2(contribution of sequence [1, 4]) + 4(contribution of [4]) = 6

Kindly help me with the above probelm, Thanks. I tried forming dp state based on unique values and for each possible subsequence where sum equals target, 2^(n — currentElementsCount) will be its contribution to ans. However couldn't arrive at a proper solution.

•  » » 4 weeks ago, # ^ |   0 This was from an online test conducted by a company.There was a slight mistake in the title, which has been corrected. The problem statement is exactly the same as the original problem from the test. The constraint for n is accurate, but I assumed the ranges for arr[i] and k.
 » 4 weeks ago, # | ← Rev. 5 →   0 //////////////////Keep calm and code on//////////////////// #include using namespace std; #define pb push_back using ll= long long; #define f(i,n) for(int i=0;i vi; typedef vector vll; typedef vector vvi; typedef vector vvll; typedef pair pii; typedef vector> vpii; typedef unordered_map umap_ii; typedef unordered_map umap_ll; typedef unordered_map umap_si; int dp[2002][2002]; int fun(int n,vi& arr,int count,int ind){ if(ind==n)return 0; if(dp[ind][count]!=-1)return dp[ind][count]; int sum=0; if(n-ind-10)sum+=fun(n,arr,count-1,ind+1)+arr[ind]; return dp[ind][count]=sum; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n,k; cin>>n>>k; vectorarr; int ans=0; memset(dp,-1,sizeof(dp)); for(int i=0;i>a; arr.pb(a); } int sum=0; for(int i=1;i<=n;i++){ int x=fun(n,arr,i,0); if(x==k){ sum+=pow(2,n-i);// as other element have choice to be in the subsequence (yes:No) } } cout << sum << endl; // return 0; } will this o(n^3) or o(n^2)
•  » » 4 weeks ago, # ^ |   0 I found this code lis in o(n*log n) set s; set::iterator it; for(int i=0;i
•  » » » » 4 weeks ago, # ^ |   0  set s; vector lis; for(int i = 0; i < n; i++) { auto it = s.lower_bound(arr[i]); if(it != s.end()) s.erase(it); s.insert(arr[i]); } int sum_lis = 0; for(int x : s) sum_lis += x; cout << sum_lis << "\n";