When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

skpro19's blog

By skpro19, history, 6 years ago, In English

This is the problem link. This is my submission. It is getting TLE. I read another guy's recursive approach. It got full points. I don't understand, why this code is getting accepted, but mine is not.

Any help would be really appreciated.

Peace.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please explain your approach.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dfs(level, pos) returns the maximum value possible from that level, if we use the element at 'pos' as the last element of the level.

»
6 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

You should no use recursive approach. This question can be solved in O(m1+m2+m3+....) where mi is the number of ingredients in the ith dish, you can see my code https://www.codechef.com/viewsolution/15833805 I used the logic that only maximum or minimum number in the previous dish will cause the highest quality hence check which one should be used it's kind of greedy approach.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But, the solution I mentioned above has solved it using recursive approach using DP. Can someone explain that?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you prove your greedy approach?