The problem is similar to asking, you have 2 boxes each having capacity of **W**(<10000). And you have given a list of item of some capacity **c**( 100 <= c <= 3000). List can contain at max **n** (<= 200) items. Now you have to access the list in FIFO order and put those items in any of the two boxes until addition of item overflow each of the boxes. Note: You can not skip any item during processing, if it does not fit stop the process.

I did O(Wn) for each test case. My java solution run in 2 sec approx.

Is there any better solution than this? I thought of greedy but instantly got counter case.

I got 0.095s with recursive DP.

The memo array has two parameters: number of loaded cars and max(sum(car lengths on left side), sum(car lengths on right side)). So it's O(nW), but I guess the recursive solution must explore a small fraction of the possible states on their test cases.

My recursive was lot slower than iterative one. May be due to the use of library map instead of primitive one. I think your idea of only storing maximum is good. I was saving both left and right sum , that's why same states was executing multiple times. Thanks.

I'm guessing you have to return the max amount of items you can put in the boxes, a basic iterative DP with dimension reduction in memory (pretty standard in dp), basically O(W*N) time but only O(W) memory should to the trick and run basically instantly because the dp array is small enough to be in cache 100% of the time.

In order to apply the dimension reduction you just need to make sure that a simple condition is met: all of the information of certain levels is never accesed again, in this case once you have k items in the box you just access k-1, so everything from k-2 to 0 is not used, depending on the problem/implementation you can use 1 or 2 rows instead of N.

Note: more complex problems might require m rows.

I think this makes some sense, but I am not sure I fully understand it. Can you please write down any sort of pseudo code to help me grasp the concept ?

Sure, I can show you how to optimize knapsack, not this problem because solving it should help you understand how to apply this trick :)

Let me know if you have any doubts.