CMX1P01 - Code Together - Code Mates x1 Editorial

PROBLEM LINK:

Contest
Practice

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";
	}
	
}
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[10000];
	vector<vector<ll>> vec(10000);
	for(ll i=1;i<=n;++i)
	{
		cin>>arr[i];
		vec[arr[i]].pb(i);
	}
	ll l[10000];
	for(ll i=1;i<=n;++i)
		cin>>l[i];
	ll lg[10000];
	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

can u please help me in identifying issue in the code due to which WA comes:-

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][0]%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