Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1967
You are given a set of N integers. You can take K different elements from them to make a group. Two groups will be different if there is at least one element which is not common to both. For example, if there are 4 elements a, b, c, d and you are asked to take two elements then ab, ad, bc, cd are all valid and different groups. A grouping system is complete if for a particular K, number of different groups is the maximum. In the former case, {ab, bc, cd, bd, ad, ac} is a complete grouping system. For a particular complete grouping system, the fitness is calculated in the following way 1. Each group of a grouping system contributes a part the multiplication of all numbers of that group 2. Contribution from all groups are added 3. The fitness is equivalent to T otal Contribution mod M, M is the bounding parameter In our example, for K = 2, the fitness is F2 = (ab + bc + cd + bd + ad + ac) mod M. If K = 1, then fitness is F1 = (a + b + c + d) mod M. Here, in this problem you have to find the complete grouping system with maximum fitness. Input Each test case starts with two positive integer N (2 ≤ N ≤ 1000) and M (1 ≤ M < 2 31). In next few lines there will be N positive integers. Each integer will be at best 1000. Input will be terminated by a case where N = M = 0. Output For each test case, print in a line the maximum fitness possible for a grouping system.
Sample Input 4 10 1 2 3 4 4 100 1 2 3 4 4 6 1 2 3 4 0 0
Sample Output 5 50 5
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
/*
If C[m][k] denotes the sum of products of elements of all subsets of size k chosen from first m elements,
then we have: C[m][k] = C[m-1][k] + C[m-1][k-1] * A[m], (where A[m] is m-th number in input.)
Example: consider a,b,c - pascal triangle (same as binomial coefficient)
// sX = sum of group size X
// each depth, consider a new character, to get to abc = sum(ab)*c + sum(length 3 groups)
m= (1)
m=a (1)(s1)(0)
m=b (1)(s1)(s2)(0)
m=c(1)(s1)(s2)(s3)(0)
*/
long long dp[1001][1001];
int main() {
int n,m,v;
while(scanf("%d %d",&n,&m),(n+m)) {
vector<int> nums(1);
for(int i=1;i < =n;i++){
cin >> v;
nums.push_back(v);
}
dp[0][0] = 1;
for(int i = 1; i < = n; i++) {
dp[i][0] = 1;
for(int j = 1; j < = i; j++) {
dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]*nums[i]) % m;
}
}
long long res = 0;
for(int i = 1; i < = n; i++) res = max(dp[n][i], res);
printf("%lld\n", res);
}
}
Input
1 2 3 4
4 100
1 2 3 4
4 6
1 2 3 4
0 0
Output
50
5
Demonstration
UVA Online Judge solution - 11026-A Grouping Problem - UVA Online Judge solution in C,C++,java