for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    if k * 2 > n:
        print(-1)
        continue
    ans = 0
    for i in range(k):
        ans += int(s[i] != 'R') + int(s[n - i - 1] != 'L')
    print(ans)

for _ in range(int(input())):
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    for i in range(n):
        a[i] -= c
    for i in range(n // 2):
        a[i] = max(a[i], 0)
    print(sum(a))

for _ in range(int(input())):
    n, k = map(int, input().split())
    if n == 1:
        if k == 1:
            print("YES")
            print(0)
        else:
            print("NO")
        continue
    k ^= n
    if k.bit_length() > (n - 1).bit_length():
        print("NO")
        continue
    s = list()
    if 0 < k <= n - 1:
        s.append(k)
    elif k:
        s.append(n - 1)
        s.append((n - 1) ^ k)
    s.append(0)
    a = s[:]
    for i in range(n):
        if i not in s:
            a.append(i)
    print("YES")
    print(*reversed(a))

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    i64 x, y;
    std::cin >> x >> y;
    i64 min = 1e18, p, q;
    auto upd = [&](i64 _p, i64 _q) -> void {
        if ((_p & _q) == 0 && abs(_p - x) + abs(_q - y) < min) {
            min = abs(_p - x) + abs(_q - y);
            p = _p;
            q = _q;
        }  
    };
    upd(x, y);
    for (int i = 29; i >= 0; i--) {
        if ((x & y) >> i & 1) {
            upd((x >> i << i) + (1LL << i), y);
            upd(x, (y >> i << i) + (1LL << i));
            upd(x >> i << i, (y >> i << i) - 1);
            upd((x >> i << i) - 1, y >> i << i);
        }
    }
    std::cout << p << " " << q << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}

What is the optimal strategy for both players?

If you have obtained a formula for $$$f(x,y)$$$, how do you calculate the required sum efficiently, perhaps using some tree techniques?

#include <bits/stdc++.h>
 
using namespace std;
 
using i64 = long long;
 
i64 solve_tree(int n, int r, vector<vector<int>> g) {
    vector<int> dep(n), sz(n, 1), pa(n);
    i64 ans = 0;
    auto dfs = [&](auto &&self, int u, int p) -> map<int, int> {
        pa[u] = p;
        map<int, int> mp;
        mp[dep[u]] = 1;
        for (auto v : g[u]) if (v != p) {
            dep[v] = dep[u] + 1;
            auto nmp = self(self, v, u);
            if (mp.size() < nmp.size()) swap(mp, nmp);
            for (auto &[d, f] : nmp) {
                ans += 1LL * f * mp[d] * (d - dep[u]);
                mp[d] += f;
            }
            sz[u] += sz[v];
        }
        return mp;
    };
    dfs(dfs, r, -1);
    for (int u = 0; u < n; u++) {
        i64 s = 1LL * sz[u] * (sz[u] - 1) / 2;
        for (auto v : g[u]) if (v != pa[u]) s -= 1LL * sz[v] * (sz[v] - 1) / 2;
        ans -= 1LL * dep[u] * s;
    }
    sort(dep.begin(), dep.end());
    for (int u = 0; u < n; u++) ans += 1LL * dep[u] * (n - u - 1);
    return ans;
}
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n - 1; i++) a[i] = i + 1;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        a[u] = max(a[u], v);
    }
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) g[a[i]].push_back(i);
    cout << solve_tree(n, n - 1, g) << "\n";
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) solve();
}

Solve the problem in $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

using B = bitset<100001>;

using i64 = long long;
using i128 = __int128_t;

constexpr i64 MOD = 998244353;

vector<i64> calc(int n, string &s, i64 x, i64 y) {
    B bf0, bf1, br0, br1;
    bf0.set(0);
    br0.set(0);
    for (auto c : s) {
        B nbf0, nbf1, nbr0, nbr1;
        if (c != '1') {
            nbf0 |= bf0 << 1;
            nbf1 |= bf1 << 1;
            nbr0 |= br0 >> 1;
            nbr1 |= br1 >> 1;
        }
        if (c != '0') {
            nbf0 |= br1;
            nbf1 |= br0;
            nbr0 |= bf1;
            nbr1 |= bf0;
        }
        nbf0[0] = nbf0[0] | nbr0[0];
        nbr0[0] = nbr0[0] | nbf0[0];
        nbf1[0] = nbf1[0] | nbr1[0];
        nbr1[0] = nbr1[0] | nbf1[0];
        bf0 = nbf0;
        bf1 = nbf1;
        br0 = nbr0;
        br1 = nbr1;
    }
    vector<i64> res;
    auto tosum = [&](i64 c) -> i64 {
        return (i128(c) * c + i128(x - y) * c + i128(n) * x * y) / (2 * x);
    };
    for (int i = 0; i <= n; i++) {
        if (bf0[i]) res.push_back(tosum(i * x));
        if (bf1[i]) res.push_back(tosum(i * x + y));
    }
    for (int i = 1; i <= n; i++) {
        if (br0[i]) res.push_back(tosum(-i * x));
        if (br1[i]) res.push_back(tosum(-i * x + y));
    }
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return res;
}

void solve() {
    int n;
    cin >> n;
    i64 x, y;
    cin >> x >> y;
    string s;
    cin >> s;
    auto rs = calc(n, s, x, y);
    i64 ans = 0;
    for (auto v : rs) ans = (ans + (v % MOD + MOD)) % MOD;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();

}

Can you transform some constraints of the problem into something easier to handle?

Try to come up with a dynamic programming solution that runs in polynomial time.

How do you optimize your solution? Pay attention to any unusual constraints.

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    f = [10 ** 9] * 320
    f[0] = 0
    for i in range(n):
        if s[i] == "1":
            for j in range(318, -1, -1):
                f[j + 1] = min(f[j + 1], f[j])
        nf = [10 ** 9] * 320
        for j in range(320):
            nf[j] = min(nf[j], max(f[j], a[i]) + max(1, 2 * j - 1))
            if j:
                nf[j - 1] = min(nf[j - 1], f[j] + 2 * j - 1)
        print(nf[0]) 
        f = nf

Solve the problem in $$$O(n \operatorname{polylog} n)$$$.

Processing two permutations is difficult. How can we reduce them to one?

In a DFS order, the nodes of any subtree form a contiguous segment, with the root of the subtree appearing at the very beginning of that segment. What property does this imply for our problem?

The property that a segment must be a "permutation of a specific set" is not straightforward to check directly. Is there a way to simplify this condition into something more computationally efficient?

Because each valid segment can be mapped to a subtree, the valid segments form a laminar family (i.e., they do not cross). Any two valid segments are either completely disjoint or one is strictly contained inside the other.

The problem asks for the largest depth. To achieve this, we can greedily find the largest valid segment for every fixed start position.

Read the hints above.

Recall that we need to solve for any $$$1 \le l \le n$$$, the largest $$$r$$$ such that:

• $$$c[l] = \min(c[l \dots r])$$$
• $$$\max(c[l \dots r]) - \min(c[l \dots r]) = r - l$$$

There are multiple ways to solve this. We will introduce a divide-and-conquer approach.

To solve this problem using a divide-and-conquer approach, we define a recursive function that processes the interval $$$[l, r]$$$. The core logic handles the sub-problems where the valid range $$$[i, j]$$$ crosses the midpoint $$$mid$$$ (with $$$l \le i \le mid \lt j \le r$$$).

We precompute the prefix minimums and maximums for the right half ($$$mid + 1 \dots r$$$) and the suffix minimums and maximums for the left half ($$$l \dots mid$$$). Let's denote the suffix values for index $$$i$$$ as $$$min[i]$$$ and $$$max[i]$$$, and similarly for the prefix values at index $$$j$$$.

The problem requires $$$c[i] = \min(c[i \dots j])$$$. Since we are iterating $$$i$$$ from $$$mid$$$ down to $$$l$$$, this condition implies that $$$c[i]$$$ must be the minimum of the left part $$$c[i \dots mid]$$$. If $$$min[i] \neq min[i+1]$$$, it indicates that $$$c[i]$$$ is strictly smaller than the minimum of the range to its right, making it a candidate for the global minimum.

For such valid $$$i$$$, we consider two cases based on the location of the maximum value in the range $$$[i, j]$$$:

Case 1: The Maximum is on the Left

If the maximum value of the range is determined by the left side (i.e., $$$\max(c[i \dots j]) = max[i]$$$), the equation $$$\max - \min = j - i$$$ can be rewritten to determine the specific target index $$$j$$$:

We simply calculate this candidate $$$j$$$ and verify three conditions:

• $$$j$$$ is within the valid right range ($$$mid \lt j \le r$$$).
• The minimum on the right does not contradict our global minimum assumption ($$$min[j] \gt min[i]$$$).
• The maximum on the right is not larger than our current maximum ($$$max[j] \lt max[i]$$$).

If these hold, we update the answer for $$$i$$$.

Case 2: The Maximum is on the Right

If the maximum value is on the right side (i.e., $$$\max(c[i \dots j]) = max[j]$$$), the equation becomes:

Rearranging the terms to separate $$$i$$$ and $$$j$$$, we get:

To solve this efficiently, we group the indices $$$j$$$ from the right half based on the value of $$$max[j] - j$$$. For each $$$i$$$, we simply access the corresponding group to find the largest $$$j$$$ that satisfies the remaining validity conditions ($$$min[j] \gt min[i]$$$ and $$$max[j] \gt max[i]$$$). Because $$$max[j]$$$ is monotonic, we can introduce two-pointer strategy to avoid the $$$\log$$$ factor.

By conducting this algorithm, we can solve the largest valid segments for each start position. Then, we can use a stack to simulate the dfs process of the common tree, and solve the maximum depth easily.

The time complexity is $$$O(n\log n)$$$ by careful implementation.

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n+1), b(n+1);
    for (int i = 1; i <= n; ++i) std::cin >> a[i];
    for (int i = 1; i <= n; ++i) std::cin >> b[i];
    std::vector<int> mp(n+1), c(n+1), R(n+1);
    for (int i = 1; i <= n; ++i) mp[b[i]] = i;
    for (int i = 1; i <= n; ++i) c[i] = mp[a[i]];
    for (int i = 1; i <= n; ++i) mp[c[i]] = i;
    std::vector<int> min(n + 1), max(n + 1);
    std::vector<std::vector<std::pair<int, int>>> rmax(2 * n + 1);
    std::vector<int> p(2 * n + 1);

    auto work = [&](auto &&self, int l, int r) -> void {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        self(self, l, mid);
        self(self, mid + 1, r);
        min[mid] = max[mid] = c[mid];
        for (int i = mid - 1; i >= l; --i) {
            min[i] = std::min(min[i + 1], c[i]);
            max[i] = std::max(max[i + 1], c[i]);
        }
        min[mid + 1] = max[mid + 1] = c[mid + 1];
        rmax[c[mid + 1] - mid - 1 + n].emplace_back(c[mid + 1], mid + 1);
        for (int i = mid + 2; i <= r; ++i) {
            min[i] = std::min(min[i - 1], c[i]);
            max[i] = std::max(max[i - 1], c[i]);
            rmax[max[i] - i + n].emplace_back(min[i], i);
        }
        for (int i = mid; i >= l; --i) {
            if (min[i] != min[i + 1]) {
                int j = i + max[i] - min[i];
                if (j > mid && j <= r && min[j] > min[i] && max[j] < max[i]) {
                    R[i] = std::max(R[i], j);
                }
                j = min[i] - i + n;
                while (p[j] < std::ssize(rmax[j]) && rmax[j][p[j]].first > min[i]) {
                    ++p[j];
                }
                if (p[j]) {
                    int k = rmax[j][p[j] - 1].second;
                    if (max[k] > max[i]) R[i] = std::max(R[i], k);
                }
            }
        }
        for (int i = mid + 1; i <= r; ++i) {
            rmax[max[i] - i + n].clear();
            p[max[i] - i + n] = 0;
        }
    };
    work(work, 1, n);

    std::stack<int> st;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        while (!st.empty() && st.top() <= i) st.pop();
        if (R[i]) {
            st.push(R[i]);
            ans = std::max(ans, int(st.size()));
        }
    }
    std::cout << (ans + 1) << '\n';
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    std::cin >> T;
    while (T--) solve();
    return 0;
}

The problem background is a tribute to the visual novel Symphonic Rain. I highly recommend you to play it!

Construct the optimal tree by following the approach used in F1. Two child nodes $$$a$$$ and $$$b$$$ of a node are defined as entangled if and only if $$$a$$$ and $$$b$$$ appear in different orders in the two permutations. The maximal entangled set of a node's children is defined as the largest connected component formed by the entangled relationships among its children.

Theorem $$$1$$$: Each maximal entangled set and the points in its subtree must form an interval in both DFS sequences.

Proof: Suppose one DFS sequence contains nodes $$$a, b, c$$$ such that $$$a$$$ and $$$c$$$ belong to the same maximal entanglement set while $$$b$$$ does not. Then in the other DFS sequence, all nodes after $$$b$$$ must appear after $$$a$$$ and before $$$c$$$. Thus $$$a$$$ and $$$c$$$ cannot be entangled, leading to a contradiction.

Theorem $$$2$$$: Among the maximal entangled sets of a leaf node, if any maximal entangled set contains only one node, then this maximal entangled set must be the last maximal entangled set to appear in both DFS sequences.

Proof: Suppose there exists a maximal entanglement set with a single node that is not the latest maximal entanglement set in either DFS sequence. Then all subsequent maximal entanglement sets must be able to be connected under this node, contradicting the optimal tree property.

Theorem $$$3$$$: A maximal entanglement set must be connected under the same node in any valid tree.

Proof: For a pair of entangled child nodes $$$x, y$$$ of node $$$a$$$ in an optimal tree, let $$$p_x$$$ and $$$p_y$$$ be the ancestors of $$$x$$$ and $$$y$$$, respectively. Since $$$p_x$$$ and $$$p_y$$$ cannot be points in the subtree of $$$a$$$ other than $$$a$$$ itself (otherwise it contradicts the optimal tree structure). Furthermore, since $$$x$$$ appears earlier than $$$y$$$ in some DFS sequence, traversing from $$$x$$$ to $$$y$$$ requires popping all other nodes in $$$a$$$'s subtree (because $$$p_y$$$ is not within the maximal entangled group's range). This implies that traversing from $$$x$$$ to $$$y$$$ can only be achieved by popping $$$p_y$$$ multiple times from $$$x$$$ and then attaching $$$y$$$ to $$$p_y$$$. Thus, $$$p_y$$$ must be an ancestor of $$$p_x$$$. Similarly, $$$p_x$$$ must also be an ancestor of $$$p_y$$$, so $$$p_x = p_y$$$.

Theorem $$$4$$$: If a maximal entanglement set has size greater than 1, then on any valid tree, if the parent node of this maximal entanglement set is $$$p$$$, then the subtree of all nodes within this maximal entanglement set must lie within the subtree of $$$p$$$.

Proof: Suppose a node $$$d$$$ in the subtree of some node $$$x$$$ within the maximal entanglement set does not lie within the subtree of $$$p$$$. Find a node $$$y$$$ entangled with $$$x$$$. Then, in the DFS sequence where $$$x$$$ appears before $$$y$$$, $$$d$$$ must lie between $$$x$$$ and $$$y$$$, contradicting that $$$d$$$ is not in the subtree of $$$p$$$.

Therefore, each maximal entanglement set greater than $$$1$$$ can be collapsed into a single node, treated as a leaf attached to its parent. At this point, the two DFS sequences become identical. The number of solutions is thus equal to the number of trees where the DFS sequences perfectly match and every node that was originally in a maximal entanglement set remains a leaf in the new tree. For solutions within each maximal entanglement set, we can recursively compute the number of trees matching the DFS sequence for each node within that set. Multiplying these values yields the total number of valid trees.

Consider counting the number of trees where the DFS sequence is identical to the given sequence, and every node that was originally in a maximal entanglement set remains a leaf in the new tree. Treat the DFS process as a bracket sequence: entering a new node is treated as a left bracket, and exiting a node is treated as a right bracket. If a node is a leaf, then the next bracket after its left bracket must be a right bracket. Thus, the problem asks for the number of bracket sequences that satisfy having $$$n$$$ left brackets and right brackets, where the next bracket after the $$$a_1, a_2, \dots, a_m$$$th left bracket is always a right bracket. A simple $$$O(n^2)$$$ dynamic programming approach suffices to find the answer.

The overall time complexity is $$$O(n^2)$$$.

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long ans;
int a[5000],b[5000],pa[5000],pb[5000],tvis[5000],cvis[5000],zvis[5000];
vector<int>line[5001];
int dep[5001],cntsg[5001],wp[5001];
vector<int>vec;
long long dp[5001],tdp[5001];
long long solve(){
	long long i,j,n=vec.size(),csum;
	for(i=0;i<=n;i++)dp[i]=0;
	dp[0]=1;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)tdp[j+vec[i]]=(tdp[j+vec[i]]+dp[j])%mod;
		csum=0;
		for(j=n;j>=0;j--)
		{
			csum=(csum+tdp[j])%mod;
			dp[j]=csum;
			tdp[j]=0;
		}
	}
	vec.clear();
	return dp[0];
}
void dfs(int t){
	vector<int>::iterator it;
	int i;
	for(i=0;i<cntsg[t];i++)vec.push_back(0);
	if(wp[t]==-1)ans=ans*solve()%mod;
	else
	{
		vec.push_back(1);
		dfs(wp[t]);
	}
	for(it=line[t].begin();it!=line[t].end();it++)
	{
		if(*it==wp[t])continue;
		vec.push_back(1);
		dfs(*it);
	}
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,n,i,j,t,ccnt,r;
	for(cin>>T;T>0;T--)
	{
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			a[i]--;
			pa[a[i]]=i;
		}
		for(i=0;i<n;i++)
		{
			cin>>b[i];
			b[i]--;
			pb[b[i]]=i;
		}
		for(i=0;i<n;i++)tvis[i]=0;
		for(i=n-1;i>-1;i--)
		{
			t=pb[a[i]];
			cntsg[i]=0;
			wp[i]=-1;
			for(j=0;j<n;j++)
			{
				cvis[j]=0;
				zvis[j]=0;
			}
			ccnt=0;
			r=-1;
			for(j=0;i+j<n&&t+j<n;j++)
			{
				if(cvis[a[i+j]]==0)ccnt++;
				cvis[a[i+j]]++;
				if(cvis[a[i+j]]==0)ccnt--;
				if(cvis[b[t+j]]==0)ccnt++;
				cvis[b[t+j]]--;
				if(cvis[b[t+j]]==0)ccnt--;
				if(ccnt==0)
				{
					zvis[i+j]=1;
					r=i+j;
				}
			}
			for(j=i+1;j<=r;j++)
			{
				if(tvis[j])
				{
					line[i].push_back(j);
					tvis[j]=0;
					if(zvis[j-1])
					{
						cntsg[i]++;
						wp[i]=j;
					}
					else wp[i]=-1;
				}
			}
			if(wp[i]!=-1)cntsg[i]--;
			tvis[i]=1;
		}
		cntsg[n]=0;
		wp[n]=-1;
		for(i=0;i<n;i++)
		{
			cvis[i]=0;
			zvis[i]=0;
		}
		ccnt=0;
		r=-1;
		for(i=0;i<n;i++)
		{
			if(cvis[a[i]]==0)ccnt++;
			cvis[a[i]]++;
			if(cvis[a[i]]==0)ccnt--;
			if(cvis[b[i]]==0)ccnt++;
			cvis[b[i]]--;
			if(cvis[b[i]]==0)ccnt--;
			if(ccnt==0)
			{
				zvis[i]=1;
				r=i;
			}
		}
		for(i=0;i<n;i++)
		{
			if(tvis[i])
			{
				line[n].push_back(i);
				tvis[i]=0;
				if(i==0||zvis[i-1])
				{
					cntsg[n]++;
					wp[n]=i;
				}
				else wp[n]=-1;
			}
		}
		if(wp[n]!=-1)cntsg[n]--;
		ans=1;
		dep[n]=0;
		dfs(n);
		for(i=0;i<=n;i++)line[i].clear();
		cout<<ans<<'\n';
	}
	return 0;
}

Solve the problem in $$$O(n \log^2 n)$$$.

Observation 0: If $$$q_1,q_2,\dots,q_n$$$ is valid, then $$$q_1\bmod n+1,q_2\bmod n+1,\dots,q_n\bmod n+1$$$ is another valid $$$q$$$. This is obvious.

Therefore, we do not need the exact original labeling of values. We may assume $$$q_v=n$$$.

Define $$$Child_v={u\mid s[u][v]=1}$$$; Define $$$smn_v = min_{u\in Child_v}u$$$; Define $$$smx_v = max_{u\in Child_v}u$$$.

Observation 1: If the value at index $$$v$$$ is $$$n$$$, then the position of $$$n−1$$$ must be either $$$mn_v$$$ or $$$mx_v$$$.

Proof: If $$$q_{x}=n-1$$$, and $$$smn_v \lt x \lt smx_v$$$. Then the parent node of at least one of $$$mn_v$$$ and $$$mx_v$$$ must be $$$x$$$. This is contrary to the previous assumption.

So we only need to choose between these two candidates. We may assume $$$q_u=n-1$$$.

Define an edge $$$(u, parent_u)$$$ to cross index $$$v$$$ if $$$u$$$ and its parent lie on different sides of $$$v$$$, in other words, $$$(u-v)\cdot(parent_u-v) \lt 0$$$.

Observation 2: In every Cartesian tree during the process, the edge between index $$$u$$$ ($$$q_u=n-1$$$) and its parent $$$(u, parent_u)$$$ never cross the index $$$v$$$ ($$$q_v=n$$$).

Proof: For every node on a Cartesian tree, its parent node must be the closest node greater than it. If this edge $$$(u, parent_u)$$$ crosses node v, then one side's closest point to node u becomes v, leading to a contradiction.

Now let's decide whether $$$n−1$$$ is on the left or right. We are at index $$$v$$$ (treat it as value $$$n$$$).

Case A: all extreme children are on one side. If $$$smx_v \lt v$$$, then every child that ever attaches to $$$v$$$ lies left of $$$v$$$. Therefore $$$n−1$$$ must be on the left, and by Observation 1 it must be $$$smn_v$$$. If $$$smn_v \gt v$$$, similarly $$$n−1$$$ must be on the right, hence it must be $$$smx_v$$$.

Case B: children exist on both sides ($$$smn_v \lt v \lt smx_v$$$)

Observation 3: In the case B ($$$smn_v \lt v \lt smx_v$$$), among these two extreme children, one must have at least one parent edge crosses $$$v$$$, and the other one mustn't.

Proof: One child $$$q_x=n-1$$$ mustn't have a parent edge that crosses the index $$$v$$$ ($$$q_v=n$$$) due to the observation 2. For the other child node $$$q_y$$$, when $$$q_x=n-1$$$ is the root node, the parent node of $$$q_y$$$ must be $$$q_x$$$. They are on both sides of index $$$v$$$ ($$$q_v=n$$$). Therefore, it has at least one parent edge that crosses the index $$$v$$$ ($$$q_v=n$$$).

Similarly, define $$$Fa_v={u\mid s[v][u]=1}$$$; Define $$$fmn_v = min_{u\in Fa_v}u$$$; Define $$$fmx_v = max_{u\in Fa_v}u$$$.

If $$$fmx_{smn_v} \lt v$$$, then $$$smn_v$$$ doesn't have a parent edge that crosses $$$v$$$, then $$$q_{smn_v} = n - 1$$$. And vice versa.

The time complexity is $$$O(n^2)$$$. The bottleneck is preprocessing the input data.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;


signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> fa_mx(n + 1), fa_mn(n + 1, n);
        vector<int> son_mx(n + 1), son_mn(n + 1, n);
        vector<vector<int>> fa(n + 1), son(n + 1);
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            s = ' ' + s;
            for (int j = 1; j <= n; j++) {
                if (i == j or s[j] == '0') continue;
                int u = j, v = i;
                fa_mx[v] = max(fa_mx[v], u);
                fa_mn[v] = min(fa_mn[v], u);
                son_mx[u] = max(son_mx[u], v);
                son_mn[u] = min(son_mn[u], v);
            }
        }
        vector<int> a(n + 1);
        for (int p = n, val = n; ; val--) {
            a[p] = val;
            if (val == 1) break;
            int mn = son_mn[p], mx = son_mx[p];
            if (mx < p) {
                p = mn;
            } else if (mn > p) {
                p = mx;
            } else {
                int mx1 = fa_mx[mn];
                if (mx1 <= p) {
                    p = mn;
                } else {
                    int mn2 = fa_mn[mx];
                    assert(mn2 >= p);
                    p = mx;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " \n"[i == n];
        }
    }
}