HUNGALGO - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Oleksandr Kulkov

DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
Hungarian algorithm proceeds in steps. Initially you’re given matrix with N rows and N columns.

  1. In the first step you should subtract from each element the smallest element in its row.
  2. In the second step you should do the same with columns.

You’re given a matrix with N rows and N columns with non-negative elements in it. You have to determine if it can be obtained from some matrix via these two steps.

EXPLANATION:
You should note that after you’ve done these 2 steps with non-negative matrix if you’ll try to apply them once again it won’t change the matrix because minimum element in each row and each column will become equal to 0. Thus if matrix may be obtained from some matrix via mentioned 2 steps then it also may be obtained from itself in the same way. Thus you should simply check that minimum element in each column and each row is 0 which means that applying of 2 steps to given matrix won’t change it at all. Possible implementation:

int N;
cin >> N;
int a[N][N], b[N][N];
for(int i = 0; i < N; i++) {
	for(int j = 0; j < N; j++) {
		cin >> a[i][j];
		b[j][i] = a[i][j];
	}
}
bool ok = true;
for(int i = 0; i < N; i++) {
	ok &= *min_element(a[i], a[i] + N) == 0 && 
		  *min_element(b[i], b[i] + N) == 0;
}
cout << (ok ? "YES" : "NO") << endl;

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

2 Likes