PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Niket Agarwal
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
Problem-statement
The problem basically is :
In a NxN matrix , for each cell calculate the product of maximum sum of values on 4 shortest path from the corners of the matrix to the current cell.
Print out the maximum among the products for all cells.
EXPLANATION:
It’s just a slight modification of the classical dp problem 'In a NxM matrix , find maximum valued shortest path from cell (1,1) to cell (N,M).
In this version however, we have to repeat the steps for all directions.
First fix source as (1,1) then find shortest path with max value to each cell. For those who are seeing this kind of problem for the first time, the dp will have 2 states.
DP[i][j] = maximum possible value that can be obtained on a shortest path from (1,1) to (i,j)
The base case is DP[1][1] = A[1][1] and the transitions is as follows:
DP[i][j] = A[i][j] + max(DP[i-1][j]+DP[i][j-1])
It’s intuitive because we know for shortest path length we can only move down or right ,and that means we can only arrive to cell (i,j) from cell (i-1,j) and cell (i,j-1).
In this problem, we do this for 4 directions.
1- top-left to bottom-right , i.e , (1,1) to (N,N)
2- top-right to bottom-left , i.e , (1,N) to (N,1)
3- bottom-right to top-left , i.e , (N,N) to (1,1)
4- bottom-left to top-right , i.e , (N,1) to (1,N)
See setter solution for implementation.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000;
const int mod=1000000007;
int dp[4][N][N],a[N][N];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=1;
cin>>t;
while(t--)
{
int n;
cin>>n;
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
cin>>a[i][j];
dp[0][i][j]=0;
dp[1][i][j]=0;
dp[2][i][j]=0;
dp[3][i][j]=0;
}
}
dp[0][0][0]=a[0][0];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if(i==0&&j==0)continue;
dp[0][i][j]=a[i][j];
int x=0,y=0;
if(i-1>=0)x=dp[0][i-1][j];
if(j-1>=0)y=dp[0][i][j-1];
dp[0][i][j]=(dp[0][i][j]+max(x,y));
}
}
dp[1][0][n-1]=a[0][n-1];
for (int i = 0; i < n; ++i)
{
for (int j = n-1; j >= 0; --j)
{
if(i==0&&j==n-1)continue;
dp[1][i][j]=a[i][j];
int x=0,y=0;
if(i-1>=0)x=dp[1][i-1][j];
if(j+1<=n-1)y=dp[1][i][j+1];
dp[1][i][j]=(dp[1][i][j]+max(x,y));
}
}
dp[2][n-1][n-1]=a[n-1][n-1];
for (int i = n-1; i >= 0; --i)
{
for (int j = n-1; j >= 0; --j)
{
if(i==n-1&&j==n-1)continue;
dp[2][i][j]=a[i][j];
int x=0,y=0;
if(i+1<=n-1)x=dp[2][i+1][j];
if(j+1<=n-1)y=dp[2][i][j+1];
dp[2][i][j]=(dp[2][i][j]+max(x,y));
}
}
dp[3][n-1][0]=a[n-1][0];
for (int i = n-1; i >= 0; --i)
{
for (int j = 0; j <=n-1; ++j)
{
if(i==n-1&&j==0)continue;
dp[3][i][j]=a[i][j];
int x=0,y=0;
if(i+1<=n-1)x=dp[3][i+1][j];
if(j-1>=0)y=dp[3][i][j-1];
dp[3][i][j]=(dp[3][i][j]+max(x,y));
}
}
int ans=0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
ans=max(ans,dp[0][i][j]*dp[1][i][j]*dp[2][i][j]*dp[3][i][j]);
}
}
cout<<ans<<'\n';
}
return 0;
}
Tester's Solution
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
public static void process()throws IOException
{
int n=ni();
long[][]A=new long[n+2][n+2];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
A[i][j]=nl();
long[][]a=new long[n+2][n+2];
long[][]b=new long[n+2][n+2];
long[][]c=new long[n+2][n+2];
long[][]d=new long[n+2][n+2];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=Math.max(a[i-1][j],a[i][j-1])+A[i][j];
for(int i=n;i>0;i--)
for(int j=1;j<=n;j++)
b[i][j]=Math.max(b[i+1][j],b[i][j-1])+A[i][j];
for(int i=n;i>0;i--)
for(int j=n;j>0;j--)
c[i][j]=Math.max(c[i+1][j],c[i][j+1])+A[i][j];
for(int i=1;i<=n;i++)
for(int j=n;j>0;j--)
d[i][j]=Math.max(d[i-1][j],d[i][j+1])+A[i][j];
long ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans=Math.max(ans,a[i][j]*b[i][j]*c[i][j]*d[i][j]);
pn(ans);
}
static AnotherReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
boolean oj = true;
if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
int t=1;
t=ni();
while(t-->0) {process();}
out.flush();out.close();
}
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);out.flush();}
static int ni()throws IOException{return sc.nextInt();}
static long nl()throws IOException{return sc.nextLong();}
static double nd()throws IOException{return sc.nextDouble();}
static String nln()throws IOException{return sc.nextLine();}
static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class AnotherReader{BufferedReader br; StringTokenizer st;
AnotherReader()throws FileNotFoundException{
br=new BufferedReader(new InputStreamReader(System.in));}
AnotherReader(int a)throws FileNotFoundException{
br = new BufferedReader(new FileReader("input.txt"));}
String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
st = new StringTokenizer(br.readLine());}
catch (IOException e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}