skpro19's blog

Doubt in Codechef long MARRAYS
By skpro19, history, 7 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

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

Please explain your approach.

→ Reply
  • »
    »
    7 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.

    → Reply
»
7 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.

→ Reply
  • »
    »
    7 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?

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

    Can you prove your greedy approach?

    → Reply