PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
2826
PREREQUISITES:
PROBLEM:
You’re given an N\times N grid. Each cell is either empty or has a snake in it, which will extend one cell in a specified direction each second.
The danger of a path in the grid is the number of cells in the path covered by at least one snake.
Answer Q queries of the following form:
- Given T, find the minimum danger of a path from (1, 1) to (N, N) in the grid at the start of the T-th second.
EXPLANATION:
First, let’s see how we’d answer a single query, for the start of time T.
Suppose we had a boolean N\times N grid A, where A_{i, j} is 1 if a snake covers cell (i, j) and 0 otherwise.
Our task is then to find a path with lowest cost from (1, 1) to (N, N) in this grid, where the cost of a path is the sum of values of the cells we touch, and from each cell we can move up/down/left/right.
This is essentially a graph with N^2 vertices and \leq 4N^2 edges, so dijkstra’s algorithm will solve it in \mathcal{O}(N^2 \log N) time (with somewhat bad constant factor too).
Unfortunately, that’s likely too slow for the given constraints.
To make this faster, we can use the fact that every value is either 0 or 1.
The shortest path in such a graph (where all weights are 0 or 1) can infact be computed in linear time, using 0-1 bfs.
In our case, that translates to an algorithm that’s \mathcal{O}(N^2) since there are \mathcal{O}(N^2) edges and vertices.
We now have two tasks: adapting this idea to multiple queries, and actually finding the boolean grid A quickly for each query.
Solving multiple queries
There can be upto 2\cdot 10^5 queries, and we certainly can’t afford to run the \mathcal{O}(N^2) algorithm for each of them.
However, we don’t need to!
Notice that the grid A doesn’t actually change starting from T = N, because every snake would’ve definitely hit the edge of the grid within N-1 moves.
So, the answer for T \gt N is the same as the answer for T = N.
In other words, we only really care about the answers for T = 1, 2, 3, \ldots, N.
That’s only N values of T, each taking \mathcal{O}(N^2) time; so we can precompute them all in \mathcal{O}(N^3) time.
Then, queries can be answered in \mathcal{O}(1) each using the precomputed answers.
Computing grid A
Here, we’ll still use the fact that we only need to deal with N instants of time.
The most ‘natural’ algorithm to compute A at time T is the following:
For each cell (i, j) with a snake, extend it T-1 steps in its respective direction.
This ‘bruteforce’ algorithm can take upto \mathcal{O}(N^3) time however, for example if there were close to N^2 snakes and T = N; and doing this for each T would result in a \mathcal{O}(N^4) algorithm which is too slow.
However, it’s not hard to optimize this.
Notice that when moving from T to T+1, each snake moves only one step forward.
So, let’s store two things: the current grid A, and the current ‘head’ of each snake (along with its direction).
Then, to update the grid A, just move each head one step forward.
There are at most N^2 heads, and we do this only for T = 1, 2, 3, \ldots, N, so the total time taken is \mathcal{O}(N^3).
There are other ways to compute A too.
For example, you could precompute, for each cell, the first time instant it becomes a 1 (which requires finding the closest L to its right, the closest D above it, and so on). This can be done in \mathcal{O}(N^2) time.
Then, for a given T, A_{i, j} = 1 if and only if this first instant is \lt T which is easy to see.
TIME COMPLEXITY
\mathcal{O}(N^3 + Q) per testcase.
CODE:
Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
map<char, array<int, 2>> mp;
mp['U'] = {-1, 0};
mp['D'] = {1, 0};
mp['R'] = {0, 1};
mp['L'] = {0, -1};
int n, q; cin >> n >> q;
vector<string> grid(n);
for (int i = 0; i < n; ++i)
cin >> grid[i];
vector first(n, vector(n, n*n + 5));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '.') continue;
auto [dx, dy] = mp[grid[i][j]];
int x = i, y = j;
for (int k = 0; k <= n; ++k) {
first[x][y] = min(first[x][y], k);
x += dx, y += dy;
if (min(x, y) < 0 or max(x, y) >= n) break;
}
}
}
vector<array<int, 2>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
auto bfs = [&] (int t) {
vector dist(n, vector(n, n*n + 5));
dist[0][0] = first[0][0] <= t;
deque<array<int, 2>> qu; qu.push_back({0, 0});
while (!qu.empty()) {
auto [x, y] = qu.front(); qu.pop_front();
for (const auto &[dx, dy] : dir) {
int nx = x + dx, ny = y + dy;
if (min(nx, ny) < 0 or max(nx, ny) >= n) continue;
int cost = first[nx][ny] <= t;
if (dist[nx][ny] > dist[x][y] + cost) {
dist[nx][ny] = dist[x][y] + cost;
if (cost == 0) qu.push_front({nx, ny});
else qu.push_back({nx, ny});
}
}
}
return dist[n-1][n-1];
};
vector<int> ans(n+2);
for (int i = 0; i <= n+1; ++i) {
if (i > 0 and ans[i-1] == 2*n-1) ans[i] = ans[i-1];
else ans[i] = bfs(i);
}
while (q--) {
int t; cin >> t;
--t;
cout << ans[min(n+1, t)] << '\n';
}
}