PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Pranav Rajagopalan, Pranav Reddy P
Tester: Alex Danilyuk
Editorialist: Jatin Yadav
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Dynamic Programming, Graphs
PROBLEM:
You have a N \times N grid. Each cell is either a land cell or a water cell. An island is defined as a connected component of land cells. If you are at a land (x, y), he can perform one of two actions:
- Type 1: Move to to some land cell (x', y') that lies on a different island at a cost of | x - x' | + | y - y'|
- Type 2: Move to some land cell that lies on the same island at a cost of 0.
Let the beauty of a sequence of moves be the number of moves of type 1 while traveling from (x_a, y_a) to (x_b, y_b). We define the simple cost as the minimum cost of a sequence with \mathrm{beauty} \leq 1.
What is the maximum possible beauty of a sequence of cells going from (x_a,y_a) to (x_b, y_b) without exceeding the simple cost? Find the answer for every possible land cell (x_b, y_b).
EXPLANATION:
The problem can be divided into two parts. The first part is to find the simple cost for each possible land cell, and the second is to find the maximum possible beauty for each land cell.
Part 1 : Computing the simple costs
First, find the connected components (that is, the islands), say I_1, I_2, \ldots, I_k. WLOG, assume (x_a, y_a) \in I_1.
Define D_r to be the minimum manhattan distance between a cell in I_r and a cell in I_1. For any cell in I_r, the simple cost is D_r, because within an island we can move with cost 0 using type 2 moves.
Let’s compute for each cell (x, y) the smallest manhattan distance to a cell in I_1. Then, D_r can be found by taking minimum over all cells in island I_r. There are multiple ways to find the smallest distances. We can precompute all minimum distances in O(N^2) by dividing into 4 possibilities based on the signs of \Delta x and \Delta y. For each possibility, we can do a simple DP. for example if we are finding the minimum distance of (x, y) to cells (x_1, y_1) \in I_1 with x_1 \le x, y_1 \le y. Then, we have
Thus, all the simple costs can be precomputed in O(N^2).
Code
vector<vector<int>> dist(4, vector<int>(n * m, INF));
vector<int> dx2 = {1, 1, -1, -1}, dy2 = {-1, 1, -1, 1};
function<int(int, int, int)> getClosest = [&](int dir, int x, int y){
if(min(x, y) < 0 || x >= n || y >= m) return INF;
int id = m * x + y;
if(islandID[id] == capital) return 0;
if(dist[dir][id] != INF) return dist[dir][id];
return dist[dir][id] = min(getClosest(dir, x + dx2[dir], y),
getClosest(dir, x, y + dy2[dir])) + 1;
};
for(int i = 0; i < n * m; i++){
int island = islandID[i];
for(int dir = 0; dir < 4; dir++){
D[island] = min(D[island], getClosest(dir, i / m, i % m));
}
}
Part 2 : Computing Maximum Beauty
Define \mathrm{dp}[d][x][y] to be the maximum beauty of a path that ends at the cell (x, y) having cost \le d. Also, define \mathrm{dp}_2[d][x][y] to be the maximum beauty of a path that ends at the cell (x, y) having cost \le d, such that the last move was of type 1.
Then, \mathrm{dp}[d][x][y] equals the maximum of \mathrm{dp}_2[d][x'][y'] over all cells (x', y') in the same island as (x, y).
\mathrm{dp}_2[d][c] = 1 + \max (\mathrm{dp}[d - |x - x'| - |y - y'|][x'][y']) over all (x', y') belonging to a different island than (x, y).
The answer for a cell (x, y) equals \mathrm{dp}[s][x][y], where s is its simple cost. Since all simple costs are <2N, we have a total of O(N^3) dp states.
Also, computing a state takes O(N^2) time as we have to iterate over (x', y'). This gives an O(N^5) algorithm, which is enough to pass subtask 1.
To optimize, we observe that there exists an optimal solution in which the following holds:
Consider any move of type 1 from (x_1, y_1) to (x_2, y_2). Then, there is no land cell other than (x_1, y_1) and (x_2, y_2) in their bounding rectangle.
If there was some other cell in their bounding rectangle, say (x, y), then we could have gone (x_1, y_1) \rightarrow (x, y) \rightarrow (x_2, y_2) without increasing the cost or decreasing the beauty. This is because the beauty contributed by the two moves is atleast 1 as (x, y) cannot lie on the same island as both (x_1, y_1) and (x_2, y_2). Also, the manhattan distance between (x_1, y_1) and (x_2, y_2) is the same as the sum of the distances from (x, y) to (x_1, y_1) and (x_2, y_2), so the cost has also not increased.
Let’s call a move (x_1, y_1) \rightarrow (x_2, y_2) valid if it satisfies the bounding rectangle property above. We will prove that there are O(N^2) valid moves.
First, for any (x_1, y_1) and y_2, there can be at max 2 valid x_2, the closest land cells above and below (x_1, y_2) . This observation leads to an O(N^4) solution, which passes subtask 2.
Consider any row i. Say there are land cells at columns j_1, j_2, \ldots j_t in this row. Also, define j_0 = 0, j_{t+1} = N + 1. Then for any land cell (i, j_r), only the cells in columns in range [j_{r-1}, j_{r+1}] can be valid. Also, we already showed that there are O(1) valid moves to a given column from any cell. Thus, the total number of valid moves from (i, j_r) is O(j_{r+1} - j_{r-1} + 1). Clearly, as we sum over all r, this is O(N). This means there are O(N) valid moves from any row, and hence O(N^2) valid moves overall.
So, if we precompute the closest cells above and below every cell, we can traverse all the valid transactions in O(N^2) for every dp layer. As there are O(N) layers, total time complexity is O(N^3).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using pii=std::pair<int,int>;
using namespace std;
const int maxn = 401;
const int maxpoints = maxn * maxn, maxislands = maxn * maxn, maxdist = 2 * maxn;
int t, n, fromx, fromy, grid[maxn][maxn], base_island[maxn][maxn], dp[maxdist][maxislands], simple_cost[maxislands], ans[maxislands], closest[maxn], dist[maxn][maxn], visited[maxn][maxn];
pii dirs[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<pii> adj[maxislands];
int is_valid(int x, int y)
{
return (x >= 0 && x < n && y >= 0 && y < n);
}
void dfs(int x, int y, int island_idx)
{
visited[x][y] = 1;
base_island[x][y] = island_idx;
for(auto ne : dirs)
{
int nex = x + ne.first;
int ney = y + ne.second;
if(is_valid(nex, ney) && grid[nex][ney] && !visited[nex][ney])
dfs(nex, ney, island_idx);
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for(int cases = 0; cases < t; cases++)
{
cin >> n;
for(int i = 0; i < n; i++)
{
string s;
cin >> s;
for(int j = 0; j < n; j++)
{
grid[i][j] = s[j] - '0';
base_island[i][j] = -1;
visited[i][j] = 0;
dist[i][j] = maxdist;
}
closest[i] = -1;
}
// Merge islands
int island_cnt = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(grid[i][j] && !visited[i][j])
dfs(i, j, island_cnt++);
for(int i = 0; i < island_cnt; i++)
{
ans[i] = 0;
simple_cost[i] = 2 * maxn;
adj[i].clear();
}
// Find the k <= 2 * n^2 optimal edges
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(grid[i][j] == 1)
{
int from_island = base_island[i][j];
int curhas = -1;
for(auto dir: {-1, 1})
{
for(int k = j; k >= 0 && k < n; k += dir)
if(closest[k] > curhas)
{
if(base_island[closest[k]][k] != from_island)
{
int to_island = base_island[closest[k]][k];
int curdist = abs(closest[k] - i) + abs(k - j);
adj[from_island].push_back({to_island, curdist});
adj[to_island].push_back({from_island, curdist});
}
curhas = closest[k];
}
curhas = closest[j];
}
closest[j] = i;
}
cin >> fromx >> fromy;
fromx--; fromy--;
int from_island = base_island[fromx][fromy];
// Multisource bfs from source island to find min cost
// to each island using at most a single flight
queue<tuple<int, int>> q;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(grid[i][j] == 1 && base_island[i][j] == from_island)
{
dist[i][j] = 0;
q.push({i, j});
}
while(!q.empty())
{
int curx, cury;
tie(curx, cury) = q.front();
if(grid[curx][cury])
simple_cost[base_island[curx][cury]] = min(simple_cost[base_island[curx][cury]], dist[curx][cury]);
q.pop();
for(auto ne : dirs)
{
int nex = curx + ne.first;
int ney = cury + ne.second;
if(is_valid(nex, ney) && dist[nex][ney] > dist[curx][cury] + 1)
{
dist[nex][ney] = dist[curx][cury] + 1;
q.push({nex, ney});
}
}
}
// Main dp, O(n ^ 3) states.
// Number of edges / transistions is 2 * n^2 per layer.
// There are a total of 2 * n layers, so O(n ^ 3) total.
for(int cost = 0; cost < 2 * n; cost++)
for(int j = 0; j < island_cnt; j++)
dp[cost][j] = -1;
dp[0][from_island] = 0;
for(int cost = 0; cost < 2 * n; cost++)
for(int j = 0; j < island_cnt; j++)
if(dp[cost][j] != -1)
for(auto x : adj[j])
{
int to_island = x.first;
int move_cost = x.second;
if(cost + move_cost < 2 * n)
dp[cost + move_cost][to_island] = max(dp[cost + move_cost][to_island], dp[cost][j] + 1);
}
// Take best answer for each island with cost <= simple_cost
for(int j = 0; j < island_cnt; j++)
for(int cost = 0; cost < 2 * n; cost++)
if(cost <= simple_cost[j])
ans[j] = max(ans[j], dp[cost][j]);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cout << ((grid[i][j]) ? ans[base_island[i][j]] : 0) << " ";
cout << "\n";
}
}
return 0;
}
Tester's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int INF = 1001001;
const int N = 303;
const int M = N * N * 2;
const int T = 2 * N;
const int DX[] = {-1, 1, 0, 0};
const int DY[] = {0, 0, -1, 1};
int n;
char s[N][N];
int id[N][N];
int dist[N][N][2];
int col[N][N][2];
bool used[N][N][2];
int Q[T];
pii QQ[M * 10];
int prv[M * 10];
int sz;
int ans[M];
int maxDist[M];
int curDist[M];
int m;
int V;
bool checkCell(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < n;
}
void dfs(int x, int y) {
id[x][y] = m;
for (int i = 0; i < 4; i++) {
int xx = x + DX[i], yy = y + DY[i];
if (!checkCell(xx, yy) || id[xx][yy] != -1 || s[xx][yy] == '0') continue;
dfs(xx, yy);
}
}
void addQ(int d, pii val) {
QQ[sz] = val;
prv[sz] = Q[d];
Q[d] = sz++;
}
void tryUpd(int x, int y, int d, int c) {
if (d >= dist[x][y][1]) return;
if (d < dist[x][y][0]) {
if (c == col[x][y][0]) {
dist[x][y][0] = d;
addQ(d, mp(x, y));
} else {
dist[x][y][1] = dist[x][y][0];
col[x][y][1] = col[x][y][0];
dist[x][y][0] = d;
col[x][y][0] = c;
addQ(d, mp(x, y));
}
} else if (c != col[x][y][0]) {
dist[x][y][1] = d;
col[x][y][1] = c;
addQ(d, mp(x, y));
}
}
void bfs() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < 2; k++)
used[i][j][k] = 0;
sz = 0;
for (int i = 0; i < T; i++)
Q[i] = -1;
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++)
for (int k = 0; k < 2; k++) {
if (dist[x][y][k] < T)
addQ(dist[x][y][k], mp(x, y));
}
for (int d = 0; d < T - 1; d++) {
while(Q[d] != -1) {
int x = QQ[Q[d]].first;
int y = QQ[Q[d]].second;
Q[d] = prv[Q[d]];
for (int k = 0; k < 2; k++) {
if (used[x][y][k] || dist[x][y][k] != d) continue;
used[x][y][k] = 1;
int c = col[x][y][k];
for (int i = 0; i < 4; i++) {
int xx = x + DX[i], yy = y + DY[i];
if (!checkCell(xx, yy)) continue;
tryUpd(xx, yy, d + 1, c);
}
}
}
}
}
void solve() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%s", s[i]);
m = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
id[i][j] = -1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (id[i][j] != -1) continue;
if (s[i][j] == '0') continue;
dfs(i, j);
m++;
}
int x, y;
scanf("%d%d", &x, &y);
V = id[x - 1][y - 1];
assert(V != -1);
for (int i = 0; i < m; i++) {
ans[i] = 0;
maxDist[i] = INF;
curDist[i] = INF;
}
curDist[V] = 0;
for (int t = 1; t <= n; t++) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
for (int k = 0; k < 2; k++) {
dist[i][j][k] = INF;
col[i][j][k] = -1;
}
if (id[i][j] != -1 && curDist[id[i][j]] < INF) {
dist[i][j][0] = curDist[id[i][j]];
col[i][j][0] = id[i][j];
}
}
bfs();
if (t == 1) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (id[i][j] == -1) continue;
maxDist[id[i][j]] = min(maxDist[id[i][j]], dist[i][j][0]);
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (id[i][j] == -1 || id[i][j] == V) continue;
int k = 0;
if (col[i][j][k] == id[i][j]) k++;
if (dist[i][j][k] <= maxDist[id[i][j]]) {
ans[id[i][j]] = t;
}
}
for (int i = 0; i < m; i++)
curDist[i] = INF;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (id[i][j] == -1) continue;
int k = 0;
if (col[i][j][k] == id[i][j]) k++;
curDist[id[i][j]] = min(curDist[id[i][j]], dist[i][j][k]);
}
bool fnd = false;
int val = INF;
for (int i = 0; i < m; i++)
val = min(val, curDist[i]);
for (int i = 0; i < m; i++)
fnd |= val < maxDist[i];
if (!fnd) break;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int w = 0;
if (id[i][j] != -1) w = ans[id[i][j]];
printf("%d ", w);
}
printf("\n");
}
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
void getMaxFlights(vector<string> type, int src_x, int src_y){
const int INF = 1 << 29;
vector<int> dx = {-1, 1, 0, 0};
vector<int> dy = {0, 0, 1, -1};
int n = type.size();
int m = type[0].size();
int src = src_x * m + src_y;
vector<vector<int>> islands, down(n, vector<int>(m));
vector<vector<int>> up = down, up2 = down, down2 = down;
vector<int> D(n * m + 1, INF), vis(n * m), islandID(n * m, n * m), cells;
function<void(int, int)> dfs = [&](int u, int v){
int I = u * m + v;
cells.push_back(I);
vis[I] = 1;
islandID[I] = islands.size();
for(int dir = 0; dir < 4; dir++){
int i = u + dx[dir], j = v + dy[dir];
if(min(i, j) >= 0 && i < n && j < m && type[i][j] == '1'){
if(!vis[i * m + j]){
dfs(i, j);
}
}
}
};
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(type[i][j] == '1' && !vis[i * m + j]){
cells.clear();
dfs(i, j);
islands.push_back(cells);
}
}
int capital = islandID[src];
int k = islands.size();
for(int j = 0; j < m; j++){
int pos2 = -1;
for(int i = 0; i < n; i++){
up2[i][j] = pos2;
if(type[i][j] == '1') pos2 = i;
up[i][j] = pos2;
}
pos2 = -1;
for(int i = n - 1; i >= 0; i--){
down2[i][j] = pos2;
if(type[i][j] == '1') pos2 = i;
down[i][j] = pos2;
}
}
vector<vector<int>> dist(4, vector<int>(n * m, INF));
vector<int> dx2 = {1, 1, -1, -1}, dy2 = {-1, 1, -1, 1};
function<int(int, int, int)> getClosest = [&](int dir, int x, int y){
if(min(x, y) < 0 || x >= n || y >= m) return INF;
int id = m * x + y;
if(islandID[id] == capital) return 0;
if(dist[dir][id] != INF) return dist[dir][id];
return dist[dir][id] = min(getClosest(dir, x + dx2[dir], y), getClosest(dir, x, y + dy2[dir])) + 1;
};
for(int i = 0; i < n * m; i++){
int island = islandID[i];
for(int dir = 0; dir < 4; dir++){
D[island] = min(D[island], getClosest(dir, i / m, i % m));
}
}
vector<vector<int>> dp(2 * (n + m), vector<int>(k, -INF));
dp[0][capital] = 0;
for(int d = 0; d + 1 < n + m; d++){
for(int i = 0; i < k; i++)
dp[d + 1][i] = max(dp[d + 1][i], dp[d][i]);
for(int u = 0; u < n; u++){
int lft = 0;
for(int v = 0; v < m; v++) if(type[u][v] == '1'){
int uv = u * m + v;
int id = islandID[uv];
int val = dp[d][id];
if(val < 0){
lft = v;
continue;
}
for(int r = lft; r < m; r++){
int rv = abs(r - v);
int x = up[u][r], _x = down[u][r];
if(r == v) x = up2[u][r], _x = down2[u][r];
if(x != -1){
int xr = islandID[x * m + r];
if(xr != id){
int d2 = d + u - x + rv;
dp[d2][xr] = max(dp[d2][xr], val + 1);
}
}
if(_x != -1){
int xr = islandID[_x * m + r];
if(xr != id){
int d2 = d + _x - u + rv;
dp[d2][xr] = max(dp[d2][xr], val + 1);
}
}
if(r > v && type[u][r] == '1') break;
}
lft = v;
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int id = islandID[i * m + j];
cout << (type[i][j] == '1' ? dp[D[id]][id] : 0) << " ";
}
cout << endl;
}
}
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(0);
int t; cin >> t;
while(t--){
int n; cin >> n;
vector<string> type(n);
for(int i = 0; i < n; i++) cin >> type[i];
int a, b, c, d;
cin >> a >> b;
getMaxFlights(type, a - 1, b - 1);
}
}
