## Monday, September 15, 2014

### a bit of uva: UVa 11026 - A Grouping Problem

Problem Statement:
UVa 11026 - A Grouping Problem

Summary:
We are given $$a_1,a_2,\ldots,a_n$$ and a number $$K$$ which defines the sum of products of permutation of length K, e.g. $$K=1$$ is $$a_1+a_2+\ldots+a_n$$, $$K=2$$ is $$a_1a_2 + a_2a_3+ \ldots + a_{n-1}a_n$$ and so on and so forth. Find the maximum of these sum of products $$\mod{M}$$.

Solution:
Despite the technicality, this problem has a very nice recursive formulation:
Let $$S(k,n)$$ be the sum of products of permutation of length $$k$$ amongst $$n$$ elements. Then we have $$S(k,n) = a_n * S(k-1,n-1) + S(k, n-1)$$. This is actually derived from the factorization of $$a_n$$ from all the terms that contain $$a_n$$. From here, we can do a bottom-up DP to arrive at the answer. Here is a sample implementation:

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

typedef long long Long;
Long MOD, a[1003], dp[1003][1003];
int N;
// Recursion: S(k, n) = a_n * S(k-1, n-1) + S(k, n-1)

int main(){
for(int i=0;i<1003;++i){
dp[0][i] = 1;
}
while(cin >> N >> MOD){
if(N+MOD == 0) break;
for(int i=1;i<=N;++i){
cin >> a[i];
}
for(int i=1;i<=N;++i){
for(int j=i;j<=N;++j){
dp[i][j] = (a[j] * dp[i-1][j-1])%MOD;
if(j > i) dp[i][j] += dp[i][j-1];
dp[i][j] %= MOD;
if(dp[i][j] < 0) dp[i][j] += MOD;
}
}
Long ans = 0;
for(int i=1;i<=N;++i){
ans = max(ans, dp[i][N]);
}
cout << ans << endl;
}
return 0;
}