SQUARE_LOOP - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: wuhudsm
Testers: iceknight1093, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

3312

PREREQUISITES:

Breadth-first search

PROBLEM:

You are given an N\times N grid, each cell of which contains either O or X.
You can move from cell (x_1, y_1) to (x_2, y_2) if they both contain O, and lie in the same row or column.

Answer Q independent queries of the following form:
Given (x, y), set cell (x, y) in the grid to contain X. Then, find the shortest path that starts in the first row, ends in the first row, contains distinct cells, and moves outside the first row at least once.

EXPLANATION:

Ignore the queries for now: let’s see how to compute the answer for a fixed grid.

Of course, the obvious method that comes to mind is to construct the underlying graph and attempt to compute the required quantity in it, perhaps by performing multiple BFS-es.

However, the graph we construct has \mathcal{O}(N^2) vertices and \mathcal{O}(N^3) edges, so performing a BFS \mathcal{O}(N) times on it is infeasible; and certainly it seems impossible to deal with updates to the grid.

Let’s construct a different graph model instead; in fact, one that is a rather standard idea on grid graphs.

Consider a bipartite graph with 2N vertices, with an edge between i and N+j if and only if G_{x, y} is O.
Essentially, 1, 2, 3, \ldots, N represent the rows of the grid, and N+1, \ldots, 2N represent the columns.
Let’s name this graph \Gamma.

Note that any path in the grid corresponds to a path of edges in this graph.

Now, let’s look at the shortest valid path in the grid.
It’s always optimal for the first move to be downwards from the first row, i.e, an edge of the form (1, x) for some x \gt N.
Similarly, it’s always optimal for the last move to be upwards from outside the first row, i.e, another edge of the form (1, y) for y \gt N. Note that y \neq x must also hold since the cells on the path are distinct.

Further, an optimal path will never make two horizontal (or two vertical) moves in a row, since they can be replaced with a single move.
In other words, our sequence of moves looks like vertical \to horizontal \to vertical \to \ldots \to vertical.

Notice that this simply corresponds to a cycle in \Gamma that starts and ends at vertex 1; and in fact, the number of vertices in the path equals the length of the cycle.

So, our aim is to simply compute the shortest cycle passing through vertex 1 in \Gamma.

Finding the shortest cycle through a vertex

Let’s fix a vertex u, and say we want to find the shortest cycle that passes through u in a given graph.

Finding this can be done with BFS in \mathcal{O}(|V| + |E|), as follows:

First, run a BFS from vertex u and compute a BFS tree.
Now, the shortest cycle through u will look like u \to \ldots \to x \to y \to \ldots \to u, where x and y satisfy the following conditions:

  • There is an edge x\to y that is not a tree edge
  • The lowest common ancestor of x and y in the BFS tree is u

The length of such a cycle is, of course, dist(u, x) + dist(u, y) + 1, where the distances can be computed during the BFS.

So, simply check the second condition for every non-tree edge and take the minimum cycle length across all of them that satisfy it.
Note that you don’t need to actually compute the LCA of any pair: the only check that needs to be done is whether x and y lie in the subtrees of different children of u, so for each vertex simply maintain which child’s subtree it lies in.

In the case of our \Gamma, we have 2N vertices and \mathcal{O}(N^2) edges, so this process takes \mathcal{O}(N^2) time.

Dealing with updates

Each update sets one O in the grid to X.
Notice that in terms of \Gamma, this simply correponds to deleting an edge!

Once we find the shortest cycle in \Gamma containing 1, note that it has \leq 2N edges.
If the deleted edge isn’t among them, the answer doesn’t change, since deleting an edge can’t give us a shorter cycle.

Then, for each edge on the shortest cycle, delete it and once again compute the answer for the resulting graph.

This gives us an algorithm in \mathcal{O}(N^3) in total, after which each query is answered in \mathcal{O}(1) time.

TIME COMPLEXITY:

\mathcal{O}(N^3 + Q) per testcase.

CODE:

Setter's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=510;
const int LOGN=11;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n,q,ans_origin;
int  d[N<<1];
int  f[N<<1][LOGN];
char c[N<<1][N<<1];
vector<int> G[N<<1];
map<pair<int,int>,int> tag;

int lca(int x,int y)
{
	if(d[x]>d[y]) swap(x,y);
	for(int i=LOGN-1;i>=0;i--) if(d[f[y][i]]>=d[x]) y=f[y][i];
	if(x==y) return x;
	for(int i=LOGN-1;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}

int solve(vector<int> G[],map<pair<int,int>,int> &tag)
{
	queue<int> Q;
	for(int i=1;i<=n*2;i++) d[i]=f[i][0]=0;
	d[1]=1;
	Q.push(1);
	while(!Q.empty())
	{
		int x=Q.front();
		Q.pop();
		for(int i=0;i<G[x].size();i++)
		{
			int y=G[x][i];
			if(!d[y])
			{
				f[y][0]=x;
				d[y]=d[x]+1;
				Q.push(y);
			}
		}
	}
	for(int i=1;i<LOGN;i++)
		for(int j=1;j<=n*2;j++)
			f[j][i]=f[f[j][i-1]][i-1];
	int mn=INF,U,V;
	for(int i=1;i<=n;i++)
	{
		if(!d[i]) continue;
		for(int j=0;j<G[i].size();j++)
		{
			int u=i,v=G[i][j],l=lca(u,v);
			if(l==u||l==v) continue;
			if(d[l]==1&&d[u]+d[v]-1<mn)
			{
				mn=d[u]+d[v]-1;
				U=u;V=v;
			}
		}
	}
	if(mn==INF) return -1;
	tag[make_pair(U,V)]=1;
	while(f[U][0]) tag[make_pair(min(U,f[U][0]),max(U,f[U][0]))]=1,U=f[U][0];
	while(f[V][0]) tag[make_pair(min(V,f[V][0]),max(V,f[V][0]))]=1,V=f[V][0];
	return mn;
}

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("\n");
		for(int j=1;j<=n;j++) 
		{
			scanf("%c",&c[i][j]); 
			if(c[i][j]=='O')
			{
				G[i].push_back(j+n);
				G[j+n].push_back(i);
			}
		}
	}
	ans_origin=solve(G,tag);
	for(int i=1;i<=q;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(!tag[make_pair(x,y+n)]) printf("%d\n",ans_origin);
		else
		{
			vector<int> G2[N<<1];
			map<pair<int,int>,int> tag2;
			for(int j=1;j<=n;j++)
			{
				for(int k=1;k<=n;k++)
				{
					if(c[j][k]=='O'&&(j!=x||k!=y))
					{
						G2[j].push_back(k+n);
						G2[k+n].push_back(j);
					}
				}
			}	
			printf("%d\n",solve(G2,tag2));
		}
	}
	
	return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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);
	
	int n, q; cin >> n >> q;
	vector<string> grid(n);
	vector adj(2*n, vector<int>());
	for (int i = 0; i < n; ++i) {
		cin >> grid[i];
		for (int j = 0; j < n; ++j) {
			if (grid[i][j] == 'O') {
				adj[i].push_back(n+j);
				adj[n+j].push_back(i);
			}
		}
	}
 
	auto shortest_cycle = [] (auto adj, int src, bool findcyc = false) {
		int sz = adj.size();
		vector<int> dep(sz, INT_MAX), par(sz, -1);
		vector<int> whichch(sz);
		queue<int> q; q.push(src); dep[src] = 0;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int v : adj[u]) {
				if (dep[v] == INT_MAX) {
					dep[v] = 1 + dep[u];
					par[v] = u;
					q.push(v);
					if (u == src) whichch[v] = v;
					else whichch[v] = whichch[u];
				}
			}
		}
		int mincycle = 1e9, x = -1, y = -1;
		for (int i = 0; i < sz; ++i) {
			for (int u : adj[i]) {
				if (i == par[u] or par[i] == u) continue;
				if (whichch[i] == whichch[u]) continue;
				if (mincycle > dep[i] + dep[u] + 1) {
					mincycle = dep[i] + dep[u] + 1;
					x = i, y = u;
				}
			}
		}
		vector<array<int, 2>> edges;
		if (mincycle != INT_MAX and findcyc) {
			edges.push_back({x, y});
			while (x != src) {
				edges.push_back({x, par[x]});
				x = par[x];
			}
			while (y != src) {
				edges.push_back({y, par[y]});
				y = par[y];
			}
		}
		return pair{mincycle, edges};
	};
	
	auto [orig_ans, cycle] = shortest_cycle(adj, 0, true);
	map<array<int, 2>, int> edge_id;
	int id = 1;
	for (auto &[x, y] : cycle) {
		if (x > y) swap(x, y);
		edge_id[{x, y}] = id++;
	}
	vector<int> ans(id);
 
	for (int i = 1; i < id; ++i) {
		auto [u, v] = cycle[i-1];
		auto tmp1 = adj[u], tmp2 = adj[v];
		vector<int> nw1, nw2;
		for (int x : adj[u]) {
			if (x != v) nw1.push_back(x);
		}
		for (int x : adj[v]) {
			if (x != u) nw2.push_back(x);
		}
		adj[u] = nw1; adj[v] = nw2;
		ans[i] = shortest_cycle(adj, 0).first;
		adj[u] = tmp1; adj[v] = tmp2;
	}
 
	while (q--) {
		int x, y; cin >> x >> y;
		--x, --y;
		int out = orig_ans;
		if (edge_id[{x, n+y}]) out = ans[edge_id[{x, n+y}]];
		if (out > 1e8) out = -1;
		cout << out << '\n';
	}
}
1 Like