You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFCODE - Editorial

6
5

Problem Link

Practice

Contest

Author: Prateek

Tester: Pawel Kacprzak and Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

MEDIUM

Prerequisites

Product Trick, Meet-in-Middle

Problem

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. 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]}$. 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

This question is marked "community wiki".

asked 18 May, 13:48

likecs's gravatar image

6★likecs
2.9k427
accept rate: 9%

edited 18 May, 22:43


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

link

answered 18 May, 16:24

ssaxena36's gravatar image

5★ssaxena36
7315
accept rate: 26%

edited 19 May, 19:47

I need editorial for GPD, want to know how to solve GPD.

link

answered 18 May, 15:23

prakhariitd's gravatar image

6★prakhariitd
1.1k19
accept rate: 10%

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

  1. with sorting https://www.codechef.com/viewsolution/13630408
  2. without sorting https://www.codechef.com/viewsolution/13630386
link

answered 18 May, 18:42

vinayak_1's gravatar image

4★vinayak_1
191
accept rate: 0%

It can be also solved with dp approach (with map)

Code

link

answered 18 May, 17:21

hafiz_00's gravatar image

6★hafiz_00
11
accept rate: 0%

Will you please explain your approach? @hafiz_00

(27 May, 09:06) siddharthp5384★

A simple brute force recursion (along with concept of log and O.C. of 'trimming') gave me an A.C :D

My code

link

answered 18 May, 17:41

vijju123's gravatar image

4★vijju123
7.4k212
accept rate: 17%

Please add the tag "may17" in all the editorials. It will be easier to find all the editorials at once. Also, someone please upvote me so I can gain commenting privileges.

link

answered 18 May, 19:17

gatecse2018's gravatar image

2★gatecse2018
111
accept rate: 0%

edited 18 May, 19:19

1

Commenting privilege is 50 karma. You should try to earn it yourself instead of asking for free upvotes...

(18 May, 19:32) vijju1234★

@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 count-1,that is don't count empty subset this will allow you to fetch 30 points only. Hope this helps!

link

answered 18 May, 19:57

yash_22's gravatar image

4★yash_22
213
accept rate: 0%

edited 18 May, 19:59

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

link

answered 18 May, 16:07

sujoy3kb's gravatar image

4★sujoy3kb
111
accept rate: 0%

edited 18 May, 19:12

can anyone please tell what is wrong in my code https://www.codechef.com/viewsolution/13580088 it is giving WA in two test cases

link

answered 18 May, 16:15

ayush201's gravatar image

3★ayush201
61
accept rate: 0%

and got AC in this https://www.codechef.com/viewsolution/13580236 just a language change but logic is same

(18 May, 16:23) ayush2013★

Can anyone tell me what's wrong with this solution, https://www.codechef.com/viewsolution/13538559 .I didn't get even 30pts for this.I have done the same as the subtask 1 of this editorial.

link

answered 18 May, 17:39

shivank01's gravatar image

2★shivank01
1
accept rate: 0%

See the caveats section in the editorial, you are not handling overflow issues.

(18 May, 23:29) likecs6★

can anybody explain how duplicates are handled in 2nd approach ?

link

answered 18 May, 21:06

saurav9's gravatar image

3★saurav9
1
accept rate: 0%

@admin I guess there's a problem .

SHORT-

Same code shows accepted during the contest but now in the practice arena it shows TLE.

LONG-

I submitted my solution during the contest . Got AC answers in subtask #1 (30 points) and in subtask #2 , all tasks were AC except two tasks numbered 1,8. But now when i submit the same solution (code) in the practice arena ... mentioned in this post . I get a TLE for each and every task . Do u consider this as a problem on ur part ?

LINKS-

my solution during contest- https://www.codechef.com/viewsolution/13621620

same solution after the contest(in practice arena) - https://www.codechef.com/viewsolution/13631281

link

answered 18 May, 21:54

rohan_bose95's gravatar image

4★rohan_bose95
422
accept rate: 0%

You should try again

(18 May, 23:40) prakhariitd6★

Now it gives different result, very weird shouldn't have happened

(18 May, 23:53) prakhariitd6★

Got AC by using Log and DP :)

code

link

answered 18 May, 22:29

divyansh_gaba7's gravatar image

4★divyansh_gaba7
75818
accept rate: 24%

Pseudo code for Subtask 1 will give you a TLE if you don't perform a raincheck i.e. a[i]<K.

link

answered 18 May, 23:27

dusht0814's gravatar image

4★dusht0814
1945
accept rate: 14%

Why can't we use dp for this problem? I have done using dp. Can someone tell me if it is a correct approach?

My code

link

answered 19 May, 16:22

pro_coder123's gravatar image

4★pro_coder123
211
accept rate: 0%

can anyone tell me what is the wrong with this solution,https://www.codechef.com/viewsolution/13635976 .i do same as the editorials solution 1.

link

answered 19 May, 19:00

manaranjanfav's gravatar image

3★manaranjanfav
1
accept rate: 0%

in the editorial it is said that we can sort the array and remove dublcates....after removing dublicates how will we handle the answer..

link

answered 19 May, 19:49

sidd845's gravatar image

4★sidd845
153
accept rate: 0%

I got all testcases accepted in 0.06 sec but got TLE for task 8. Can anyone tell whats wrong with my code? https://www.codechef.com/viewsolution/13542837 .

link

answered 19 May, 19:54

vivekj52's gravatar image

3★vivekj52
1
accept rate: 0%

I need editorial for long sandwich question please post asap

link

answered 19 May, 20:07

hruday968's gravatar image

4★hruday968
1.4k8
accept rate: 12%

https://www.codechef.com/viewsolution/13636503 Can somebody point out the mistake in my code, am getting WA in 2 subtasks. I followed the steps told in solution1. Thanks in advance. :)

link

answered 19 May, 20:16

shrikantbadri's gravatar image

3★shrikantbadri
714
accept rate: 20%

https://www.codechef.com/viewsolution/13636745

solved using dp and recursion :) can anyone explain the log and oc trimming solutions plz ...thanks n advance :)

link

answered 19 May, 20:32

sidd845's gravatar image

4★sidd845
153
accept rate: 0%

please upvote me.. I have to ask a question

link

answered 19 May, 21:27

mir_sabbir's gravatar image

5★mir_sabbir
1
accept rate: 0%

Regarding the 2nd subtask, after splitting, is it necessary to apply binary search? If yes, then why?

link

answered 20 May, 11:37

swamicoder's gravatar image

3★swamicoder
1737
accept rate: 12%

@shivank01 here is your AC code for the first subtask,https://www.codechef.com/viewsolution/13639615 . For the second subtask you can view my code involving meet in the middle algorithm, https://www.codechef.com/viewsolution/13639438

link

answered 20 May, 11:52

shadow10's gravatar image

4★shadow10
11
accept rate: 0%

edited 20 May, 11:56

can you please explain your 2nd approach ?

(20 May, 14:07) acodebreaker23★
link

answered 20 May, 12:21

pk1302's gravatar image

3★pk1302
11
accept rate: 0%

edited 20 May, 12:22

Where is setter's solution ?

link

answered 20 May, 13:57

acodebreaker2's gravatar image

3★acodebreaker2
1.2k10
accept rate: 19%

For large dataset, i sorted the array.For each subset, i started with largest number to check whether the product is greater than k. Every number has a bit position between 1<=pos<=30 Whenever we get any number which makes the product greater than k,we can increment the counter to the point where that bit position changes from 1 to 0. By this approach i got all test cases accepted in 0.05 sec except test case #8. Can anyone figure it out what's the issue with it? https://www.codechef.com/viewsolution/13542837

link

answered 21 May, 12:40

vivekj52's gravatar image

3★vivekj52
1
accept rate: 0%

Can anyone tell me what is wrong with the following code. I have tried several things and always same cases are giving wrong answer.

https://www.codechef.com/viewsolution/13779472

link

answered 25 May, 00:28

shashank1209's gravatar image

4★shashank1209
1
accept rate: 0%

I think editorialist should comment his code for better understanding.

link

answered 25 May, 20:10

aadeshrathore's gravatar image

3★aadeshrathore
111
accept rate: 0%

https://www.codechef.com/viewsolution/13791336

this is passing subtask 1 but not the subtask 2 though I have used meet in the middle algorithm. Can somebody please pointout problem in my code.

link

answered 26 May, 19:31

jack0897's gravatar image

2★jack0897
1
accept rate: 0%

I am getting a TLE in test case 8. I have used simple backtracking by calculating products and checking if the product exceeds K and also considering overflows.

Please correct me if I am wrong but I feel complexity remains the same if we log the array elements and consider the sum of number to be less than K. So why is that solution running under time? Doesn't multiplication and addition take same time on modern processors?

Here's my solution: https://www.codechef.com/viewsolution/13579609

Thanks!

link

answered 26 May, 22:13

manjrekarom29's gravatar image

3★manjrekarom29
212
accept rate: 0%

I implemented the solution 1 of subtask 2 still I'm getting WA in some test cases of subtask 2(subtask 1 works fine) If anyone could look for mistakes...help appreciated.

Here is my solution:

https://www.codechef.com/viewsolution/13883437

link

answered 29 May, 03:04

savage_coder's gravatar image

3★savage_coder
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×10,863
×890
×164
×9

question asked: 18 May, 13:48

question was seen: 3,286 times

last updated: 29 May, 03:04