PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic programming
PROBLEM:
You have an N\times M grid, each cell of which contains 0, 1, or 2.
The grid is called good if there exist two different right-down paths, both from (1, 1) to (N, M), such that at most A_{i, j} of the two paths cover (i, j).
You can choose a row or column, and ‘upgrade’ every 1 in the chosen row/column to a 2.
Find the minimum number of moves needed to make the grid good.
EXPLANATION:
A cell with 0 cannot be traversed at all, and our operation allows us to upgrade 1’s to 2’s, which means we cannot create any new paths - we can only increase the capacity of some already available cells.
In particular, this means that if no path exists from (1, 1) to (N, M), then nothing we do can create a path at all, so the answer is -1.
In similar fashion, if only one path exists between them, again no solution exists.
So, we assume at least two distinct paths exist from (1, 1) \to (N, M).
(We don’t need to directly check for this just yet - we’ll see why soon.)
In this case the answer is never -1, since we can always choose every row (or every column), thus upgrading every value to 2 and allowing us to choose two existing paths always.
Let’s form two “extreme” paths.
The first one will start at (1, 1), and always prefer moving right if possible. It will move down if and only if moving right is either impossible (due to a 0), or will cause it to become unable to reach (N, M).
The second one is similar, but will instead always prefer moving down over right.
Both paths can be constructed easily by precomputing for cell (i, j) whether it has at least one path that can reach (N, M); this is easily done with a boolean DP.
Observe now that any valid path from (1, 1) \to (N, M) must lie “between” these two extreme paths.
More precisely, consider any diagonal with constant i+j. Any valid path will contain exactly one cell from this diagonal, and it will lie between the cells on this diagonal contained on the two extreme paths.
In particular, if we are able to form both extreme paths, and they are different, then we have \ge 2 paths to (N, M); otherwise there’s \le 1 unique path and the answer is -1.
We thus only need to think about solving when both extreme paths exist.
Call a cell “forced” if it is present on both extreme paths.
This cell must then appear on every valid path.
This forces the value in this cell to be 2, since no matter what both paths we choose will pass through it.
Conversely, if all forced cells have value 2 we can simply take the extreme paths themselves to obtain a valid solution.
So, the problem reduces to finding the minimum number of operations needed to upgrade all forced cells that are 1, to 2.
Let’s create a graph with N+M vertices: one for each row and column.
The row vertices are numbered 1, 2, \ldots, N, and the column vertices are N+1, \ldots, N+M.
If cell (x, y) is a forced cell with value 1, add the edge (x, N+y) to the above graph.
After adding all such edges, observe that performing an operation on the grid is equivalent to picking any one vertex of the new graph we constructed, and essentially deleting all edges incident to it.
So, we want to pick the minimum number of vertices that will allow us to cover all the edges.
This is, by definition, the minimum vertex cover problem.
However, our graph is special: it is bipartite by construction, and also cannot contain any cycles because of where we obtained the edges from (the forced cells), and thus must be a forest.
The minimum vertex cover of a tree can be found in linear time using either dynamic programming or a greedy algorithm, already allowing us to solve the problem quickly.
In fact, with further observation it can be seen that each tree of the forest is a “caterpillar”, i.e. looks like a single long path with some leaves attached to the path.
This allows us to simulate the greedy vertex cover without actually needing to construct the tree or do a full DFS on it, easing implementation.
TIME COMPLEXITY:
\mathcal{O}(NM) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, m; cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){
cin >> a[i][j];
}
auto go = [&](int x, int y, int dx, int dy){
queue <pair<int, int>> q;
vector<vector<bool>> vis(n, vector<bool>(m, false));
if (a[x][y] != 0){
q.push({x, y});
vis[x][y] = true;
}
while (!q.empty()){
auto [u, v] = q.front(); q.pop();
if (u + dx >= 0 && u + dx < n && a[u + dx][v] != 0 && !vis[u + dx][v]){
vis[u + dx][v] = true;
q.push({u + dx, v});
}
if (v + dy >= 0 && v + dy < m && a[u][v + dy] != 0 && !vis[u][v + dy]){
vis[u][v + dy] = true;
q.push({u, v + dy});
}
}
return vis;
};
auto b = go(0, 0, 1, 1);
auto c = go(n - 1, m - 1, -1, -1);
vector <int> f(n + m, 0);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){
if (b[i][j] && c[i][j]){
f[i + j] += 1;
}
}
for (int i = 0; i <= n + m - 2; i++){
if (f[i] == 0){
cout << -1 << "\n";
return;
}
}
vector <pair<int, int>> todo;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){
if (b[i][j] && c[i][j] && (f[i + j] == 1) && a[i][j] == 1){
todo.push_back({i, j});
}
}
bool good = false;
for (int i = 0; i <= n + m - 2; i++){
good |= f[i] > 1;
}
if (!good){
cout << -1 << "\n";
return;
}
int ans = 0;
for (int i = 0; i < todo.size(); i++){
int j = i;
while (j + 1 < todo.size() && (todo[j + 1].first == todo[i].first || todo[j + 1].second == todo[i].second)){
j++;
}
ans += 1;
i = j;
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}