Gold Rush(CC026) - Editorial

editorial
, , ,
1

CONTEST:
CODICTION 2.0

PROBLEM LINK:
Contest
Practice

Author : Vishal Rochlani
Tester: Murtaza Ali, Yash Sharma, Pratik Jain
Editorialist: Saniya Agrawal

DIFFICULTY:
Medium

PREREQUISITES:
DP, Matrix, Prefix Sum, Suffix Sum

PROBLEM:
Calculate the maximum amount of gold you can get when you move from 1st row to the last row adding gold present in the cells and subtracting gold equivalent to the difference in columns when moving.

SOLUTION:
To solve in an optimised manner we would save the best possible amount of gold for every cell in a dp array and then iterate through the last row to find the required answer.

So, we iterate through each row and for every index we store the most beneficial option for it using the prefix and suffix array.The prefix array will store the index of the element having maximum value in 0 to j while suffix would give the index of the element having maximum value in j to n. But we can not compare the maximum element directly as we also need to include the cost of moving between columns. So for that, we first subtract j from our maximum element and then compare its value. And then, accordingly we update values of maximum and index of maximum element.We do the same thing for the suffix array but this time we subtract (n-1-j) and add (n-1-j) to our max value.

Code 
pre[0] = 0;
ll mx = dp[i-1][0],ind = 0;
for(j = 1;j < n;j++)
{
    if(mx-j< dp[i-1][j])
    {
        mx = dp[i-1][j]+j;
        ind = j;
    }
    pre[j] = ind;
}

We use the below formula to calculate dp[i][j]
dp[i][j] = max((dp[i-1][pre[j]]-(j-pre[j])),(dp[i-1][suf[j]]-(suf[j]-j)) + a[i][j]

Here, to the gold present in the cell initially, we add the gold of the cell from where we have made this movement subtracting the difference of columns.We do this for both the prefix and suffix cells and their max gives us the value for the dp array.

After traversing all the columns, to get our final solution, we simply need to find the maximum value from the last row and that would be our answer.

Setter's Code 
#include"bits/stdc++.h"
#define ll long long

using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll i,j,n,t,k;

  cin>>t;

  while(t--)
   {
     cin>>n;
     ll a[n][n],dp[n][n], suf[n], pre[n];

     for(int i=0;i < n;i++)
     {
         for(j=0;j < n;j++)
         {
             cin>>a[i][j];
         }
     }

     for(i=0;i <n; i++)
     {
         dp[0][i] = a[0][i];
     }

     for(i=1;i < n;i++)
    {
       pre[0] = 0;
       ll mx = dp[i-1][0],ind = 0;
       for(j = 1;j < n;j++)
       {
           if(mx-j< dp[i-1][j])
           {
               mx = dp[i-1][j]+j;
               ind = j;
           }
           pre[j] = ind;
       }

       mx = dp[i-1][n-1],ind = n-1;
       suf[n-1] = n-1;
       for(j = n-1;j >= 0;j--)
       {
           if(mx-(n-1-j)< dp[i-1][j])
           {
               mx = dp[i-1][j]+(n-1 - j);
               ind = j;
           }
           suf[j] = ind;
       }

       for(j=0;j < n;j++)
       {
           k = max((dp[i-1][pre[j]]-(j-pre[j])),(dp[i-1][suf[j]]-(suf[j]-j)) );
           dp[i][j] = k+a[i][j];
       }
   }

   ll ans = LONG_MIN;

   for(j=0;j < n;j++)
   {
       ans = max(ans, dp[n-1][j]);
   }

   cout<<ans<<"\n";
}

return 0;
}
1 Like