Vanishing Island Editorial

Naive Binary Search

With the sea level rising by 1 mm per year, more land gradually becomes submerged. The first idea that comes to mind is performing a binary search on the different water elevations. In each iteration of the binary search, we can run a sample graph traversal algorithm and check if the number of components in the graph is more than 1.

You can probably guess why this solution is wrong. If you check the sample, you will notice how the number of components in the graph does not strictly increase with the rise in water level. While the island can be divided into multiple sections, a section of the island can also later be fully submerged, thus reducing the number of components and causing this solution to produce an incorrect answer.

Disjoint Set Union (DSU) Solution

To solve this problem efficiently, we need to change our approach. Instead of simulating the water rising over time, we process the grid in reverse: starting from the highest land elevation and working downward while leveraging the DSU data structure.

Solution Approach

1. Sort the Land Cells by Elevation:

   • Ignore initially submerged cells (elevation 0).
   • Group all land cells by elevation and sort them in descending order.

2. Process in Reverse Order:

   • Start from the highest elevation and gradually "activate" cells by considering them as above water.
   • Maintain a Disjoint Set Union (DSU) structure to track connected land components.

3. Union-Find Merging:

   • When a new cell is activated, consider it a new landmass.
   • Merge it with any adjacent activated cells using DSU.
   • Track the number of connected components.

4. Detecting the First Split:

   • At each elevation level, if the number of connected components exceeds 1, record that elevation.
   • Then, mark the highest elevation where the island is first divided.
   • Ensure that all cells with the same elevation are processed before recording the number of partitions.

If no split occurs before complete submersion, return -1.

Complexity Analysis

• Sorting elevations: (O(n^2 \log n^2))
• DSU operations (amortized): (O(1)) per merge
• Total Complexity: Approximately (O(n^2 \log n)), which is efficient for (n \leq 10^4).

Implementation

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define mp make_pair
#define pb push_back

const double pi = acos(-1);
const ll MAX = 2 * 1e5 + 5;
const ll MOD = 998244353;
const ll N = 1e3 + 5;
const ll INF = 1e18 + 5;
const double PI = 4 * atan(1);
const double eps = 1e-7;

ll grid[N][N];
ll n, m, x, y;
bool visited[N][N];

pair<int,int> deltas[4] = {
    {1, 0},
    {0, 1},
    {-1, 0},
    {0, -1}
};


/** DSU with partial persistence */
struct DSU_partial {
    int n, time;
    std::vector<int> par, sz, tim;
    vector<vector<int>> partition_members;
    // Union Find with union by size.
    // "Partially persistent": past states can be seen, but not modified
    // operations in O(log(n))
    DSU_partial(int n) : n(n) {
        par.resize(n + 1);
        tim.resize(n + 1);
        partition_members.resize(n + 1);
        for(int i=0;i<n+1;i++){
            partition_members[i].push_back(i);
        }
        sz = std::vector<int>(n + 1, 1);
        iota(par.begin(), par.end(), 0);
    }

    // find leader of current component on time t
    int find(int x, int t = INT_MAX) {
        return par[x] == x || tim[x] > t ? x : find(par[x], t);
    }

    // Is x and y connected on time t
    bool connected(int x, int y, int t = INT_MAX) {
        return find(x, t) == find(y, t);
    }

    // merge two components
    // returns whether they dont already belong to the same
    inline bool merge(int u, int v, int t=0) {
        u = find(u), v = find(v);
        if (u == v) return false;

        if (sz[u] > sz[v]) std::swap(u, v);
        par[u] = v;
        tim[u] = t;
        sz[v] += sz[u];

        partition_members[v].insert(
            partition_members[v].end(), 
            partition_members[u].begin(),
            partition_members[u].end());
        
        return true;
    }

    int static compressCoordinates(pair<int,int> coord, int width){
        return coord.first * width + coord.second;
    }
};

inline bool isValid(const pair<int, int> cell, const int n, const int m){
    return 0 <=cell.first && cell.first < n 
            && 0 <=cell.second && cell.second < m;
}

void solve()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> grid[i][j];
            assert(0 <= grid[i][j] && grid[i][j] <= 1e9);
        }
    }
    
    map<ll, vector<pair<int,int>>> landCells;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if(grid[i][j] == 0)
                continue;
            landCells[grid[i][j]].push_back({i,j});
        }
    }
    vector<ll> distinctElevations;
    for(auto [elevation, cellsWithSameElevation] : landCells){
        distinctElevations.push_back(elevation);
    }
    sort(distinctElevations.rbegin(), distinctElevations.rend());
    
    ll ans = -1;
    DSU_partial dsu(n*m);

    ll islands = 0;

    ll highestElevationAfterSplitting = -1;
    for(auto elevation: distinctElevations){
        auto cellsWithSameElevation = landCells[elevation];

        for(auto currentCell: cellsWithSameElevation){
            islands++;
            for(auto delta: deltas){
                pair<int,int> neighbourCell = {currentCell.first + delta.first, currentCell.second + delta.second};
                if(!isValid(neighbourCell, n, m) 
                    || grid[currentCell.first][currentCell.second] > grid[neighbourCell.first][neighbourCell.second]){
                    continue;
                }
                bool newMerge = dsu.merge(dsu.compressCoordinates(currentCell, m),
                        dsu.compressCoordinates(neighbourCell, m));
                
                if(newMerge){
                    islands--;
                }
            }
        }

        if(islands > 1){
            highestElevationAfterSplitting = elevation;
        }
    }
    
    if(highestElevationAfterSplitting != -1){
        sort(distinctElevations.begin(), distinctElevations.end());
        
        ans = *(--lower_bound(distinctElevations.begin(), distinctElevations.end(), highestElevationAfterSplitting));
    }

    cout<<ans<<endl;
    return;
}

int main()
{
    ll t = 1;

    // cin >> t;
    for (ll i = 1; i <= t; i++)
    {
        solve();
    }
    return 0;
}

Optimized binary search solution

While we proved that the naive binary search solution doesn't work and the intended solution uses DSU, there is a clever way to get around that. The first key observation is introducing the concept of a peak. A peak is group of connected cells (could be one) that have the same elevation, that are not connected and that don't neighbor any other cell with higher elevation than them.

Suppose you know the elevation of all peaks in that island, then you would come up with the following observations:

1. If there is only one peak, that means there is no valid solution.
2. The water elevation required to divide the island into two or more separate landmasses is always lower than the elevation of the smallest peak.
3. If we set the upper bound of the search space to the elevation of the lowest peak, the solution becomes binary searchable!

The tricky part is determining the elevation of different peaks. There are likely multiple efficient ways to achieve this, but since we only care about the lowest elevation peak, here is my proposed approach:

1. Sort cells by elevation (from lowest to highest)
2. Process all cells with the same elevation at once
3. For each component of cells with the same elevation, check whether it forms a peak. This can be done by verifying if any neighboring cell has a higher elevation (a simple graph traversal will suffice). If no such neighboring cell exists, we have found a peak!
4. The first peak we find is, by definition, the lowest elevation peak.

Implementation

I will leave this section up to you 😉!