TRACE- Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Hasan Jaddouh
Tester- Jakub Safin
Editorialist- Abhishek Pandey

DIFFICULTY:

CAKEWALK

PRE-REQUISITES:

2-D Matrix, Looping

PROBLEM:

Given a 2-D matrix A, find the maximum trace possible for any possible sub-matrix

QUICK EXPLANATION:

We can, of course, apply brute force to generate every possible sub-matrix and check its trace, and print the maximum trace we found.

There, also exists a linear time solution which will be prime focus of editorial.

EXPLANATION:

This editorial will have 2 parts, the brute force (O({N}^{4})) solution of editorialist and the O({N}^{2}) solution by the setter, @kingofnumbers .

1. Editorialistā€™s approach-

Refer to editorialistā€™s code for this. We will use 3 nested for-loops. The first loop will tell the row number from where our sub-matrix starts. The second loop gives the column number where the sub-matrix starts. The third loop is the length of sub-matrix.

In other words, we will iterate over every cell in the matrix, and check all possible square matrices which can be generated from that cell, and then move to next cell and so on. Every possible sub-matrix is checked, and the maximum trace found is stored in a variable. The code will loop like-

for(i=0;i< n;i++)//Row number { for(j=0;j< n;j++)//Column Number { for(k=0;i+k< n and j+k< n;k++)//Length of Sub-matrix { trace=max(trace,findTrace(i,j,k));//Check trace of every sub-matrix. Print the maximum one. } } }

2. Setterā€™s Approach-

Recall that trace of a matrix is sum of all element son the main diagonal. Now, since all numbers are positive, just think how many cells do we have to actually check?

Note that, my solution checks all possible cells. However, we can prove that the maximum trace is obtained if we start our sub-matrix from either the topmost row or the leftmost column. Can you try to derive/prove this mathematically? A hint will be that all elements are positive. Another hint is given in the image below :slight_smile:

IMAGE

What he does is, that, he only finds trace of the 2n matrices, (my solution found trace of all {N}^{2} matrices). Checkint trace is straightforward looping, which can be seen in the reference solutions. Alternatively, you can, like setter, mathematically find which of the 2n matrix does each element belong to. The setter starts from the top-right corner (whose trace is in mxxx[0] in his solution) and goes linearly to top-left, and from there down to bottom-left, adding values to corresponding traces, and finally printing the maximum one of them.

SOLUTIONS:

For immediate availability of setter and testerā€™s solution, they are also pasted in the tabs below. This is for your reference, and you can copy code from there to wherever you are comfortable reading them. This is to prevent non-availability of solutions (which hinders understanding of editorial) as @admin links the solutions.

Setter

Click to view
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
			
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
 
int mxxx[1111];
int T;
int n;
 
int main(){
	//freopen("00.txt","r",stdin);
	//freopen("00o.txt","w",stdout);
	T=readIntLn(1,100);
	while(T--){
		n=readIntLn(2,100);
		for(int i=0;i<2*n;i++){
			mxxx[i] = 0;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				int h;
				if(j==n-1){
					h=readIntLn(1,100);
				} else {
					h=readIntSp(1,100);
				}
				mxxx[i-j+n-1]+= h;
			}
		}
		int sol=0;
		for(int i=0;i<2*n;i++){
			sol = max(sol,mxxx[i]);
		}
		cout<<sol<<endl;
	}
	assert(getchar()==-1);
} 

Tester

Click to view
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge
 
using cat = long long;
 
#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif
 
int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int T;
	cin >> T;
	for(int t = 0; t < T; t++) {
		int N;
		cin >> N;
		vector< vector<int> > A(N, vector<int>(N));
		for(int i = 0; i < N*N; i++) cin >> A[i/N][i%N];
		int maxsum = 0;
		for(int i = -N; i <= N; i++) {
			int sum = 0;
			for(int s = 0; s <= 2*N; s++) if((s+i)%2 == 0)
				if((s+i)/2 < N && s-i >= 0 && s+i >= 0 && (s-i)/2 < N) 
					sum += A[(s+i)/2][(s-i)/2];
			maxsum = max(maxsum, sum);
		}
		cout << maxsum << "\n";
	}
	return 0;}
 
// look at my code
// my code is amazing

Editorialst

Click to view
/*
 *
 ********************************************************************************************
 * AUTHOR : Vijju123                                                                        *
 * Language: C++14                                                                          *
 * Purpose: -                                                                               *
 * IDE used: Codechef IDE.                                                                  *
 ********************************************************************************************
 *
 Comments will be included in practice problems if it helps ^^
 */
 
 
 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n;
int arr[110][110];
 
//Returns trace. Takes starting point, and length of square sub-matrix as input
int findTrace(int i,int j,int k)
{
    int trace=0,l;
    for(l=0;l<=k;l++)
    {
        trace+=arr[i+l][j+l];
    }
    return trace;
}
 
int main() {
	// your code goes here
	#ifdef JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	while(t--)
	{
	    //input
	    int i,j;
	    cin>>n;
	    
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<n;j++)
	            cin>>arr[i][j];
	    }
	    
	    int k,l,trace=0;
	    for(i=0;i<n;i++)
	    {
	        for(j=0;j<n;j++)
	        {
	            for(k=0;i+k<n and j+k<n;k++)
	            {
	                trace=max(trace,findTrace(i,j,k));//Check trace of every sub-matrix. Print the maximum one.
	            }
	        }
	    }
	    cout<<trace<<endl;
	}
	
	return 0;
}

CHEF VIJJUā€™S CORNER :smiley:

1. Proof of why only 2n matrices suffice-

Click to view

The 2n matrices start from either the top-most row or the left-most column. Now, say, I start my sub-matrix from somewhere else, except these 2 locations. Lets call their trace T. Since the sub-matrix didnt start at the topmost row or the leftmost column, we can clearly say that there exists atleast one element A_{i,j} in diagonally, North-West direction. And they are all positive, so T< T+ \sum_{p=0}^{p=k} A_{i-p,j-p}. Hence, T can never be maximal. This, any sub-matrix not starting from either top-most row, or the leftmost column can never have maximal trace.

2. Estimate the difficulty of problem if sub-matrix did not mean contiguous rows/columns? What if it meant a sub-set of rows and columns?

3. Estimate the difficulty if negative elements were allowed. Can we do better than O({N}^{4}) or O({N}^{3}) in that case? Note that our proof stated in point 1. above will be invalid if elements can be negative.

4. - Pseudo code to calculate trace (editorialistā€™s solution)

Click to view
int findTrace(int i,int j,int k)
{
    int trace=0,l;
    for(l=0;l<=k;l++)
    {
        trace+=arr[i+l][j+l];
    }
    return trace;
}

5. What lies at the end of this box?

Click to view

Compilingā€¦

Click to view

Compilingā€¦

Click to view

Compilingā€¦

Click to view

Compilingā€¦

Click to view

Runningā€¦

Click to view

Runningā€¦

Click to view

Runningā€¦

Click to view

Runningā€¦

Click to view

Runningā€¦

Click to view

RE:SIGSEV

6. Some problems for practicing 2-D Matrices-

Can you please help me out what am I missing out in my solution to this problemā€¦

My code can be found here - https://ideone.com/MObK14

I have used an approach to create a vector of all the possible main diagonals given in the matrix (I have split the longest diagonal into 2 parts as submatrix should be less than the size of original matrix?)

As each number is positive I have just added all the vector elements to check the highest sum.

I donā€™t quite understand what am I missing out on understanding the concept behind this question.

Any help would be highly appreciated.

Thanks

The problem statement clearly said that submatrixā€™s size can be equal to the original matrix, so this step-

 (I have split the longest diagonal into 2 parts as submatrix should be less than the size of original matrix?)

seems wrong to me.

UPDATE 2: I forgot to comment one extra line of push_back that caused the wrong answer

UPDATE: I tried submitting it again and this time it workedā€¦ very very strange :frowning:

But, I even tried that, you can see commented code and even that didnt work out.

Also can you please explain the statement of how submatrix sizeā€™s constraint were given? they seemed very cryptic to meā€¦ It would be great if you could explain them to me please.

Formally, if B is a submatrix of A with size lƗl, then there must be integers r and c (1ā‰¤r,cā‰¤N+1āˆ’l) such that Bi,j=Ar+iāˆ’1,c+jāˆ’1 for each 1ā‰¤i,jā‰¤l.

Also, definition of sub-matrix usually allows the complete matrix. Its like, set and subset. The complete set is also a subset of itself.

Yeah I knew that but this statement confused me a lotā€¦ I even asked in the comments of the question but probably I didnt frame it in a correct way.
Any tips to approach this type of statements? Like how do you prove this (thinking that it might be some special condition and not knowing the set-subset theory thing)

It comes with practice dear. I have dealt with multiple such questions, so I know by experience.

Regarding your comment, you referred that ā€œis the condition something specialā€¦ā€ etc. but I didnt know what were you considering as ā€œnormalā€ and what was ā€œSpecialā€ for you.

Thank you so much for the help!
I learned very important thing by this question, check your code thoroughly for comments etc and if you are having some extra line of code before you submit (that made me struggle for 3 hours where I had come up with a solution in half an hour)

Thanks again!

1 Like

can anyone please help me, whatā€™s wrong with my code-
https://www.codechef.com/viewsolution/18666185

here is my code it is in O(n^2)
use dynamic approach here checkout
https://www.codechef.com/viewsolution/18659127

Try this-

Input
1
4
1 1 100 1
1 1 1 1
1 1 1 1
1 1 1 1
Your Output
102
Expected Output
101

Can anybody tell where my code is going wrong.
Hereā€™s my code- https://www.codechef.com/viewsolution/18677676

another simple to way to code could be

int a[n][n];
int trace[2*n-1];
for(int i=0;i< n;i++) for(int j=0;j< n;j++)
trace[i-j+(n-1)] += a[i][j] // i-j+(n-1) tells the diagnol a[i][j] belong to
ans = max(trace)
Input
1
4
1 1 100 1000
1 1 1 1
1 1 1 1
1 1 1 1
Your Output
101
Expected Output
1000

Setterā€™s solution uses that. Its discussed in editorial :slight_smile:

1 Like

t=int(input())
for _ in range(t):
n=int(input())
a=[]
for i in range(n):
a.append(list(map(int,input().split())))
sum1=a[n-1][0]
for i in range(-(n-2),n):

    suma=0
    if i<0:
        t=i-1
        for k in range(n+i):
            suma+=a[t][k]
            t+=1
        if suma>sum1:
            sum1=suma
    if i>0:
        t=i
        for k in range(n-i):
            suma+=a[k][t]
            t+=1
        if suma>sum1:
            sum1=suma
    if i==0:
        for k in range(n):
            suma+=a[k][k]
        if suma>sum1:
            sum1=suma
print(sum1)

import java.util.*

fun main(args: Array<String>) {
try{
val mTrace=Trace()
    mTrace.start()
}catch(e:Exception){
}
}

class Trace {
    fun start() {
        val mScanner = Scanner(System.`in`)
        var noTestCases = mScanner.nextLine().toInt()
        var maxTrace: Int
        while (noTestCases-- > 0) {
            var matrixLength = mScanner.nextLine().toInt()
            var matrix = Array(matrixLength, { IntArray(matrixLength) })
            maxTrace = 0
            for (i in 0 until matrixLength) {
                var row = IntArray(matrixLength)
                for (j in 0 until matrixLength) {
                    row[j] = mScanner.nextLine().toInt()
                }
                matrix[i] = row
            }

            for (i in 0 until matrixLength) {
                var traceCount = 0
                val x = 0
                val y = i
                for (j in 0 until matrixLength - i) {
                    val currentVal = matrix[x+j][y+j]
                    traceCount += currentVal
                }
                if(traceCount>maxTrace)
                    maxTrace=traceCount
            }

            for (i in 1 until matrixLength) {
                var traceCount = 0
                var x = i
                var y = 0
                for (j in 0 until matrixLength - i) {
                    val currentVal = matrix[x+j][y+j]
                    traceCount += currentVal
                }
                if(traceCount>maxTrace)
                    maxTrace=traceCount
            }
            println(maxTrace)


        }
    }
}

All Cases Working fine.Please tell why its not working.