- Practice
- Functional Programming
- Ad Hoc
- Mangoes
- Discussions

# Mangoes

# Mangoes

zofy11 + 0 comments Hey guys, could anyone give me some hints how to approach this, I submitted 2 approaches using Scala and both timeouted from fifth test-case.

I tried iterating through combinations but it did not work.

Any help?

Thanks

pabiagioli + 1 comment Did anyone solve this problem with OCaml? This problem is similar to the Knapsack Algorithm, but I don't know why I'm getting 9 Test Cases with timeout... Usually OCaml timeouts are due to String manipulation, but here are all integers... Any pointers?

ltchen + 0 comments Looking at the input constraint, it is unlikely a 0-1 Knapsack problem which is NP-complete (no known polynomial time algorithm exists)...

lizzael_v_c + 0 comments Has anyone solved this problem in F#?

pbanavara + 1 comment Have a question folks. I have solved this in a FP approach with immutable data structures. However, TC #5 onwards am hitting an OOM error.

My algo is very simple - use the scala set.subsets method to generate combinations of (1 to numberOfFriends) and then apply the given formula for each of these subsets, get the max of the applied formula.

The timeout is because the subsets and the further computation takes into account all the combinations. For ex: If a subset of length 3 achieves the maximum possible number of mangoes, the computation should stop there and not go ahead with subsets of lengths > 3. This is not the case here. What I'm trying to find out is how to do this without using a loop or in a pure functional approach. Can someone provide any clues ? I can message my Scala code if needed.

fmeeuw + 0 comments For stopping early, you can use a recursive function, that stops when the max number of mangoes is reached. I also made the solution in scala and ran into the timeouts as well. Unfortunately this will not solve your timeouts.

I made two improvements in the calculation to get rid of the timeouts. I can give some hints: 1. It is not strictly neccesarry to consider all combinations 2. You don't necessarily have to start with 1 invitation first.

Good luck!

pranshu211 + 1 comment Can we choose which friends to bring? Or do we have to bring all friends till the i'th position to bring the i'th friend?

abhiranjan + 1 comment Yes. He can bring any subset of friends. There's no dependancy on whom to bring first.

pranshu211 + 0 comments Okay. Thanks!

[deleted] + 0 comments I want to code in c++ but it is not available

List Item

No more comments

Sort 7 Discussions, By:

Please Login in order to post a comment