MXPOWER - Editorial

PROBLEM LINK:

Practice
Division1
Division2

Author: Sachin Yadav
Tester: Taranpreet Singh
Editorialist: N.V. Karthikeya

DIFFICULTY:

EASY

PREREQUISITES:

Precomputation, Prefix-Sums

PROBLEM:

Given a square matrix of integers find the maximum value which can be obtained by adding all the elements in a diamond in that matrix. Refer the figure given in the problem for a better idea.

QUICK EXPLANATION:

Key observation here would be that given a cell as center , for getting the sum of diamond of larger size, we only need to add diagonal boundary cells to a smaller diamond

Precompute the prefix-sums of all the diagonals from left-top to right-bottom as well as left-bottom to right-top.
Now iterate over all the cells of the matrix, in each iteration consider that cell to be the centre of the diamond and find the maximum valued diamond corresponding to that cell using the calculated prefix sums of diagonals.

So once we find the maximum corresponding to each centre the maximum value possible is maximum amongst all these calculated values.

EXPLANATION:

Precomputation :
We need to find prefix-sums corresponding to all the diagonals from top-left to bottom-right as well as bottom-left to top-right as shown in the figure. There are 2\times N-1 first kind of diagonals and 2\times N-1 second kind of diagonals, so totally there are 4\times N-2 diagonals.

Let us maintain four N \times N matrices for easy understanding and let each of these represent the diagonals corresponding to the upper half triangle and lower half triangles. So precomp1_upper, precomp1_lower, precomp2_upper and precomp2_lower corresponding to red, blue, orange and yellow colours in the figure respectively.

Now precomp1_upper[i][j] represents diagonal starting at cell matrix[1][i] and having length j. So starting with length one we can compute prefix sums of this matrix in O(N^2), similarily precompute for the remaining 3 matrices.


Now as mentioned in the quick explanation iterate over each cell of the given matrix by considering matrix[i][j] as centre in each iteration and now find maximum value diamond corresponding to that centre.

Now to compute for the cell matrix[4][5] in the figure, we initially can figure out the maximum size of diamond possible as min(i,j,N-i+1,N-j+1)-1. We start the 0 size diamond which is just the centre so compare the maximum till now with cell value and update maximum also assign this value calculated to a variable.

value[diamond of size 2]=value[diamond of size 1] + [(precomp1_upper[3][4] - precomp1_upper[3][2]) + (precomp1_upper[1][5] - precomp1_upper[1][3]) + (precomp2_upper[7][5] - precomp2_upper[7][3]) + (precomp2_lower[2][5] - precomp2_lower[2][3])] - [matrix[5][3] + matrix[6][4] + matrix[5][5] + matrix[4][4]].

We basically added the surrounding 4 diagonals and subracted the common corners once, as we have added them twice while adding diagonals. Similarily do this for all sizes and all possible centres.

TIME COMPLEXITY:

  • O(N^3)

SOLUTIONS:

Setter's Solution
#include<iostream>
typedef long long ll;
using namespace std;
int T, N;
int arr[101][101];
ll dig1[205][202]={0}, dig2[205][202]={0};
 
pair<int,int> dig1_idx(pair<int,int> pt)
{
    pair<int,int> res;
    if(pt.first>=pt.second)
        return {N-1-(pt.first-pt.second),pt.second};
    else return {N-1 + pt.second-pt.first,pt.first};
}
 
pair<int,int> dig2_idx(pair<int,int> pt)
{   
    if(N-1-pt.first<=pt.second) return {2*N -2 - pt.first - pt.second,N-1-pt.second};
    else return {2*N -2 - pt.first - pt.second,pt.first};
}
 
void compute_diagnols()
{
    int dig1_cnt=0;
    for(int i=N-1; i>=0; i--)
    {
        for(int j=0; j<N-i; j++)
            dig1[dig1_cnt][j+1]=arr[i+j][j]+ dig1[dig1_cnt][j];
        dig1_cnt++;
    }
    for(int j=1; j<N; j++)
    {
        for(int i=0; i<N-j; i++)
            dig1[dig1_cnt][i+1]=arr[i][i+j] + dig1[dig1_cnt][i];
        dig1_cnt++;
    }
 
    int dig2_cnt=0;
 
    for(int i=N-1; i>=0; i--)
    {
        for(int j=0; j<N-i; j++)
            dig2[dig2_cnt][j+1]=arr[i+j][N-1-j]+dig2[dig2_cnt][j];
        dig2_cnt++;
    }
    for(int j=N-2; j>=0; j--)
    {
        for(int i=0; i<=j; i++)
            dig2[dig2_cnt][i+1]=arr[i][j-i]+dig2[dig2_cnt][i];
        dig2_cnt++;
    }
}
 
ll solve()
{
    compute_diagnols();
    ll answer=arr[0][0];
    ll temp;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
        {   
            ll temp=arr[i][j];
            answer=max(answer,temp); 
            int max_side=min(min(i,j),min(N-i-1,N-j-1));
            for(int side=1; side<=max_side; side++)
            {
                pair<int,int> l={i,j-side}, r={i,j+side};
                pair<int,int> t={i-side,j}, b={i+side, j};
                temp+=arr[l.first][l.second]+arr[r.first][r.second]+arr[t.first][t.second] + arr[b.first][b.second];
                pair<int,int> dig1_b=dig1_idx(b), dig1_r=dig1_idx(r);
                pair<int,int> dig2_b=dig2_idx(b), dig2_l=dig2_idx(l);
                temp+=dig1[dig1_b.first][dig1_b.second]+dig1[dig1_r.first][dig1_r.second]+ dig2[dig2_b.first][dig2_b.second]+ dig2[dig2_l.first][dig2_l.second];
                temp-=dig1[dig1_b.first][dig1_b.second-side+1]+dig1[dig1_r.first][dig1_r.second-side+1]+ dig2[dig2_b.first][dig2_b.second-side+1]+ dig2[dig2_l.first][dig2_l.second-side+1];
                answer=max(temp,answer);
            }
        }
    return answer;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while(T--)
    {
        cin>>N;
        for(int i =0; i<N; i++) for(int j=0; j<N; j++) cin>>arr[i][j];
        cout<<solve()<<"\n";
    }
    return 0;
} 
Tester's Solution
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    //Into the Hardware Mode
    void pre() throws Exception{}
    void solve(int TC)throws Exception{
        int n = ni();
        long[][] g = new long[2+n][2+n];
        for(int i = 1; i<= n; i++)
            for(int j = 1; j<= n; j++)
                g[i][j] = nl();
        long[][] d1 = new long[2+n][2+n], d2 = new long[2+n][2+n];
        for(int i = 1; i<= n; i++){
            for(int j = 1; j<= n; j++){
                d1[i][j] = d1[i-1][j-1]+g[i][j];
                d2[i][j] = d2[i-1][j+1]+g[i][j];
            }
        }
        long ans = -IINF;
        for(int i = 1; i<= n; i++){
            for(int j = 1; j<= n; j++){
                long cur = g[i][j];
                ans = Math.max(ans, cur);
                for(int d = 1; Math.max(i, j)+d <= n && Math.min(i, j) > d; d++){
                    cur += d1[i-1][j+d-1]-d1[i-d][j];
                    cur += d1[i+d-1][j-1]-d1[i][j-d];
                    cur += d2[i-1][j-d+1]-d2[i-d][j];
                    cur += d2[i+d-1][j+1]-d2[i][j+d];
                    
                    cur += g[i][j+d]+g[i][j-d]+g[i-d][j]+g[i+d][j];
                    ans = Math.max(ans, cur);
                }
            }
        }
        pn(ans);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    long IINF = (long)1e18, mod = (long)1e9+7;
    final int INF = (int)1e9, MX = (int)2e6+5;
    DecimalFormat df = new DecimalFormat("0.0000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
    static boolean multipleTC = true, memory = false, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        if(fileIO){
            in = new FastReader("C:/users/user/desktop/inp.in");
            out = new PrintWriter("C:/users/user/desktop/out.out");
        }else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();
        for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}
 
    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }
 
        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }   
}

A few paragraph breaks would be better. The editorial looks a bit cluttered.
Also, there is no requirement of bullets for every section.

I edited it. Does it look fine now?

2 Likes

Isn’t this problem the same as the Max 2d range sum problem, but just that the square is tilted? If yes, this editorial could be made much clearer by linking that technique for most of the explanation and just giving an overview of the implementation.

Also, how did you make those diagrams?

I guess both are different.
In Max 2d range sum, we fix the ends and use Kadane’s.

But here we fix the center and add layer by layer to get a bigger diamond and no Kadane’s algorithm.

Ah. The preferred solution lies in your hands. However I believe the problem can be solved using kadane’s algo, something many more people are familiar with. There is nothing wrong in whichever approach you choose as long as the solution is clear and simple to understand.

All other illustrations for contest and editorials were made in Adobe Ilustrator.
But for this one, the editorialist used MS Word.

1 Like

Can someone please explain how in the below example:

-1 1
1 1

produce a maximum energy of 1?

As per my understanding, the maximum energy should be [-1+1+1+1] = 2. These 4 cells form a diamond?

1 Like

No, these four cells don’t form a diamond. Look at the image provided in the editorial for clarification.

Can you please explain how?

If 1x1 cell can form a diamond why cant 2x2 cells?

First trace the pattern formed given in the image, the no. of boxes in any size of diamond follows the pattern 1,3,5…upto the max. odd value till n to…5,3,1 and all these rows are having there middle box coincided onto the same y-axis. if you take 2*2 size ,then you are not having any middle box , like in n=3 you are having 2nd as middle box but in n=2 case you can’t say which one is in the middle . therefore for only odd values upto given n in input, diamonds can be formed.