PROBLEM LINK:
Setter & Editorialist : Mayuresh Patle
Tester : Uttkarsh Bawankar
DIFFICULTY:
EASY
PREREQUISITES:
Recursion, Modular Arithmetic, Amortised Complexity Analysis
PROBLEM:
You are given an array L of size N, in which each element belongs to exactly one of the M available groups. Let’s say i^{th} element L_i belongs to group numbered G_i. You are also given another array LG of size M.
For each i such that 1 \leq i \leq M, you are allowed to remove any number of elements (possibly 0) from the i^{th} group. You’ve to find the maximum the value of (\prod_{L_j \in G_i} L_j) \mod LG_i, using the above operation.
Notable constraints:
 1 \leq N \leq 160
 \lceil \frac{N}{16} \rceil \leq M \leq N
 Each Group has at most 16 members.
QUICK EXPLANATION
For each group, calculate the required value for each subset of elements in that group and print the maximum value.
EXPLANATION:
On analysing the constraints, we can conclude that:
 Maximum possible number groups, with each group having maximum possible number of elements (i.e. 16) is \frac{MaxN}{16}=\frac{160}{16}=10.
 Hence, if we generate all subsets in this scenario, maximum iterations will be 10*2^{16} = 655360, which is affordable in given time constraints.
Hence, we can can maintain M arrays (or any similar structure) such that the i^{th} structure (for 1\leq i \leq M) will contain all the elements which belong to the i^{th} group.
Now, for each group, we can recursively calculate the required value for each subset of that group. The recursive function will make exactly 2 calls, one call will include the current element and other call will not include the current element.
Hidden Traps:
 Overflow Error: Make sure you apply \mod LG_i after each multiplication to avoid the overflow error.

Special Case: When L_j \mod LG_i = 0,\ \forall L_j \in G_i, your function might return 1 in this case. To avoid this, you can either
 Maintain a count of considered elements, and return 0 if no element is considered for the current subset. Tester’s solution uses this approach.
 Ignore such elements while adding to the group. If group size is 0, then the answer will be 0. Setter’s solution uses this approach.
Amortised Time Complexity : O( T*10*2^{16} )
Auxiliary Space: O(T*(N+M))
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <ll> vll;
vector <vll> G; //This will store nonzero lucks in Groups
vll g,l,lg;
void go(ll group,ll index,ll luck,ll& ans)
{
if(index==G[group].size()) //Base Case
{
ans=max(ans,luck); //Update ans
return;
}
go(group,index+1,(luck*G[group][index])%lg[group],ans); //Include
go(group,index+1,luck,ans); //Exclude
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll T,n,m,i;
cin>>T;
while(T)
{
cin>>n>>m;
//Initialization
g.assign(n+1,0);
l.assign(n+1,0);
lg.assign(m+1,0);
G.assign(m+1,vll());
for(i=1;i<=n;++i) cin>>g[i]; //Group of students
for(i=1;i<=n;++i) cin>>l[i]; //Luck of students
for(i=1;i<=m;++i) cin>>lg[i]; //Luck of Guide
for(i=1;i<=n;++i) if(l[i]%lg[g[i]]) //Exclude 0's (& remainder 0's too)
G[g[i]].push_back(l[i]%lg[g[i]]); //Add nonzero lucks to Group
for(i=1;i<=m;++i)
{
ll ans=1;
go(i,0,1,ans); //recursive bruteforce
if(G[i].empty()) ans=0; //Group Luck = 0 case
cout<<ans<<" ";
}
cout<<"\n";
}
return 0;
}
Tester's Solution
//author: utkd52
#include<bits/stdc++.h>
typedef long long ll;
#define fi(n) for(int i=0;i<n;i++)
#define fj(n) for(int j=0;j<n;j++)
#define pb push_back
#define USE_FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
ll curMax;
void calSum(vector<ll> &v, int ind, ll sum, vector<ll> &l, ll md, ll added)
{
ll mulSum = ((sum%md) * (l[v[ind]]%md))%md;
if(ind==v.size()1)
{
if(sum%md > curMax && added>0)
{curMax = sum%md;}
if (mulSum > curMax) {curMax = mulSum;}
return;
}
else
{
calSum(v, ind+1, (sum%md), l, md, added);
calSum(v, ind+1, mulSum, l, md, added+1);
}
}
int main()
{
USE_FAST_IO;
ll t,n,m,p,q;
cin>>t;
while(t)
{
cin>>n>>m;
vector<ll> l(n), lc(m), ans(m);
vector<vector<ll>> g(m);
fi(n)
{
cin>>p;
g[p1].pb(i);
}
fi(n)cin>>l[i];
fi(m)cin>>lc[i];
ll sum=0;
fi(m)
{
curMax =0;
bool z = true;
fj(g[i].size())if(l[g[i][j]]!=0)
{
z = false;
break;
}
if(!z)
{
calSum(g[i], 0, 1, l, lc[i],0);
ans[i] = curMax;
}
else ans[i] = 0;
}
fi(m)cout<<ans[i]<<" ";
cout<<"\n";
}
}