UVa 10690 - Expression Again

Problem Statement:
UVa 10690 - Expression Again

Solution:
I like this problem. Let A be the sum of the n numbers on the left, and S be the sum of all n+m numbers. Notice that the choice of A will determine the sum of the m numbers on the right, namely S-A. Our goal is to maximise and minimise A(S-A), where S is fixed. If we know beforehand all possible values of A, then the problem reduces to simply iterating through all choices of A and keeping track of the minimum and maximum A(S-A).



Now the problem is equivalent to finding all possible values of A, given n+m numbers. To do this, notice that A must be in between -2500 and 2500, because n+m is at most 100, and each of the given numbers are in the range of -50 and 50. Hence there are overall at most 5000 choices of A. Define reachable(i, val) which returns 0 or 1, where 1 means that we can have A equals to val by choosing exactly i numbers from the n+m numbers, and 0 otherwise. Then for each number x, if reachable(i, val) equals to 1, then so is reachable(i+1, val+x). By iterating through all x, we can determine whether a choice of A can be reached after choosing n numbers, by checking reachable(n, A). This approach will have a runtime complexity of \( O(5000(n+m)^2) \).

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int dp[55][5200];
int a[105];
int M, N;
int X = 2600;
void solve() {
    int sum = 0;
    for(int i=0;i<M+N;++i){
        sum += a[i];
    }
    for(int i=0;i<55;++i){
        for(int j=0;j<5200;++j){
            dp[i][j] = 0;
        }
    }
    dp[0][X] = 1;
    for(int k=0;k<M+N;++k){
        vector<pair<int,int> > st;
        for(int i=0;i<=k && i < M;++i){
            for(int j=0;j<5200;++j){
                if(dp[i][j]) {
                    st.push_back(make_pair(i+1, j+a[k]));
                }
            }
        }
        for(int i=0;i<st.size();++i){
            dp[st[i].first][st[i].second] = 1;
        }
    }
    int maxans=-12345678, minans=12345678;
    for(int j=0;j<5200;++j){
        if(dp[M][j]) {
            maxans = max(maxans, (j-X) * (sum - j + X));
            minans = min(minans, (j-X) * (sum - j + X));
        }
    }
    printf("%d %d\n",maxans, minans);
}

int main() {
    while(scanf("%d%d",&M,&N) != EOF) {
        for(int i=0;i<M+N;++i) scanf("%d",&a[i]);
        solve();
    }
    return 0;
}