Q : Given N containers, each container has balls of different colors, and each color can have multiple quantity in a single container. We need to select A quantity of color C1 , B quantity of color C2, C quantity of color C3 etc.
Penalty is equal to sum of all leftover quantity in a container if something is picked from container, else 0. We need to minimise the penalty and find set of containers which can help acheive minimum penalty.
Example
container 1 — [ (c1, 100), (c2, 100), (c3, 50) ] container 2 — [ (c1, 50), (c2, 50), (c3, 50) ] container 3 — [ (c1, 50), (c2, 50), (c3, 80) ]
we need to pick (c1, 100), (c2, 100)
If we select container 1 -> penalty = 50
If we select container (2,3) -> penalty = (50+80) = 130
So answer would be 50 and set of boxes would be [Container 1]
Constraints :
Container Count <= 100, Color Count <= 1000, Max quantity of each color <= 500
Time Limit : 60 seconds
tough question
Is 60sec the time limit for one test ? If that's the case I guess the intended solution is backtracking?
could you please share some insight? the dp states?
Might be wrong but I want to give it a go.
Let-
$$$- m =$$$ the number of diff. colours.
$$$- n =$$$ the number of containers.
Let $$$dp[i][c_1][c_2][c_3]...[c_m] =$$$ $$$c_j$$$ of $$$j^{th}$$$ colour remaining to chose from boxes numbered $$$i$$$ to $$$n - 1$$$.
We need to return the state $$$dp[0][C_1][C_2][C_3]...[C_M]$$$
Making an $$$m$$$ dimensional $$$dp$$$ state is kinda.. whacky as, we don't know $$$m$$$ changes from (question to question).
I was thinking of creating a 2D DP state $$$dp[i][j]$$$ where $$$j$$$ some kind of a hash for $$$c_1, c_2, c_3, ..., c_m$$$
Claim: If you choose to pick from a box $$$i$$$, exhaust it as much as possible, as partially choosing from some colour $$$c_j$$$ from $$$i$$$ and further boxes would not decrease the penalty in any way.
Now the state becomes
include:
dp[i][c_1][c_2][c_3] = min(dp[i][c_1][c_2][c_3], dp[i + 1][c_1'][c_2'][c_3'] + penalty);exclude:
dp[i][c_1][c_2][c_3] = min(dp[i][c_1][c_2][c_3], dp[i + 1][c_1][c_2][c_3]);Now, regarding hashing for $$$c_1, c_2, c_3, ... c_m$$$.
Cosider $$$dp[i][3][1][0][4]$$$.
4 different colours, I can represent them as a string as $$$"aaabdddd"$$$ (no $$$c$$$)
I can then hash it to some unique value $$$hashval$$$ and represent it as $$$dp[i][hashval]$$$.
Since $$$1 ≤ m ≤ 1000$$$ we should represent them in a vector of numbers, like
{1,1,1,2,4,4,4,4}and hash it.Any corrections/suggestions welcome!
And now calculate the number of states you have in this dp. (It's a big number)
I'm almost certain that this is NP-hard, and not in the way where DP actually helps you.
I'm guessing that the answer they are looking for is a brute force that returns early if you already know the current set of containers cannot be part of an optimal solution. (Which might in theory be too slow, but might always be fast enough in practice.)
Probably the fastest solution is linear programming, but I'm not sure that LP solver can be written from scratch on interview.
How would you guarantee that the LP has integer BFS? I think that's a separate proof to be made, also looking at the time limit and the problem itself, this looks like it is NP hard, currently am trying to find a reduction to bin-packing, if it is NP hard, that would automatically imply the LP cannot have integer BFS, in which case the LP solution definitely would be fractional. So at best we could have an approximate solution in polynomial time using LPs.
What do you think?
I think that in LP form there could be some good heuristics, not relying on "normal" LP methods. Most probably this problem is NP-hard, and imho constraints are too high for deterministic precise solution
Why did we not pick (c1, 100), (c2, 100), or (c3, 50), and the penalty would be just 0?