Test by shivam

Problem Link

Practice

Contest

Author: Prateek

Tester: Pawel Kacprzak and Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

MEDIUM

Prerequisites

Product Trick, Meet-in-Middle

Problem

Click to view

You 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 Explanation

Calculate all possible subsets product for 2 halves of the array. Apply meet in the middle to find the overall answer.

Explanation

First 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.


//Assuming 0-based indexing
n = size(a)
up = 1 << n
for i in 0 to (up-1):
	prod = 1
	for j in 0 to (n-1):
		if (i & (1 << j)):
			//element j is present in given subset/subsequence
			prod *= a[j]
	if (prod <= K):
		ans += 1


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.

Click to view

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 pre-calculation 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]}.

Click to view

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 sub-problems 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 :

  1. If the product at any moment of time exceed $K$, just stop the recursion at that level. Using the above argument, we can see that the maximum depth of any recursive procedure will be $20$ only.
  2. Sort the numbers in reverse order and remove the duplicates. As larger numbers will get multiplied in initial stages of recursion, earlier we will get to the product exceeding $K$ and thus greatly reducing the recursion depth.
  3. Maintain prefix product in reverse manner. This will help us to evaluate the answer in $O(1)$ if it is possible at any moment of time and stop the useless recursion as well. This can be done if at any moment of time we know that $X * Y <= K$, where $X = $ current product and $Y = $ product of remaining numbers to be seen.

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 :

 
INF = 2e18
bool safe_mul(a, b):
	if (a <= (INF+b-1)/b) return true
	return false

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

Setter’s solution

Tester’s solution

Editorialist solution - 1

Editorialist solution - 2

Test

Sr. No. Team Name Member 1 Member 2
1 acrush_tc ACRush
2 singleminded Carsten Eilks
3 dreamoon_shik Huang I-Wen Ting Wei Chen
4 ssu_tglsu Maxim Finyutin Dan Sagunov
5 team_sua Lin, Xi Sebastian King
6 namekata Koichi Namekata autumn_eel
7 mclg Mark Chen Lewin Gan
8 dragoon_nfssdq Md. Nafis Sadique Md Mahbubul Hasan
9 pavelteam Pavel Zeman -
10 simplicissimus xuyinzhan sevenkplus
Abstracts Due Sep 10, 2017
Full Papers Submission Sep 17, 2017
Notification of Acceptance Nov 25, 2017
Camera Ready Copy Due Dec 15, 2017
Sr. No. Team Name Member 1 Member 2
1 [acrush_tc][1] [Tiancheng Lou][2] -
2 [singleminded][3] [Carsten Eilks][4] -
3 [dreamoon_shik][5] [Huang I-Wen][6] [Ting Wei Chen][7]
4 [ssu_tglsu][8] [Maxim Finyutin][9] [Dan Sagunov][10]
5 [team_sua][11] [Lin, Xi][12] [Sebastian King][13]
6 [namekata][14] [Koichi Namekata][15] [autumn_eel][16]
7 [mclg][17] [Mark Chen][18] [Lewin Gan][19]
8 [dragoon_nfssdq][20] [Md. Nafis Sadique][21] [Md Mahbubul Hasan][22]
9 [pavelteam][23] [Pavel Zeman][24] -
10 [simplicissimus][25] [xuyinzhan][26] [sevenkplus][27]
//