CHEFCODE - Editorial

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

@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

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

@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

Got AC by using Log and DP :slight_smile:

code

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

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

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

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

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 .

I need editorial for long sandwich question please post asap

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:

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:

please upvote me… I have to ask a question

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

@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