CHEFCODE - Editorial

@shivank01 here is your AC code for the first subtask,CodeChef: Practical coding for everyone . For the second subtask you can view my code involving meet in the middle algorithm, CodeChef: Practical coding for everyone

https://www.codechef.com/viewsolution/13639790
The correct soln of @manaranjanfav.

Where is setter’s solution ?

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

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

I think editorialist should comment his code for better understanding.

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.

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: CodeChef: Practical coding for everyone

Thanks!

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

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k;cin>>n>>k;int a[n],ans=0;
for(int i=0;i<n;i++)cin>>a[i];
int up=1<<n;
for(int i=0;i<=up-1;i++)
{
int pro=1;
for(int j=0;j<=n-1;j++)
{
if(i&(1<<j))pro*=a[j];
}
if(pro<=k)ans++;
}cout<<ans<<endl;
}

Giving wrong answer ?

and got AC in this CodeChef: Practical coding for everyone
just a language change but logic is same

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

1 Like

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

You should try again

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

can you please explain your 2nd approach ?

Will you please explain your approach? @hafiz_00

Isn’t this brute-force for languages supporting big-int ?
By the way got wa on my answer here. Any help on the same would be appriciated. :smiley:

pr[j]/pr[i-1] is an issue here.
Try print(1/2) and see the output.

Maybe yes if you are talking about soln other than meet-in-the-middle.
You can do it in c++ as well. CC’s c++ supports __int128. ;p

Edit - Your soln is also wrong. You read question wrong.

1 Like

Wow. Thanks, I didn’t know that.

Yeah, I see the difference between subsequence, and subsegment.
Thanks for the answer.