## Wednesday, March 18, 2015

### 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;
}