CHEFCODE - Editorial

editorial
, , ,
21

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

22

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.

23

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

24

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 .

25

I need editorial for long sandwich question please post asap

26

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:

27

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:

28

please upvote me… I have to ask a question

29

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

30

@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

31

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

32

Where is setter’s solution ?

33

can you please explain your 2nd approach ?

34

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

35

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

36

I think editorialist should comment his code for better understanding.

37

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.

38

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!

39

Will you please explain your approach? @hafiz_00

40

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