ESCN2021 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Div-2 Contest

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

DIFFICULTY:

Easy

PREREQUISITES:

Prefix sum of matrix

PROBLEM:

Given two integers K, W and a matrix A of dimensions N*M with integer elements, such that all the elements are odd numbers, count the number of square submatrices such the sum of the elements in the square submatrix is an even number and is \gt K, print “Ee Sala Cup Namde” if the found count is \geq W, otherwise print “Mundin Sala Cup Namde”.

QUICK EXPLANATION:

Find the sum of all sub-matrices with even length l, i.e. dimension of l*l in a prefix sum matrix of A, and count the number of submatrices which satisfies the condition sum \gt K, and finally check is count \geq W, then print the string “Ee Sala Cup Namde”, otherwise print “Mundin Sala Cup Namde”.

EXPLANATION:

For each cell (x,y) as the top left corner, we try to find the square submatrix with even lengths, such that sum of the elements in the matrix is an even number and \gt K, i.e., we find sum for all the even values of l such that f(x,y,l) = {\sum_{i=x}^{i=x+l-1} \sum_{j=y}^{j=y+l-1} A_{i,j}} \gt K. So if we get f(x,y,l) \gt K, we can increment the count by 1 each time.

  • For all the even values of l we get the sum as an even integer because

    • number of elements = l*l which is always an even number

    • addition of odd integers, even number of times which gives an even integer.

  • f(x,y,l) can be computed in O(1) using prefix sum.

  • Check the condition is count \geq W, if it found to be true, then print “Ee Sala Cup Namde”, else print “Mundin Sala Cup Namde”.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define loopi(i,a,b) for(int i=(a);i<=(b);i++)
#define loopj(j,c,d) for(int j=(c);j<=(d);j++)

vector<vector<ll> > pre;

ll getSum(int top_row, int top_col, int n) {

    int btm_row = top_row + n - 1, btm_col = top_col + n - 1;

    return pre[btm_row][btm_col] - pre[top_row - 1][btm_col] - pre[btm_row][top_col - 1] + pre[top_row - 1][top_col - 1];
}

void solve() {

    ll n, m, k, w;
    cin >> n >> m >> k >> w;

    pre.clear();
    pre.resize(n + 1, vector<ll>(m + 1));

    ll ans = 0;
    loopi(i, 1, n) {

        loopj(j, 1, m) {

            ll a;
            cin >> a;
            pre[i][j] = a + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
        }
    }

    loopi(i, 1, n) {

        loopj(j, 1, m) {

            ll max_order = min(n - i + 1, m - j + 1);
            for(int o = 2; o <= max_order; o += 2) {

                ans += (getSum(i, j, o) > k);
            }
        }
    }

    if(ans >= w) {

        cout << "Ee Sala Cup Namde" << endl;  return;
    }

    cout << "Mundin Sala Cup Namde" << endl;
}

int main(int argc, char const *argv[]) {

    ll t = 1;
    cin >> t;

    loopi(i, 1, t) {

        solve();
    }

    return 0;
}

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