# GOOGLE KICK START ROUND-A- Plates MLE

I’ve tried to solve this with brute force which gives me MLE(memory limit exceeded) for test set 2… Can someone suggest me a better approach for this…

My solution:
from itertools import combinations

def balls_in_boxes(n, m):
“”"Generate combinations of n balls in m boxes.

``````>>> list(balls_in_boxes(4, 2))
[(0, 4), (1, 3), (2, 2), (3, 1), (4, 0)]
>>> list(balls_in_boxes(3, 3))
[(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (3, 0, 0)]

"""
for c in combinations(range(n + m - 1), m - 1):
yield tuple(b - a - 1 for a, b in zip((-1,) + c, c + (n + m - 1,)))
``````

tc = int(input())
for t in range(0, tc):
n,k,p = map(int, input().split())

``````arr = [[0 for i in range(k)] for j in range(n)]
for i in range(0,n):
arr[i] = list(map(int, input().split()))

for i in range(0,n):
for j in range(1,k):
arr[i][j] = arr[i][j-1]+arr[i][j]

li = list(balls_in_boxes(p,n))
maxCost = 0
for tup in li:
cost = 0
#print(tup)
i = 0
for val in tup:
if(val == 0):
i += 1
continue
if(val > k):
break
else:
cost += arr[i][val-1]
i += 1
if cost > maxCost:
maxCost = cost

result = "Case #"+str(t+1)+": "+str(maxCost)
print(result)
``````

i haven’t sloved it.But some people are using dp in it…

Two problems:

1. Saving every combination in memory defeats the purpose of using a generator. At the line `li = list(balls_in_boxes(p, n))`, you are loading all the tuples in memory, even though you use only one tuple from li at any point in time. Consider doing without the variable li

2. Even if you solve the memory problem, iterating over every tuple and then computing the cost is solving several redundant problems again and again. Since n is now 100, you would run into time limit. Think of the redundant problems and try to trade off some memory in exchange for efficiency in time.

You could solve it using DP. My approach was as follows:

General Solution outline
dp[x][y] = Max cost for accumulating y plates using piles 1…x both inclusive
dp[x][y] = max(dp[x-1][y],dp[x-1][y-1]+a,…,a[y])
Link to my cpp solution: Competitive-Coding-Solutions/plates.cpp at master · ighosh98/Competitive-Coding-Solutions · GitHub

Can relate it to knapsack problem(0-1) where weight is total number of items and values are the sums (prefix sums) of the stacks.  