Brief Problem Statement

There are (n) points arranged in a cycle. Each point has (m) parameters; the (j)-th parameter of the (i)-th item is (a_{i,j}). We can maintain a set of tags, where a tag ((j,v)) means that the (j)-th parameter must be (v). Initially, the tag set is empty. The following four moves are allowed:

1. Move right to the nearest point satisfying all tags; if no such point exists, stay at the current point.
2. Move left to the nearest point satisfying all tags; if no such point exists, stay at the current point.
3. Add a tag, and simultaneously move to the nearest point satisfying all tags, including the current point; if no such point exists, the operation is illegal.
4. Delete a tag.

For every ((i,j)), find the minimum number of operations needed to go from (i) to (j).

[ n \le 1000,\quad m \le 4,\quad 1 \le a_{i,j} \le n ]

Idea Analysis

First, it is clear that the current tag set must always satisfy the condition of the current point. Therefore, we enumerate the starting point, build the graph by brute force, and run (\text{BFS}). Specifically, let (dis_s(u,s)) denote the minimum number of operations needed to start from the starting point (s), with the initial tag set empty, and reach point (u) with tag set (s). Then we directly simulate the graph construction.

By observation, we find that the edges produced by the third type of operation are (O(n^2)), so the direct complexity is about (O(n^3 2^m m)). We consider optimizing this.

Following the previous idea, it seems almost impossible to optimize, because from a fixed starting point, the successors of the third type of operation are unordered. Moreover, the bottleneck of the naive approach is that many states have already been visited, but they are still enumerated when we enumerate outgoing edges, causing a large amount of waste. Therefore, we ask: is there an enumeration method that allows us to enumerate all outgoing points of the third type of operation exactly once, without omission, while avoiding already visited states?

Thus, consider doing it in reverse. We enumerate the destination, and maintain operations (1,2,4) symmetrically. Looking back at operation (3), we find a nice property: when we reverse from the current state (s) to (t=s\setminus{j}) ((j\in s)), the legal predecessor points form a contiguous interval on the cycle. Proof: let the current state be ((u,s)), and let (x) be the nearest point to the left of (u) that has the same values as (u) for all parameters in the set (s). Then:

1. For points to the left of (x), when their state is extended by adding the tags in (s), they will pass through (x) first, so they will not pass through (u).
2. For (x) itself, it already satisfies all conditions in (s), so it will not pass through (u).
3. For points on the cycle between (u) and (x), by the definition of (x), there is no point in between that has the same values as (u) for all parameters in the set (s). In particular, the (j)-th parameter of these points must differ from that of (u) (otherwise it would satisfy the full set (s), contradicting that (x) is the nearest point to the left satisfying the (s)-conditions). Therefore, after adding the (j)-th tag of (u), these points will move to (u).

At this point, the natural idea is segment-tree-optimized graph construction, but there is a more clever approach: we use a disjoint-set union (DSU) to maintain the next legal predecessor for the current state. After a point has been enqueued, point it to the nearest point to its left that agrees with (u) on the set (t). This can be preprocessed easily. Then, when running (\text{BFS}) for the third type of operation, we can directly traverse the unvisited points on the chain, and use path compression to optimize. Since each point is traversed at most once in the third type of operation, the complexity of this part is amortized (O(n\alpha(n))), where (\alpha(n)) is the inverse Ackermann function; in practice its constant is very small.

In summary, the time complexity is (O(n^2 2^m m\alpha(n))), and a sufficiently careful implementation can pass this problem.

(translated by deepseek v4.1)