Sort 7 Discussions, By:
Please Login in order to post a comment
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.
I implement a func f(A,B)(k, threshold) which calculate the smallest sum of k people's appeti. by maintaining min-heap of size k, and binary search from 1 to N
Is there a better solution than O(n*log(n)^2) (n is the number of friends)?
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...
Looking at the input constraint, it is unlikely a 0-1 Knapsack problem which is NP-complete (no known polynomial time algorithm exists)...
Has anyone solved this problem in F#?
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.
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.
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?
Yes. He can bring any subset of friends. There's no dependancy on whom to bring first.
I want to code in c++ but it is not available
No more comments