## Friday, October 3, 2014

### a bit of dp: SPOJ - NOCHANGE

Problem Statement:
SPOJ - NOCHANGE

Summary:
Can we choose $$c_1, c_2, \ldots, c_k$$ such that $$c_1v_1 + c_2v_2 + \ldots + c_kv_k = X$$ where $$c_1 \geq c_2 \geq \ldots \geq c_k$$?
$$k \leq 5$$, $$X\leq 10^5$$

Solution:
Another interesting DP technique. Let $$S_k$$ be a set such that if $$n \in S_k$$, then $$n$$ can be represented as a sum of $$v_i$$ with non-increasing coefficients $$c_i$$ as above. (Notice that $$0 \in S_k$$ )Now consider $$S_{k+1}$$. For each $$n$$ in $$0, \ldots, X$$, $$n \in \S_{k+1}$$ if and only if there is $$m \in S_k$$ such that $$n = m + c(v_1 + v_2 + \ldots + v_{k+1})$$ for some $$c$$ (Hence the resulting coefficients will be non-decreasing as well).
Implementation:

bool solve(){
sum[0] = v[0];
for(int i=1;i<K;++i){
sum[i] = sum[i-1] + v[i];
}
for(int i=0;i<=N;++i){
dp[i] = 0;
}
dp[0] = 1;
for(int i=0;i<=N;++i){
if(dp[i]) dp[i+v[0]] = 1;
}
for(int k=1;k<K;++k){
for(int i=0;i<=N;++i){
if(!dp[i]) continue;
int u = i + sum[k];
if(u>N) break;
dp[u] = 1;
}
}
return dp[N];
}