Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### wish_me's blog

By wish_me, history, 4 years ago, Given a non negative array, find the number of subsequences having product smaller than K.

k<10^2 arr.size<10^3

Examples:

Input : [1, 2, 3, 4]

k = 10

Output :11

The subsequences are {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}

Input : [4, 8, 7, 2]

k = 50

Output : 9 Comments (18)
 » I think the brute-force solution may work. Any judge to submit?
•  » » If the size is more then what to do other than brute-force?
•  » » » I don't know about the exact time complexity of brute-force solution but the solution mentioned by -Morass- is correct and works in O(n*k).
 » Here, since input size is less than or equal to 1000, we can just consider all the subsequences and find the product of each of them. For example, we fix a left point on the array, and for that keep extending the right endpoint, unless we exceed K. The number of times we can shift the right endpoint is the number of possible right endpoints if the left endpoint is fixed at the index where we had initially done. Now, just iterate over all possible left endpoints. complexity: o(n^2).A better solution would be to use a 2 pointer type algorithm. Here, observe that if we already have a subsegment whose product exceeds K, then if we multiply more elements, it will still always exceed K. Thus, we need to divide some previous elements first. So to do this, start the left and right endpoints at 0. Then keep moving the right endpoint and keep multiplying the new elements. Each time you are able to do so without exceeding K, increase ctr. Now, if the product exceeds K, then start shifting the left endpoint and divide the product that you had, with the element the left endpoint is processing, until the product again becomes lesser than K. Now, again start shifting the right endpoint and increasing ctr as before. complexity: o(n) [since the right endpoint shifts at most n times and so does the left.]
•  » »
•  » » » ohkk.. then let me edit it. sorry, my bad.
 » Good day to you,Well, since the K is pretty low, the easiest approach might (imho) be 2D Dynamic Programming, where first dimension is index of array and second is product. In each DP-state you either try to "multiply" by current number or simply go to next-number.In recursive form, it might look like: dyn (I k) if I == N: return 1 if k >= K: return 0 return dyn(I+1,k)+dyn(I+1,k*A[I]) I guess some memorisation + some modulo (etc.. sauce) will be necessary, yet I'm sure you'll deal with it.Good Luck & Have Nice Day!
•  » » *memoization
•  » » » Right, thank you ^_^
•  » » can we do it by bottom up approach?
•  » » » 4 years ago, # ^ | ← Rev. 3 →   For iterative approach, simply "reverse" what you are asking for:so instead of dyn(I+1,k)+dyn(I+1,k*A[I]) you will iterate from back and ask for dp[I+1][k]+dp[I+1][k*A[I]] which is (as you can see) almost the same.The "ifs" ending the recursion can be done either by "pre-filling" of the table, yet in case of "multiplication" a would rather recommend to do them by ifs again.so basicaly it is same, yet instead if recursion, there is: for I (N → 1) for k (K → 1) dp[I+1][k]+dp[I+1][k*A[I]] 
•  » » 8 months ago, # ^ | ← Rev. 3 →   I think you must check k>=K before I==N. Am I correct?
 » 3 years ago, # | ← Rev. 2 →   Let z be the number of zeros in the array and n be the total number of elements. There are (2z - 1)·2n - z subsequences with product 0. Remove all zeros now and operate on the remaining array.We do something similar to what -Morass- described. Let small(i, j) denote the number of subsequences of the first i elements with product at most j. It's a simple DP, but we do this only for . Likewise, define large(i, j) such that the product is required to be at most . Again, we do this for .It's easy to deduce the following formulas now:  The final answer large(n, 1) is obtained in time.I tried to implement this: Code. Just tested on your samples and only for small answers (no modulo).
 » its just a variation of normal knapsack. each cell will have value equals :for(int i = 1 ;i<=k ;i++) for(int j = 1 ; j <=n ;j++){ if(arr[i-1] < j){ dp[i][j] = dp[i-1][j/arr[i-1]] + dp[i-1][j] + 1; } else dp[i][j] = dp[i-1][j]; } where i represents the arr of numbers and j represents the product.the final answer will be dp[k][n];
•  » » why did you did dp[i-1][j/arr[i-1]] — i didn't understand he column part i.e. [j/arr[i-1]]
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   Like in a knapsack, when we include an item we substract the item's amount from j and check the state for when that item was not included and the amount was amount — item's amount . I think its not making much sense bit you could look at the code.This is the 0/1 knapsack main for loop code for(int i=1;i
•  » » Yes, I agree. int countSubsequences(vector < int > & arr, int n, int p) { // Write your code here. int DP[n+1][p+1]; if(n==0) return 0; for(int j=0;j
 » // Put your super code here #include using namespace std; using ll = long long; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int n, k; cin>>n>>k; vector v(n+1); for(int i=1; i<=n; ++i) cin>>v[i]; vector> dp(n+1, vector(k, 0)); // dp[i][p] = number of subsequence ending at ith element of v and having product p int ans = 0; for(int i=1; i<=n; ++i){ for(int p=1; p