CHEFCODE - Editorial

editorial
, , ,
2

I need editorial for GPD, want to know how to solve GPD.

2 Likes
3

Can anyone tell me what’s wrong with my code?
It’s giving wa in 8th test case…

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

4

can anyone please tell what is wrong in my code
https://www.codechef.com/viewsolution/13580088
it is giving WA in two test cases

5

Simple recursion can solve this problem. Reducing array values into Log(Value) will cause the problem to change from Product Subsequence to Sum subsequence to prevent long overflow and reducing heavy multiplication. Counting number of ones and Simple Recursion without ONES with optimized Breaking from recursion does the trick. Final answer can be calculated by using Simple Combination Logics which you can see here Java 0.09s: AC Code Link

5 Likes
6

It can be also solved with dp approach (with map)


[1]


  [1]: https://www.codechef.com/viewsolution/13443776
1 Like
7

Can anyone tell me what’s wrong with this solution, CodeChef: Practical coding for everyone .I didn’t get even 30pts for this.I have done the same as the subtask 1 of this 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: