MATMIN1- editorial

Problem link :

matrixmin

Author : kingavrun
Tester : deo002
Editorilist : kingvarun

DIFFICULTY :

Easy

PROBLEM :

Given matrix and a string ,your task is to make all paths of from top left to bottom right of matrix as same as given string by changing elements either in matrix or in string . You have to minimize the cost for making this equal.

EXPLANATION :

We have to store the number of 1 and number of 0 in two different vectors such that we able to maintain the count of 1 and 0 for each step of the all possible paths, than we have minimize the cost by check which is suitable
1 To replace all incorrect elements of matrix by same as string element
2 To change string element and corresponding to that change some matrix elements also,

TIME COMPLEXITY :

O(T * N * M)

Setter Solution

setter solution
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int main()
{
     int t;
     cin >> t;
     while(t--)
 {
	ll n, m, i, j, ans=0, cost1, cost2;

	cin >> n >> m;

	ll a[n][m];
	vector<ll> store1(n+m-1,0) , store0(n+m-1,0);
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < m; j++)
		{		
		    cin >> a[i][j];		
			if(a[i][j]==0)          // storing count of 0 at each step of all paths
				store0[i+j]++;	
			else
				store1[i+j]++;     // storing count of 1 at each step of all paths
		}
	}
	string s;
	cin >> s;
	cin >> cost1 >> cost2;
	for(i = 0; i < n+m-1; i++)
	{
		if(s[i]=='1')
		{
			ans += min((cost1 * store0[i]), ((cost1 * store1[i])+cost2) );  
        }
		else
		{
			ans += min((cost1 * store1[i]), ((cost1 * store0[i])+cost2) );
		}	
	}
	cout << ans << "\n";
 }
return 0;
}
4 Likes