PROBLEM LINK:
Author: Vraj
Tester: Vraj
Editorialist: Vraj
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Greedy, Dynamic Programming
PROBLEM:
Given 4 arrays A_1 (of size K), A_2 (of size L), A_3 (of size M) and A_4 (of size N) with positive integers. You start with a score of 0. You remove 1 entry each from two different arrays and multiply them together to get a number. You add that number to your score. Find the maximum score achievable.
QUICK EXPLANATION:
Sort all arrays in descending order. We will have to use a 4D DP, DP[i][j][k][l] denoting the max. score achievable if i elements are used from A_1, j elements are used from A_2, k elements are used from A_3 and l elements are used from A_4. Now, update the DP for all 6 combinations of the 2 arrays to select from. As an example, for the case where elements are picked from A_1 and A_2:
dp[i+1][j+1][k][l] = \max(dp[i+1][j+1][k][l], curr + a[0][i]*a[1][j])
EXPLANATION:
Let us consider a simpler variant of the problem where you only have 2 arrays to work with. It is easy to see that the greedy approach of sorting the two arrays in descending order and pairing of the highest elements in both arrays always is the optimal solution for this case.
Now, the observation that you need to make is that this approach does not generalize to the problem at hand with 4 arrays. One easy way to figure out why the greedy approach would not work directly is to think of the scenario when multiple choices of arrays achieves the same value added to the score, you cannot arbitrarily pick one.
Therefore, to decide which two arrays are suitable, we try all the combinations of picking them smartly using DP. We define DP[i][j][k][l] as the max. score achievable if i elements are used from A_1, j elements are used from A_2, k elements are used from A_3 and l elements are used from A_4. Now you need to update the DP values according to the choices. As an example, for the case where elements are picked from A_1 and A_2:
dp[i+1][j+1][k][l] = \max(dp[i+1][j+1][k][l], curr + a[0][i]*a[1][j])
For each possible i,j,k,l, you have to update the DP table values in the way above for all 6 combinations.
The sorting of all arrays takes a total time of \mathcal{O}\left(K\log(K) + L\log(L) + M\log(M) + N\log(N)\right). We go over all possible values of i, j, k and l, making the time taken to update the DP table \mathcal{O}\left(KLMN\right).
SOLUTIONS:
Setter's Solution
n = [int(x) for x in input().split()]
a = []
for i in range(4):
a.append([int(x) for x in input().split()])
a[i].sort(reverse=True)
dp = [[[[0]*(n[3]+1) for i in range(n[2] + 1)] for j in range(n[1] + 1)] for k in range(n[0] + 1)]
ans = 0
I,J,K,L = n
for i in range(n[0] + 1):
for j in range(n[1] + 1):
for k in range(n[2] + 1):
for l in range(n[3] + 1):
curr = dp[i][j][k][l]
if i < I and j < J:
dp[i+1][j+1][k][l] = max(dp[i+1][j+1][k][l],
curr + a[0][i]*a[1][j])
if i < I and k < K:
dp[i+1][j][k+1][l] = max(dp[i+1][j][k+1][l],
curr + a[0][i]*a[2][k])
if i < I and l < L:
dp[i+1][j][k][l+1] = max(dp[i+1][j][k][l+1],
curr + a[0][i]*a[3][l])
if j < J and k < K:
dp[i][j+1][k+1][l] = max(dp[i][j+1][k+1][l],
curr + a[1][j]*a[2][k])
if j < J and l < L:
dp[i][j+1][k][l+1] = max(dp[i][j+1][k][l+1],
curr + a[1][j]*a[3][l])
if k < K and l < L:
dp[i][j][k+1][l+1] = max(dp[i][j][k+1][l+1],
curr + a[2][k]*a[3][l])
ans = max(ans, curr)
print(ans)