[1] Generalization of the problem

Let’s consider a solution to the problem generalized as follows.

Determine if there is an integer sequence \(X=(X_1,X_2,\dots,X_N)\) of length \(N\) that satisfies \(M\) conditions.

The \(i\)-th condition is expressed as follows using length-\(n\) and length-\(m\) integer sequences \(p=(p_1,p_2,\dots,p_n)\) and \(q=(q_1,q_2,\dots,q_m)\):

• The integer sequence \((X_{p_1},X_{p_2},\dots,X_{p_n})\) is lexicographically smaller than the integer sequence \((X_{q_1},X_{q_2},\dots,X_{q_m})\).

The original problem is a special case where \(p=(A_i,A_i+1,\dots,B_i)\) and \(q=(C_i,C_i+1,\dots,D_i)\).

[2] Focusing on the comparison of the first characters

For each condition, if \(p_1=q_1\), we can replace \(p,q\) with \((p_2,p_3,\dots,p_n),(q_2,q_3,\dots,q_m)\). If we repeat this and \(q\) becomes empty, we know that the condition cannot be satisfied, so the answer is No. Also, if \(p\) becomes empty, the condition is always satisfied, so we can ignore it. From now on, we assume that \(p_1\neq q_1\) for each condition.

First, we need \(X_{p_1} \leq X_{q_1}\) for each condition.

Now, we consider a directed graph with \(N\) vertices where an edge is drawn from vertex \(p_1\) to \(q_1\) for each condition.

[2-1] When the directed graph does not have a cycle

In this case, we can set \(X_i\) according to the topological order of the vertices so that \(X_{p_1} < X_{q_1}\) holds. If we set \(X\) in this way, all \(M\) conditions are satisfied, so we know the answer is Yes.

[2-2] When the directed graph has a cycle

Next, consider the case with a cycle in the graph. For two vertices \(u,v\) that belong to the same strongly connected component in the graph, we know that \(X_u=X_v\) is necessary.

Then, for each \(X_{p_i}\) that appears in each condition, we can replace \(p_i\) with the minimum label \(v\) of the vertices that belong to the same strongly connected component as \(p_i\), and this takes into account all the conditions regarding equality (it doesn’t necessarily be the minimum, as long as all the labels of the vertices belonging to the same strongly connected component are replaced with the same label). Also, this decreases the number of different integers appearing as \(p_i,q_i\) (because there is a cycle).

From the above, when the directed graph has a cycle, we can reduce the original problem to a problem of the same type with fewer variables \(X_i\).

[3] Summary

Summarizing the discussion in [2], the problem considered in [1] can be solved by the following algorithm.

1. For each condition, if \(p_1=q_1\), delete \(p_1\) and \(q_1\). If \(q\) becomes empty, print No. If \(p\) becomes empty, remove the condition.

2. Consider a directed graph where an edge is drawn from vertex \(p_1\) to \(q_1\) for each condition. If the graph does not have a cycle, print Yes. If it has a cycle, for each strongly connected component, let \(v_{min}\) be the minimum label of the vertices belonging to the strongly connected component, and replace \(p_i,q_i\) in the conditions with \(v_{min}\). Then go back to 1.

Let’s consider the complexity of this algorithm. First, for the calculation in step 2, we need decomposition into strongly connected components, which can be done in \(O(N+M)\). Next, consider the number of times step 2 is performed. When going back from step 2 to 1, the number of different integers appearing as \(p_i,q_i\) in the conditions decreases, and this number is initially at most \(N\), so step 2 will be performed \(O(N)\) times.

Therefore, this algorithm works in \(O(N(N+M))\), which is sufficiently fast.