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 non-zero 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 non-zero 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[p-1].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";
}
}