Saturday, March 28, 2015

UVa 11832 - Account Book

Problem Statement:
UVa 11832 - Account Book

Solution:
The solution to this problem employs a simple yet powerful idea. Let's call the given values as a[i]. Let S[i] be the set of values that can be reached using elements in a[1..i]. Then S[i+1] = everything in S[i] and anything that is reachable from elements in S[i] after addition or subtraction with a[i+1]. With this idea we can already solve the problem by iterating through each a[i] and test for each sign, but this approach is very inefficient, since we have to recompute the same values again and again for each a[i] we are focusing on, which gives us $$O(kN^2)$$ with k at most 80000.

So to speed things up, we add another set R[j] which stores all values reachable using elements in a[j..N]. As such, checking whether we can reach value F on each i is a matter of checking whether there is a mapping between S[i-1] to R[i+1] that allow us to get F after addition or subtraction with a[i]. With this simple idea, we brings down the complexity to $$O(kN)$$!

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std;

int a[50];
int dp[50][80010];
int dprev[50][80010];
int X = 40000;
int N, F;

void solve() {
string ans = "";
for(int i=0;i<=N+1;++i){
for(int j=0;j<80010;++j){
dp[i][j] = 0;
dprev[i][j]= 0;
}
}

dp[0][X] = 1;
for(int i=0;i<N;++i){
for(int j=0;j<=80000;++j){
int next = j + a[i+1];
if(next>=0 && next <= 80000) dp[i+1][next] = max(dp[i][j], dp[i+1][next]);
next = j - a[i+1];
if(next>=0 && next<=80000) dp[i+1][next] = max(dp[i][j], dp[i+1][next]);
}
}
dprev[N+1][X] = 1;
for(int i=N+1;i>1;--i){
for(int j=0;j<=80000;++j){
int next = j + a[i-1];
if(next>=0 && next <= 80000) dprev[i-1][next] = max(dprev[i][j], dprev[i-1][next]);
next = j - a[i-1];
if(next>=0 && next<=80000) dprev[i-1][next] = max(dprev[i][j], dprev[i-1][next]);
}
}
if(dp[N][X+F] == 0) {
printf("*\n");
return;
}
for(int k=1;k<=N;++k){
int mark[2] = {0, 0};
for(int j=0;j<=80000;++j){
if(dp[k-1][j]) {
int something = F + 2*X - a[k] - j;
if(0<=something && something<=80000) mark[0] = max(mark[0], dprev[k+1][something]);
something = F + 2*X + a[k] - j;
if(0<=something && something<=80000) mark[1] = max(mark[1], dprev[k+1][something]);
}
}

if(mark[0] && mark[1]) ans += "?";
else if(mark[0]) ans += "+";
else if(mark[1]) ans += "-";
else ans += "F";
}
cout << ans << endl;
}

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