Gold Grid problem(HackerBlock April2020 Dynamic Programming Challenge)

#1

//the code is giving wrong answer for some of the test cases.Help me to solve the problem
//GOLD GRID hacker_block dp problem
#include<bits/stdc++.h>
using namespace std;
int N,M,i,j;
int dp[1000][1000];
int Gold[1000][1000];
int ans=0;

int maxGoldCoin(int n)
{
//constuct the dp array first
dp[0][0]=Gold[0][0];

for(int i=1;i<n;i++)
{
	dp[i][0]=dp[i-1][0]+Gold[i][0];

}

for(int j=1;j<n;j++)
{
	dp[0][j]=dp[0][j-1]+Gold[0][j];
}

for(int i=1;i<n;i++)
{
    for(int j=1;j<n;j++)
    {
        if(Gold[i][j]==1)
        dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+1;
        else
        {
       dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+0;
        }
        
    }
}

//divide the grid and find out the mx result
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{

        int op1=dp[i][j];
        int op2=dp[i][n-1]-dp[i][j];
        int op3=dp[n-1][j]-dp[i][j];
        int op4=dp[n-1][n-1]-(op1+op2+op3);
         ans=max(ans,min(min(min(op1,op2),op3),op4));

    }

}

return ans;
}

int main()
{

memset(dp,0,sizeof(dp));
memset(Gold,0,sizeof(Gold));
cin>>N>>M;
while(M--)
{
 cin>>i>>j;
 Gold[i][j]=1;
}
cout<<maxGoldCoin(N);
return 0;

}
//question link:https://hack.codingblocks.com/app/contests/1338/793/problem

#2

@hrit04 please share the ide link of your code

#3

@hrit04 Xi and Yi which you are taking as input are starting from 1 so take care of that. Just correct it, you will able to solve it then.

#4

Also mark this doubt as resolved if you are able to solve it now.

#5
#6

@hrit04 I think you haven’t got what i said. I just said to do these change, you can have a look at this corrected code of yours https://ide.codingblocks.com/s/225276

#7

i have taken input Xi and Yi as starting from 1 because I have handled the case of first row and first column of the grid in the begining of the construction of the dp array.i,e

dp[0][0]=Gold[0][0];
for(int i=1;i<n;i++)
{
dp[i][0]=dp[i-1][0]+Gold[i][0];

}

for(int j=1;j<n;j++)
{
dp[0][j]=dp[0][j-1]+Gold[0][j];
}

#8

@hrit04
Ya, i already got what you are doing, see if you want to take Xi and Yi starting from 1. Then in your code you need to consider the index till n, i.e. in for-loops it should be (i-1; i<=n; i++)
Also take to size of array till 1001 as 1000 is maximum index possible.

I have also done these changes for you, if you need you can see this https://ide.codingblocks.com/s/225287

#9

Also please mark this doubt as resolved, if you are able to solve it now.

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.