Now codersbit is over… I want to upsolve a problem of that contest
Problem statement: Given an array of size n and an integer B. We have to choose those elements from its subsequence such that:
For eg if chosen subsequence is A1,A2,A3,A4
Then gcd(A1,A2)+gcd(A3,A4) should be maximum possible and length of subsequence should be less than equal to 2*B and should be even.
How to approach this problem… Pls help
I solved that problem using Dynamic Programming dp[N][B]. dp[I][J] stores the maximum sum we can make taking j pairs i.e 2j elements till jth index. The Complexity of that Approach is BN*N.
dp[B+1][N];
First Initialize the DP table with 0.
Then Fill the base condition of B=1
mx = 0;
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
dp[1][i] = max( dp[1][i], gcd(A[i],A[j]) );
}
mx=max(mx,dp[1][i]); // maximizing the ith position by taking max from previous indexes
dp[1][i] = mx;
}
Then filling our DP table
for(k=2;k<=B;k++)
{
mx = 0;
for(i=2*(k-1);i<n;i++)
{
for(j=2*(k-1);j<i;j++)
{
dp[k][i] = max( dp[k][i], dp[k-1][j-1] + gcd( A[i], A[j]) );
}
mx = max(mx,dp[k][i];
dp[k][i] = mx;
}
}
Now for each k we have our answer is stored in dp[k][n-1]
Now the problem was that we can choose any subsequence of even length less than 2*B
So return the max of k in range 1 to B dp[k][n-1]
what dp[i][j] will store
I solved it using top down approach .
long long int dp[501][501]={-1};
long long int solve(vector < int > &a, int i , int rem)
{
//If no elements are remaining in array or you can`t add any elements further return 0;
if(i<0 || rem<=0)
{
return 0;
}
// this case handles when you are at first element .It should return zero because you can`t take any element before it to pair with .
if(i==0)
{
return 0;
}
else if(dp[i][rem]!=-1)
{
return dp[i][rem];
}
else
{
dp[i][rem]=0;
// trying every pair (i,j) where j= i-1 to 0 and recursing with j-1 to 0 .
for(int j=i-1;j>=0;j–)
{
dp[i][rem]=max(dp[i][rem],__gcd(a[i],a[j])+solve(a,j-1,rem-2));
}
dp[i][rem]=max(dp[i][rem],solve(a,i-1,rem)); // This is handling case when you are ignoring element at ith index .
return dp[i][rem];
}
}
Here rem is denoting number of elements that can still be inserted if we are at index i .
So initially we are at index n-1 (0 based indexing ) and elements that can be inserted are 2 * B .
so ans will be solve(a,n-1,2 * B);
Did it somewhat the same way, built a recursive function and just stored result if not calculated
Can anyone provide some test cases for the same