Problem LinkAuthor: Prateek Tester: Pawel Kacprzak and Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyMEDIUM PrerequisitesProduct Trick, MeetinMiddle ProblemYou are given an array $A$. You are required to find the number of subsequences of $A$ such that product of the elements of the subsequence is less than or equal to $K$. Quick ExplanationCalculate all possible subsets product for 2 halves of the array. Apply meet in the middle to find the overall answer. ExplanationFirst of all we count the number of subsequences of any array of size $n$. For every element there are 2 choices, either consider that element into the subsequence or not. Thus the total number of subsequence is $2^n$. This also includes 2 trival case, the empty subsequence where all the elements are considered and the full subsequence, where all the elements are considered. Subtask 1 This subtask can be easily solved using brute force by iterating over all the subsets and checking whether their product of elements is less than or equal to $O(K)$ or not. This will take complexity $O(n * 2^n)$ which is too slow for larger subtask. Below is the pseudo code for iterating over all subsets and getting the elemnts present in each element.
Subtask 2 Solution 1 Before reading the solution outlined below, I request you to go throught this editorial on Meet in the middle. After going throught the first example in the above link, we can get some idea, how we are going to approach this question. We simply find the product of all possible subsets after diviing the array into 2 parts. Since each part be of maximum size $15$, the above procedure will be feasible. The complexity of this precalculation takes $O(2 * (n/2) * 2^{n/2}) = O(n * 2^{n/2})$, which would easily fit into our time limit. Now, we simply sort the above 2 arrays. Let us call these arrays, $B$ and $C$. Then, consider all the elemts of $B$ one by one and check how many elements of $C$ can give product less than or equal to $K$, with the given element. The sum over all the elements is the required answer. For finding the number of elements in $C$, we can use binary search to find out how many number are less than $\frac{K}{B[i]}$. This is because we want $B[i] * x <= K$, i.e. $x \leq \frac{K}{B[i]}$, where $x \in C$ Solution 2 This solution is specific for this problem only. Here we will use the fact that product of 20 distinct numbers will always exceed ${10}^{18}$ as the smallest product of 20 distinct numbers is $factorial(20) \approx 2.43 * {10}^{18}$. So, we simply do a recursive procedure and try to solve the problem. Here at each step of the recursion, we have 2 choices i.e. either to include the object into the subsequence or not. Doing it naively will give the same result as brute force and give time limit exceeded. Also, there are almost no overlapping subproblems as well, so dynamic programming cannot be applied. So, we basically cut down the recursion depth and make it work almost as fast as the above solution, (sometime even faster than the above solution) using the following tricks :
The above recursive solution can be found in the Editorialist 2nd solution. Caveats All the above algorithms will work correctly, just that there can be issues with overflows, due to the constraints on the numbers in the question. For example, multiplying 2 number as large as ${10}^{10}$ will easily result in overflow in most languages, if not using big integer arithmetic support. The editorialist has used big integer library support in python in order to avoid any issues but the same can be handled in C, C++, Java etc using the below function :
Thus the product of 2 numbers should be taken only when it is safe to multiply them else it can be concluded that the product will exceed $K$ (maximum value of $K$ in the problem is given as ${10}^{18}$). Time Complexity$O(n * 2^{n/2})$ Solution Links
This question is marked "community wiki".
asked 18 May '17, 13:48

Simple recursion can solve this problem. Reducing array values into Log(Value) will cause the problem to change from Product Subsequence to Sum subsequence to prevent long overflow and reducing heavy multiplication. Counting number of ones and Simple Recursion without ONES with optimized Breaking from recursion does the trick. Final answer can be calculated by using Simple Combination Logics which you can see here Java 0.09s: AC Code Link answered 18 May '17, 16:24

I need editorial for GPD, want to know how to solve GPD. answered 18 May '17, 15:23

I solved the problem with method explained in subtask2 solution1 ie Meet in the Middle . It gave the correct answer only when i sort the input array but i am unable to find out why we need to sort input array ? Can someone please explain this . Here is my solution
answered 18 May '17, 18:42

@shivank01 as Ai is too large 10^18 and you are taking product of a whole subset eventually you would exceed the limit lets say there are 10 elements of 10^18 s the product would be 10^180 then integer overflow happens you should have just use the condition if your product>=k at any point break else if you move to the end of loop successfully just increase the count, and ans will be count1,that is don't count empty subset this will allow you to fetch 30 points only. Hope this helps! answered 18 May '17, 19:57

@prakhariitd Its just a direct application of HLD and persistent tries. Only trick is that not every one knows about these data structures :P answered 18 May '17, 15:26
You don't even need HLD for the problem. Persistent tries are enough.
(18 May '17, 15:37)
May be. But I used it. I didn't know either HLD or Persistent Tries. But ended up learning both. So, no regrets :)
(18 May '17, 15:43)

Can anyone tell me what's wrong with my code? It's giving wa in 8th test case.. https://ideone.com/XMBnDr answered 18 May '17, 15:58

Can anyone tell me what's wrong with my code? It's giving wa in 8th test case.. https://ideone.com/XMBnDr https://www.codechef.com/viewsolution/13629225 answered 18 May '17, 16:07
