CHEFCODE - Editorial

editorial
, , ,
8

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

My code

2 Likes
9

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
    CodeChef: Practical coding for everyone
  2. without sorting
    CodeChef: Practical coding for everyone
2 Likes
10

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.

1 Like
11

@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!

1 Like
12

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

13

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

same solution after the contest(in practice arena) - CodeChef: Practical coding for everyone

14

Got AC by using Log and DP :slight_smile:

code

15

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

16

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

17

can anyone tell me what is the wrong with this solution,CodeChef: Practical coding for everyone .i do same as the editorials solution 1.

18

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

19

I got all testcases accepted in 0.06 sec but got TLE for task 8. Can anyone tell whats wrong with my code? CodeChef: Practical coding for everyone .

20

I need editorial for long sandwich question please post asap

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 ?