SHERMAT1 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Div-2 Contest

Author: Dharanendra L V
Tester: Dharanendra L V
Editorialist: Dharanendra L V

DIFFICULTY:

Easy

PREREQUISITES:

Basic observations, Square Matrix, 2D Arrays

PROBLEM:

Given a square matrix N \times N matrix having exactly N^2 elements i.e. P(i,j). We can only move to the Cell(i+1,j+1) or Cell(i-1,j-1) and need to find the total maximum sum S by visiting the cells within the boundary of the matrix and the cells which have not been visited yet.

QUICK EXPLANATION:

When we say a diagonal starting from the cell(x, y), which means all the cells (m, n) such that, x - y = m - n. Only cells satisfying these conditions are considered because you can only move diagonally.

EXPLANATION:

You are allowed to go from cell (i,j) to cell (i+1,j+1) or to cell (i-1,j-1). We can consider starting points as first row elements and first column elements and try calculating the value of each possible path you can traverse. Initialize the sum and answer as 0. For each starting cell (i,j), you can go diagonally downwards. First consider all the paths which start at cell (i,j) and end diagonally below it. We keep on adding the value P (i,j) by traversing downwards diagonally and updating the sum, and after each traverse update the answer if the answer is less than the sum. And finally, print the answer.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0); cin.tie(0)
#define test ll t = 1; while (t--)
#define REP(x) for (ll i = 0; i < x; i++)
typedef long long ll;
using namespace std;

int main()
{
    FIO;
    test
    {
        ll n;
        cin >> n;

        ll a[n][n];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> a[i][j];
            }
        }

        ll ans = 0;
        // Iterating with first row elements
        for (int i = 0; i < n; i++)
        {
            ll x = 0, y = i, sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += a[x++][y++];
            }
            if (sum > ans)
                ans = sum;
        }

        // Iterating with first column elements
        for (int i = 1; i < n; i++)
        {
            ll x = i, y = 0, sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += a[x++][y++];
            }
            if (sum > ans)
                ans = sum;
        }

        cout << ans << endl;
    }

    return 0;
}

Feel free to share your approach here. Suggestions are always welcomed. :slight_smile: