Gold grid problem

reddevil · September 10, 2019, 8:18am

i am not getting how to approach this problem…plzz…help

Robin_rst · September 10, 2019, 2:40pm

Just take prefix sum of every row and after that take prefix sum of every column.
Then if you partition the (i,j)th of grid then your top-left box sum will be the value at (i,j)th index of grid
and top-right box sum will be the sum at that row’s last column - the sum of top-left box sum
and bottom right box sum will be the value at (n,j)th of grid - the sum of top-left box
and bottom-right box sum will be the value at (n,m)th of grid - top-right box sum - bottom left box sum + the sum of top-left box ( because it get subtracted two times , first time in top-right box sum and second time in bottom-left box sum ).
Make ans at every step as
ans = max ( ans, min( all four boxes) );
You can see my implementation, i have commented the part for better understanding. Its better if you try on notebook with one small example to have a crystal clear understanding.

github.com

robinrst/Dynamic-Programming/blob/master/GoldCoinDP.cpp

#include "bits/stdc++.h"

using namespace std;

#define  f first
#define  lgn 25
#define  endl '\n'
#define  sc second
#define  N (int)1e3+5
#define  sz(x) x.size()
#define  int long long int
#define  ld long double
#define  vi vector<int>
#define  vs vector<string>
#define  vc vector<char>
#define  mii map<int,int>
#define  pii pair<int,int>
#define  vpii vector<pii>
#define  test(x) while(x--)
#define  pb push_back

This file has been truncated. show original

Robin_rst · September 14, 2019, 10:00am

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.

rasokan · September 28, 2019, 9:27am

Hello Robin,

Can you please give idea on how this prefix sum approach, help to solve this problem?

Thanks