PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Binary search, segment trees
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.
Define the score of the grid to be the minimum number of moves needed to make the grid good.
You start with an empty grid, and the cells are gradually filled in with either the value 1 or 2.
After each update, compute the score of the grid.
EXPLANATION:
We know how to solve the problem for a fixed grid:
- Compute the two extreme paths, prioritizing right over down for one and down over right for the other.
- Find all cells with a value of 1 that lie on both these paths.
- Solve a minimum vertex cover problem on the rows/columns corresponding to these forced cells; which can be done in linear time because each component is a tree (and in fact almost a line.)
Now we need to process updates that set a 0 to a positive value.
Since the updates only fill in ‘empty’ cells, we only gain flexibility over time.
That means the answer starts out at -1, then eventually will become a positive number, and then over time that positive number will reduce.
This means it’s quite easy to find out when the answer will first not be -1, since we can just binary search over the list of updates and compute the solution for the current grid.
So, we will assume that we are starting from a partially filled grid with positive answer, i.e. it is possible to create two paths from (1, 1) to (N, M) by performing some operations.
As for computing the actual answers, note that the answer depends on the configuration of “forced” cells - however, the set of forced cells will only ever decrease over time as we gain flexibility in paths.
So, we need to be able to compute the minimum vertex cover in a forest graph that constantly loses edges.
There are several ways to do this - one way for example is to exploit the fact that each tree in the forest is a “caterpillar”, i.e. a path with leaves attached to it; which allows us to almost treat it like a line.
This allows us to build a data structure like a segment tree on each caterpillar, and maintain the answer to the greedy vertex cover under constraints of each endpoint being used or not.
With appropriate merging, this allows us to perform point updates in \mathcal{O}(\log(N+M)) time (with a somewhat large constant), which is enough to solve the problem.
For exact implementation details, refer to the code below.
TIME COMPLEXITY:
\mathcal{O}(NM\log(NM) + (N+M)\log(N+M)) time per testcase, though the (N+M)\log(N+M) part has a somewhat high constant factor.
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());
struct node{
int dp[3][3]; // value assuming edges have this value
};
vector <pair<int, int>> arr;
const int N = 2e5 + 69;
int freq[N];
node seg[4 * N];
node merge(node a, node b, int idx){
node c;
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++){
c.dp[i][j] = INF;
}
}
auto cost = [&](int i, int j){
if (j != 0){
if (i != j){
return 1;
} else if (i == j){
if (i == 1 && arr[idx].first != arr[idx + 1].first){
return 1;
}
if (i == 2 && arr[idx].second != arr[idx + 1].second){
return 1;
}
return 0;
}
}
return 0;
};
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++){
for (int k = 0; k < 3; k++){
for (int l = 0; l < 3; l++){
c.dp[i][l] = min(c.dp[i][l], a.dp[i][j] + b.dp[k][l] + cost(j, k));
}
}
}
}
return c;
}
void build(int l, int r, int pos){
if (l == r){
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++){
seg[pos].dp[i][j] = INF;
}
}
for (int i = 0; i < 3; i++){
if (i == 0 && freq[arr[l].first + arr[l].second] == 1){
continue;
}
seg[pos].dp[i][i] = (l == 0 && i != 0);
}
return;
}
int mid = (l + r) / 2;
build(l, mid, pos * 2);
build(mid + 1, r, pos * 2 + 1);
seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1], mid);
}
void upd(int l, int r, int pos, int qp){
if (l == r){
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++){
seg[pos].dp[i][j] = INF;
}
}
for (int i = 0; i < 3; i++){
if (i == 0 && freq[arr[l].first + arr[l].second] == 1){
continue;
}
seg[pos].dp[i][i] = (l == 0 && i != 0);
}
return;
}
int mid = (l + r) / 2;
if (qp <= mid){
upd(l, mid, pos * 2, qp);
} else {
upd(mid + 1, r, pos * 2 + 1, qp);
}
seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1], mid);
}
void Solve()
{
// on the path, assign 0/1/2
// 0 means not using anything
// 1, 2 means using row / column
// answer = number of 1s and 2s not preceded by 1s / 2s / diff row if 1s
// valid iff everything alive covered
int n, m; cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
queue <pair<int, int>> q0, q1;
vector<vector<bool>> v0(n, vector<bool>(m, false));
auto v1 = v0;
for (int i = 0; i < n + m; i++){
freq[i] = 0;
}
int mx = 0;
int cnt = 0;
auto ac = [&](int x, int y){
if (v0[x][y] && v1[x][y]){
freq[x + y]++;
cnt += freq[x + y] == 1;
mx = max(mx, freq[x + y]);
if (freq[x + y] == 2){
// fix the guy
if (arr.size()){
int lo = 0, hi = arr.size() - 1;
while (lo != hi){
int mid = (lo + hi + 1) / 2;
if (arr[mid].first + arr[mid].second <= x + y){
lo = mid;
} else {
hi = mid - 1;
}
}
upd(0, (int)arr.size() - 1, 1, lo);
}
}
}
};
auto add0 = [&](int x, int y){
if (x + y == 0 || (x > 0 && v0[x - 1][y]) || (y > 0 && v0[x][y - 1])){
} else {
return;
}
q0.push({x, y});
v0[x][y] = true;
while (!q0.empty()){
auto [u, v] = q0.front(); q0.pop();
ac(u, v);
if (u + 1 < n && !v0[u + 1][v] && a[u + 1][v] != 0){
v0[u + 1][v] = true;
q0.push({u + 1, v});
}
if (v + 1 < m && !v0[u][v + 1] && a[u][v + 1] != 0){
v0[u][v + 1] = true;
q0.push({u, v + 1});
}
}
};
auto add1 = [&](int x, int y){
if (x + y == n + m - 2 || (x + 1 < n && v1[x + 1][y]) || (y + 1 < m && v1[x][y + 1])){
} else {
return;
}
q1.push({x, y});
v1[x][y] = true;
while (!q1.empty()){
auto [u, v] = q1.front(); q1.pop();
ac(u, v);
if (u > 0 && !v1[u - 1][v] && a[u - 1][v] != 0){
v1[u - 1][v] = true;
q1.push({u - 1, v});
}
if (v > 0 && !v1[u][v - 1] && a[u][v - 1] != 0){
v1[u][v - 1] = true;
q1.push({u, v - 1});
}
}
};
arr.clear();
bool started = false;
for (int i = 0; i < n * m; i++){
int x, y, c; cin >> x >> y >> c;
x--; y--;
a[x][y] = c;
add0(x, y);
add1(x, y);
if (mx <= 1 || cnt != n + m - 1){
cout << -1 << "\n";
} else {
if (!started){
started = true;
for (int r = 0; r < n; r++){
for (int c = 0; c < m; c++){
if (freq[r + c] == 1 && v0[r][c] && v1[r][c] && a[r][c] == 1){
arr.push_back({r, c});
}
}
}
if (arr.size())
build(0, (int)arr.size() - 1, 1);
}
if (arr.size() == 0){
cout << 0 << "\n";
continue;
}
int ans = INF;
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++){
ans = min(ans, seg[1].dp[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;
}