MIMAX-EDITORIAL

editorial
, , , ,
1

PROBLEM LINK: Click here

Contest: Hey Newbees, Here is Some Honey

Author: Arefin Labib

Co-Author: Samia Rahman

Tester: Nazmus Sakib

Tester: Sanjida Akter

Tester: Redowan Ibrahim

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Math, Implementation

PROBLEM:

Given two nxm and pxq matrix, if you can’t add them print “Syntax error”. Else add them and find the elements that are row wise minimum but column wise maximum and print them space separatly. If there is no such element, print “404 not found”.

Quick Explanation:

If the size of the matrices doesn’t match, print “Syntax error”. Else add them. Iterate row wise over the matrices and find out the elements which are row wise minimum and store it(you can use array or vector etc) Suppose we stored the elements in store1. Then again iterate over column wise, find the maximum elements in each column and store the elements, suppose they are store2. Find the common elements between store1 and store2 and print them(Don’t use setprecision,Why? See explanation). If no such elemnt found, print “404 not found”.

EXPLANATION:

There are enough time so we can discuss the naivest approach.

You know the high school mathematics concept that Two matrices may be added or subtracted only if they have the same dimension; that is, they must have the same number of rows and columns. So first take input the both matrices of nxm and pxq size and check if they have same dimension. If n!=p or m!=q then print “Syntax error”.

If that condition is false, now you have to add the matrices. After adding, Iterate over the matrix row wise and find out the elements that are minimum in their row. Store it. Suppose we have used an array store1.
itr-row
The again iterate over the matrix column wise and find out the elements that are maximum in their column. Store that too. Suppose we have stored it in store2.
itr-col
Now we can find the common elements from store1 and store2 and print them. Follow the pictures denoting the second test case from sample. In store1, 6, 3 and 1 will be stored and in store2, 6, 21 and 23 will be stored. Find the common elements and it is 6 only. If no such element is found, print 404 not found.

You should avoid set_intersection because matrix elements are not bound to be different. They can be same. Suppose a 2x2 matrix of {{0,0},{0,0}}. Then all the elements are row wise minimum and column wise maximum. So the answer is 0 0 0 0. Set_intersection will not give the correct answere here.

TIME COMPLEXITY: O(n^2)

SOLUTIONS:

Co-Author's Solution 
#include<bits/stdc++.h>
#define FastRead                      \
                                    ios_base::sync_with_stdio(false); \
                                    cin.tie(0);
#define ll long long
#define endl "\n"
#define pi acos(-1)
using namespace std;
int main()
{
    FastRead
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll t,k;
    cin>>t;
    for(k=0; k<t; k++)
    {
        ll i,j,n,m,p,q;
        cin>>n>>m;
        ll a[n+5][m+5];
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                cin>>a[i][j];
            }
        }
        cin>>p>>q;
        ll b[p+5][q+5];
        for(i=0; i<p; i++)
        {
            for(j=0; j<q; j++)
            {
                cin>>b[i][j];
            }
        }

        if(n!=p || m!=q)
            cout<<"Syntax error"<<endl;
        else
        {
            ll arr[1005]= {0},s=0,arr1[1005]= {0},s1=0,mn=INT_MAX,mx=INT_MIN,c[n+5][m+5],l,cnt=0;
            for(i=0; i<n; i++)
            {
                for(j=0; j<m; j++)
                {
                    c[i][j]=a[i][j]+b[i][j];
                }
            }
            for(i=0; i<n; i++)
            {
                for(j=0; j<m; j++)
                {
                    mn=min(mn,c[i][j]);

                }
                arr[s++]=mn;
                mn=INT_MAX;
            }
            for(j=0; j<m; j++)
            {
                for(i=0; i<n; i++)
                {
                    mx=max(mx,c[i][j]);

                }
                arr1[s1++]=mx;
                mx=INT_MIN;
            }
            for(j=0; j<m; j++)
            {
                for(i=0; i<n; i++)
                {
                    if(arr[i]==arr1[j])
                    {
                        cout<<arr[i]<<" ";
                        cnt++;
                    }

                }
            }
            if(c!=0)
            cout<<endl;
            if(cnt==0)
                cout<<"404 not found"<<endl;

        }
    }
    return 0;
}
1 Like