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