CHEFCODE - Editorial

editorial
, , ,
21

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. :slight_smile:

22

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

solved using dp and recursion :slight_smile:
can anyone explain the log and oc trimming solutions plz ā€¦thanks n advance :slight_smile:

23

please upvote meā€¦ I have to ask a question

24

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

25

@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

26

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

27

Where is setterā€™s solution ?

28

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

29

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

30

I think editorialist should comment his code for better understanding.

31

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.

32

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!

33

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

34

#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 ?

35

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

36

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

1 Like
37

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

38

You should try again

39

Now it gives different result, very weird shouldnā€™t have happened

40

can you please explain your 2nd approach ?