Link of the problem :

https://practice.geeksforgeeks.org/contest-problem/bjorn-ironside/1/

![ ]()

In the hints section , they only mentioned the code of solution , which seems to involve digit dynamic programming . Can somebody explain solution to this problem or at least explain what the dp states are ? Thankyou .

Code given by them for this problem : (C++ code written in leetcode contest type format)

class Solution{

	int mod = (int)(1e9 + 7);
	int mask;

	private:
	int MEM(int mask_j, vector<int> &a, vector<long long> &dp, int n)
	{
		if(mask_j > mask)
			return 0;
		
		if(mask_j == mask)
			return 1;
	 
		long long &ans = dp[mask_j];
	 
		if(ans!=-1)
			return (int)ans;
	 
		ans = 0;
	 
		int ind = __builtin_popcount(mask_j);
	 
		for(int j = 0; j < n; j++)
		{
			
			if(!((1<<j)&mask_j) and ((1<<j)&a[ind]))
			{
	 
				ans += 1LL*MEM(mask_j | (1<<j), a, dp, n);
	 
				if(ans>=mod)
					ans %= mod;
			}
			
		}
	 
		return (int)ans;
	}

	public:
	int numberOfWays(int n, vector<vector<char>> &mat)
	{
		
		vector<int> a(n, 0);
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				
				if(mat[i][j] == '#')
					a[i] |= (1<<j);
			}
		}
	 
		mask = (1<<n)-1;

		vector<long long> dp(mask + 5, -1);
	 
		return MEM(0, a, dp, n);
	}

};

Given 2-arrays "$$$A$$$" and "$$$B$$$" of length $$$n$$$ , calculate maximum possible product of all elements of array "$$$C$$$" ,

where,

$$$C[i] = A[j]*B[k] $$$

Or

$$$C[i] = A[j] + B[k] $$$,

(its your choice, what to select from both of them)

for all $$$1<=i<=N$$$

Once an index 'j' and 'k' have been used from array A and B respectively, you can't use them ever again.

Find the maximum possible value of C[1]*C[2]*......C[N] modulo p , where p = 1000000007.

$$$1<=A[i]<=100000 $$$

$$$1<=B[i]<=100000 $$$

$$$1<=N<=100000 $$$

Example :

Array A : [1,2]

Array B : [4,3]

Best possible array C :$$$ [(3+1),(4*2)] = [4,8] .$$$

Final answer = 4*8 = 32 which is the maximum possible product.

I applied the greedy approach in the test which failed all the test cases except 1.

My greedy approach was : Sort both "A" and "B", then do $$$C[i]=max(A[i]+B[i], A[i]*B[i]) $$$

Second problem of the test was : Given a graph with $$$N$$$ nodes and $$$M$$$ edges , remove any number of nodes you want to remove and calculate the maximum-sized-bipartite-graph. (Don't remember the constraints, I think N and M were small.)