 # CMX1P01 - Code Together - Code Mates x1 Editorial

Setter & Editorialist : Mayuresh Patle
Tester : Uttkarsh Bawankar

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)
{
{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";
}

}

2 Likes

I tried this approach using power set. But it was giving TLE. Can you help me with that?
My Code:

ll showPowerSet(vector<ll>& set, ll set_length,ll m)
{
ll ans = 0;
if(set_length==0)
return 0;
unsigned int size = pow(2, set_length);
for(int counter = 0; counter < size; counter++)
{

ll tempans = 1;
for(int j = 0; j < size; j++)
{
if(counter & (1ll<<j))
{
if(j>=set_length)
continue;
tempans = ((tempans%m)*(set[j]%m))%m;
if(tempans==0)
break;
}

}
ans = max(ans,tempans);
if(ans==m-1)
break;
}
return ans;
}

void solve()
{
ll n,m;
cin>>n>>m;
ll arr;
vector<vector<ll>> vec(10000);
for(ll i=1;i<=n;++i)
{
cin>>arr[i];
vec[arr[i]].pb(i);
}
ll l;
for(ll i=1;i<=n;++i)
cin>>l[i];
ll lg;
for(ll i=1;i<=m;++i)
cin>>lg[i];
for(ll i=1;i<=m;++i)
{
vector<ll> temp;
ll mp= lg[i];
for(ll j=0;j<vec[i].size();++j)
{
if(l[vec[i][j]]%mp!=0)
temp.pb(l[vec[i][j]]);
}
ll len = temp.size();

ll ans = showPowerSet(temp,len,mp);
cout<<ans<<" ";
}
cout<<"\n";

}

int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

ll t=1;
cin>>t;
ll z=1;
while(t--)
{
z++;
solve();
}

return 0;
}

You are doing 2^\text{Group Size} * \text{Group Size} iterations for each group, whereas only 2^{\text{Group Size}} were expected.

3 Likes

Oh, I never thought doing a recursive solution like that will yield better complexity. I guess I need to practice more. Thankyou, It was a fun contest.

3 Likes

I tried O(2^group_size * group_size * groups) and that TLEd so I had to do Meet in the Middle

Same time complexity can be achieved using iteration as well.

https://www.codechef.com/viewsolution/37341192

2 Likes

that’s a nice way to solve it.

1 Like

There are the errors leading to WA.

Error 1: In this function

int rem(int remain,int index,int pro,int count,int n){
if(index >= vec[count].size())
return remain;
int a = rem((pro*vec[count][index])%n, index+1, (pro*vec[count][index])%n,count,n);
int b = rem(vec[count][index]%n, index+1, (vec[count][index])%n,count,n);
return max(remain,max(a,b));
}


instead of excluding current value, you are starting a new series with current value.
Also, any one of remain or pro is sufficient since both are having same value. You can edit the functions as:

int rem(int remain,int index,int count,int n){
if(index == vec[count].size())      //index won't go beyond vec[count].size()
return remain;
int a = rem((remain*vec[count][index])%n, index+1,count,n);  //included vec[count][index]
int b = rem(remain, index+1,count,n);                        //excluded vec[count][index]
return max(a,b);
}


Error 2: You are not considering the combinations which exclude the element at index 0. So, rather than making a call with remain=vec[i]%M[i] and index=1, you should make this call:

rem(1, 0, i, M[i])

1 Like

got the error…Thanks a lot sir

1 Like