# ISLNDHOP - Editorial

Author: Pranav Rajagopalan, Pranav Reddy P
Tester: Alex Danilyuk

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

\mathrm{dp}[x][y] = \begin{cases} \infty & \min(x, y) < 0 \\ 0 & (x, y) \in I_1 \\ \min(\mathrm{dp}[x - 1][y], \mathrm{dp}[x][y - 1]) + 1 & \mathrm{otherwise}\\ \end{cases}

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}};

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;
}

// 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);
}
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)
{
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>;
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;
} 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;
}
} else if (c != col[x][y][0]) {
dist[x][y][1] = d;
col[x][y][1] = c;
}
}

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)
}
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);
}
}

2 Likes

You can also calculate Part 1 in O(n ^ 2) using a multisource bfs from the starting island, which is what my solution does.

Also there is another totally different approach to solving this problem which is what @um_nik’s solution does. Here is a screenshot of the short description I wrote for it during IOITC. (Note that subtasks, constraints and time limits are different, so some parts “passing some subtask” are likely to not match)

1 Like

Also a bit of the story behind this problem. Back near the start of the year when we were holding inductions for our college competitive coding club, we were trying to come up with some slightly tricky problems for the final round. The target for this would have been around Easy in terms of Codechef difficulty as we already 1 or 2 Easy-Mediums. @pranavreddy16 came up with the original problem, the formulation (land / water cells, island definition, Manhattan cost), of which still remains identical in this problem, but asked to find the MST the islands instead. While his problem had n, number of islands \leq 200 for a mutlisource bfs idea, I missed the constraint on the number of islands and spent a while breaking my head before arriving at the "at max 2 valid x_2" idea that is used in Subtask 2 to solve that problem in O(n ^ 3). We ended up removing that problem from the inductions set in the end after even Candidate Masters on our testing team failed to solve it.

Sadly even though none of us realized it at that time, that specific problem could actually be solved pretty trivially in O(n ^ 2) using Euclidian MST. So I set out to try to reformulate the idea in some way to use this observation. My main realization was that what we had was the set of edges on ALL optimal paths between any pairs, not just the MST. After some misadventures on maximum distinct islands in a path and dp on DAGs (which weren’t really acyclic after all), I arrived at the current formulation with an O(n ^ 4) solution.

Around the same time I felt that there must be a way to solve this problem too in O(n ^ 3) by performing the calculations related to the pairs in O(n ^ 2). Well after thinking about optimal rectangles in this problem and going nowhere I stumbled upon the 2 \times n^2 bound by sheer luck. The proof I initially used to reach the bound initially was utterly bogus and on a bit of scrutinization actually derived the bound as 2 \times n which was utter nonsense and the mistake was found soon after.

But no matter how hard I tried I couldn’t come up with a single countercase to the bound in all cases with n \leq 6 and for over 10^7 cases with n \leq 20. In fact the bound seemed fairly tight as I could get answers in excess of 1.95 \times n^2. I stopped worrying too much about the correctness of the bound after @um_nik presented a different O(n ^ 3) solution that didn’t rely on this observation at all. However eventually a week before IOITC I bugged @bhvdsi enough to get him to help me with the proof and he came up with an elegant approach to it. He used the fact that adding a new land cell never reduced the number of optimal rectangles (edges) in the grid along with a complete grid having 2 \times n^2 optimal edges to finally prove the bound. And that’s where it remained till today when @jtnydv25 presented an even more mind bogglingly trivial proof for it while writing the editorial.

Overall its probably the most time I’ve ever spent working and preparing a single problem, and seeing its difficulty rise from a Easy-Medium when initially proposed to Medium-Hard in its current form was fun. Its probably a problem more suited to an actual 5 hour IOI style contest than something like lunchtime due to having a slightly tedious implementation, but I still think the observations needed by both approaches to solve this problem are fairly cool.

PS: I would like to apologize for the suffering faced by anyone who read the utterly confusing statements of the early versions of this problem during IOITC testing.

4 Likes

Thanks for sharing the back-story of the problem! Had a good time reading through it.

Kudos to the authors for this one!

It took me just under two days and 10 attempts to solve it. I especially enjoyed that anyone with some DP and bfs/dfs knowledge could figure it out once they spot the key observation. Really surprised so few people even attempted this one as it packs a neat thought process with it. My implementation was a bit long and heavy like 200+ lines, but I didn’t lose interest in this one for two days which is what I look for in a beautiful problem. Once again, thanks so much!

1 Like