It can be observed that $$$s_n$$$ will not change throughout the operations, therefore, for the final string to have every character the same, every character must be equal to $$$s_n$$$.

To change every character to $$$s_n$$$, we can iterate over all characters from right to left, repeatedly setting $$$s_{i-1}\leftarrow s_i$$$ if $$$s_{i-1}\neq s_n$$$. Through this, we can need one operation for every character not equal to $$$s_n$$$, which is also obvious as a lower bound.

Time complexity: $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

char s[100005];

int main()
{
	int n, t, i, m;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		scanf("%s", s + 1);
		m = 0;
		for(i = 1; i < n; i++)
			m += (s[i] != s[n]);
		printf("%d\n", m);
	}
	return 0;
}

After some experimenting, it can be seen that the answer does not exceed $$$2$$$. Simply click at $$$a$$$ as long as there's still a tab at that point. After that, each tab must have length of $$$b$$$, move the cursor to $$$b$$$, and click until all tabs have been closed.

Now it remains to be seen under what scenarios we can achieve $$$1$$$ move. Since the last tab closed will have length $$$b$$$, our cursor should be moved to $$$b$$$. Therefore, the answer will be $$$1$$$ when $$$nb\le a$$$, or $$$b=a$$$, and $$$2$$$ otherwise.

Remember to use long long if using multiplication to calculate $$$nb$$$.

Time Complexity: $$$O(1)$$$ per test case.

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t, n, a, b;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d%d", &a, &b, &n);
		printf(((long long)b * n <= a || b >= a) ? "1\n" : "2\n");
	}
	return 0;
}

We consider a simple strategy: repeatedly merge the smallest element onto the smaller of its two neighbours.

We will prove this greedy is correct: For any merge sequence, consider the smallest element $$$mn$$$, it must be merged into a larger element at some point in the future. However, its neighbour will not be smaller, which means that we can simply modify the merge sequence to merge $$$mn$$$ into its neighbours at the very first.

Further observation will show that this value is equal to $$$\sum_{i=1}^{n-1}\max(a_i,a_{i+1})+\max(a_n,a_1)-\max({a_1,a_2,\cdots,a_n})$$$. A brief sketch of the proof is as follows: It can be shown that we can break the ring into a sequence at an arbitrary maxima, since the maxima will not be merged into others.

For the problem on a sequence, consider each element $$$a_i$$$, find the closest element $$$a_x$$$ to the left of $$$a_i$$$, such that $$$a_x \gt a_i$$$ (when equal, break ties according to index). If there are elements between $$$a_x$$$ and $$$a_i$$$, then it's clear that in performing the aforementioned greedy, at some point we will merge everything in $$$a_{x+1},a_{x+2},\cdots,a_i$$$ into a single element, and then merge it into $$$a_i$$$. Therefore the answer will be increased by $$$a_i$$$ if $$$a_{i-1} \lt a_i$$$. The same thing will happen to the right of $$$a_i$$$. Therefore the answer is $$$\sum_{i=1}^{n-1}[a_i\ge a_{i+1}]a_i+[a_i \lt a_{i+1}]a_{i+1}$$$, which can be rephrased as $$$\sum_{i=1}^{n-1}\max(a_i,a_{i+1})$$$, which in turn is the formula above.

However, this is not needed to pass the problem. We expected participants to pass using doubly linked lists, sets, or any other data structures which can support the operations needed.

Time Complexity: $$$O(n)$$$ or $$$O(n\log n)$$$.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e6 + 5;
ll a[N];

int main()
{
	int t, n, m, i;
	ll k;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		m = 0;
		for(i = 0; i < n; i++)
		{
			scanf("%lld", a + i);
			if(a[i] > a[m])
				m = i;
		}
		a[n] = a[0];
		k = -a[m];
		for(i = 0; i < n; i++)
			k += max(a[i], a[i + 1]);
		printf("%lld\n", k);
	}
	return 0;
}

// In the name of Allah.
 
#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        list<int> alive;
        int a[n];
        list<int>::iterator w[n];
        auto c_next = [&alive](const list<int>::iterator& it) {
            return next(it) == alive.end() ? alive.begin() : next(it);
        };
        auto c_prev = [&alive](const list<int>::iterator& it) {
            return it == alive.begin() ? --alive.end() : prev(it);
        };
        auto hole = [&](const list<int>::iterator& it) {
            return a[*it] <= min(a[*c_next(it)], a[*c_prev(it)]);
        };
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            w[i] = alive.insert(alive.end(), i);
        }
        queue<int> q;
        {
            int i = 0;
            for (auto it = alive.begin(); it != alive.end(); ++it, ++i)
                if (hole(it))
                    q.push(i);
        }
        long long ans = 0;
        bool mark[n] = {};
        while (alive.size() > 1) {
            auto i = q.front();
            q.pop();
            if (mark[i])
                continue;
            mark[i] = true;
            auto it = w[i];
            ans += min(a[*c_next(it)], a[*c_prev(it)]);
            auto jt = c_next(it);
            alive.erase(it);
            it = jt;
            if (hole(it))
                q.push(*it);
            it = c_prev(it);
            if (hole(it))
                q.push(*it);
        }
        cout << ans << '\n';
    }
}

For a multiset $$$S$$$, we will find a check to determine whether it can be generated.

For each color $$$x$$$ not in $$$S$$$, we need to somehow "hide" all of the $$$x$$$'s in other sets. That is, for every partitioned set, the occurrence of $$$x$$$ must be less than or equal to the occurrence of the modes.

For each color $$$c$$$ in $$$S$$$, no matter how many times $$$c$$$ appeared in $$$S$$$, or how we partition these $$$c$$$ into different sets, the color $$$c$$$ can provide at most $$$cnt_c$$$ "chances" to hide an element of $$$x$$$.

Therefore, $$$cnt_x\le\sum_{c\in S}cnt_c$$$ must hold.

It is easy to construct a partition once this condition is held for all $$$x$$$. Thus, we only need to count sets that satisfy $$$\max_{x\not\in S} cnt_x\le\sum_{c\in S} cnt_c$$$.

This is a simple knapsack dp problem from here, you can either add elements in increasing order of $$$cnt$$$ and keep track if the last color is used at all, or observe that the condition is just $$$\sum_{c\in S}cnt_c\ge\max cnt$$$, and just running a completely vanilla knapsack dp.

Time Complexity: $$$O(n^2)$$$.

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e3 + 5, P = 998244353;
 
int n;
int a[N], cnt[N];
int dp[N];
 
void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	
	memset(cnt, 0, sizeof cnt);
	int max_cnt = 0;
	for (int i = 1; i <= n; ++i) {
		max_cnt = max(max_cnt, ++cnt[a[i]]);
	}
 
	memset(dp, 0, sizeof dp), dp[0] = 1;
	for (int i = 1; i <= n; ++i) if (cnt[i]) {
		for (int j = n; j >= cnt[i]; --j) {
			dp[j] = (dp[j] + 1ll * cnt[i] * dp[j - cnt[i]]) % P;
		}
	}
	
	int ans = 0;
	for (int i = max_cnt; i <= n; ++i) (ans += dp[i]) %= P;
	cout << ans << endl;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int T;	
	cin >> T;
	while (T--) {
		solve();
	}
 
	return 0;
}

There are many ways to approach this problem, my personal approach is as follows:

Consider what kind of $$$a$$$ would satisfy the requirements, after some exploring, we can arrive at the following check: Sum each bit of $$$a$$$, resulting in an integer sequence, if this sequence is lexicographically larger or equal to the binary representation of $$$c$$$, then $$$a$$$ is ok.

This can be explained by considering bits from high to low:

• If at some point we have more $$$a$$$'s than $$$c$$$, we can use a 1-bit on this position to fix everything under this bit.
• If at some point we have $$$0$$$ a's and the $$$c$$$ bit is $$$1$$$, it's then obvious that we cannot satisfy the conditions, since we also cannot use higher bits to change the situation, as this will cause higher bits to be less than $$$c$$$.

Thus, we have obtained a clean check to $$$a$$$.

To minimize the $$$+1$$$ operations, we will iterate bits from high to low, if the current $$$a$$$'s is less than $$$c$$$, we will have to select a single $$$a$$$ element, and increase it to the point that the current bit is $$$1$$$. Note that we will not increase two $$$a$$$ elements, since in reaching the state, we will inevitably reach the state where one of the $$$a$$$ is $$$1000\cdots00$$$, and the other one is $$$0111\cdots11$$$, this is already enough.

From here, observe that only the maximum $$$O(\log V)$$$ elements are used, we can easily achieve a complexity of $$$O(n\log n+q\log^2V)$$$, or $$$O(n\log n+q\log V\log\log V)$$$ with heaps.

#include <bits/stdc++.h>
#define N 500011
#define ll long long
using namespace std;
int T,n,q,a[N];
int main()
{
	scanf("%d",&T);while(T--)
	{
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;++i)scanf("%d",a+i);
		sort(a+1,a+1+n,greater<int>());
		int nn=min(n,32);
		while(q--)
		{
			int c;scanf("%d",&c);
			static int b[44];ll ans=0;
			for(int i=1;i<=nn;++i)b[i]=a[i];
			for(int i=29;~i;--i)
			{
				int cc=0;
				for(int j=1;j<=nn;++j)cc+=b[j]>>i&1;
				if(cc>(c>>i&1))break;
				if(cc<(c>>i&1))
				{
					int id=1;
					for(int j=2;j<=nn;++j)if(b[j]>b[id])id=j;
					ans+=(1<<i)-b[id];
					b[id]=0;
				}
				else for(int j=1;j<=nn;++j)b[j]&=~(1<<i);
			}
			printf("%lld\n",ans);
		}
	}
}

Reduce the problem to bipartite matching.

Devise a greedy algorithm to solve the matching problem, and prove it (or not).

The problem can be formulated as a minimum path cover, which in turn can be converted into a bipartite matching problem:

• For each element in $$$a$$$, create both a left side vertex and a right side vertex, each left side vertex with value $$$a_i$$$ can match right side vertices with index larger than $$$i$$$, and with value $$$a_i-1$$$ or $$$a_i+1$$$.

It can be observed that the graph can be partitioned into two unconnected components by parity.

A certain intuition the matching for $$$a_i=1$$$ stricter than $$$a_i=3$$$, maybe we can try just letting the $$$a_i=1$$$ greedily choose the next element, and just believe that it will work out.

Therefore, we can propose a greedy algorithm: we iterate values $$$v$$$ from small to large, for every vertex with value $$$v$$$ on the left side, if it is unmatched, we match it with a $$$v+1$$$ on the right side with index closest to it, we do the same for value $$$v$$$ vertices on the right side.

We can prove that this is correct: Consider an element with $$$a_i=1$$$, if it did not match the closest $$$a_i=2$$$ on the right, we will try to substitute this pair into the final matching.

Suppose our $$$a_i=1$$$ vertex is $$$A$$$, the $$$a_i=2$$$ vertex on the right is $$$B$$$. If we insert $$$A-B$$$ into the matching, and discard any preexisting matches with $$$A$$$ or $$$B$$$, the only case where we our matching size decreases is when $$$A$$$ and $$$B$$$ are both matched with some $$$C$$$ and $$$D$$$, respectively.

It can then be shown by simple reasoning that $$$C$$$ and $$$D$$$ can be matched, which means our matching size will not be reduced.

Therefore, we can choose any $$$a_i=1$$$ and the closest $$$a_i=2$$$, and simply delete them from the graph.

Thus, the greedy is proved.

Implementation should be easy. Time Complexity: $$$O(n\log n)$$$ or $$$O(n)$$$.

Observation: construct a bipartite graph with $$$2n$$$ vertices, named $$$L_1,L_2,\dots,L_n$$$ and $$$R_1,R_2,\dots,R_n$$$. There is an edge between $$$L_i$$$ and $$$R_j$$$ iff $$$i \lt j$$$ and $$$|a_i-a_j|=1$$$. The answer to the original problem is $$$n$$$ minus the size of the maximum matching of this graph.

Consider using hall theorem on $$$L_1,L_2,\dots,L_n$$$, thus we only need to calculate $$$\max |S|-|N(S)|$$$.

Separate $$$L$$$ into $$$L_{odd}$$$ and $$$L_{even}$$$, which contains all the $$$L_i$$$ with odd $$$a_i$$$ and vice versa. Let $$$S_{odd}=S\cap L_{odd}$$$ and $$$S_{even}=S\cap L_{even}$$$ we can see that $$$|S|-|N(S)|=|S_{odd}|-|N(S_{odd})|+|S_{even}|-|N(S_{even})|$$$, so we can calculate the two parts separately.

For $$$\max |S_{odd}|-|N(S_{odd})|$$$, if adding an element to $$$S_{odd}$$$ doesn't make $$$N(S_{odd})$$$ bigger, we can always add it. So we only need to consider $$$S_{odd}$$$ that for every odd value $$$x$$$, all the elements in $$$S_{odd}$$$ with value $$$x$$$ forms a suffix of all appearances of $$$x$$$ in array $$$a$$$.

We can define $$$dp_{i,j}$$$ as the maximum $$$|S_{odd}|-|N(S_{odd})|$$$ when only considering elements with value $$$\leq i$$$ in $$$S_{odd}$$$ and $$$N(S_{odd})$$$ (where $$$i$$$ is always odd), and the elements with value $$$i$$$ forms the suffix starting from position $$$j$$$. Since $$$\sum cnt$$$ is bounded by $$$O(n)$$$, we have a total of $$$O(n)$$$ states. The dp transitions between $$$i$$$ and $$$i+2$$$ can be done easily in linear time, so the total complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 5;
bool vis[N];
int a[N], n;
vector<int> pos[N * 2];
int solve()
{
	int i, p, ans = 0;
	vector<int> tmp;
	for(i = 1; i < 2 * n; i++)
	{
		if(i & 1)
		{
			p = 0;
			for(auto o: pos[i])
			{
				while(p < pos[i + 1].size() && pos[i + 1][p] < o)
					p++;
				if(p < pos[i + 1].size())
					vis[pos[i + 1][p++]] = 1;
			}
		}
		else
		{
			p = pos[i + 1].size();
			reverse(pos[i].begin(), pos[i].end());
			for(auto o: pos[i])
			{
				while(p && pos[i + 1][p - 1] > o)
					p--;
				if(p)
					vis[pos[i + 1][--p]] = 1;
			}
		}
		tmp.clear();
		for(auto o: pos[i + 1])
			if(vis[o])
				ans++;
			else
				tmp.emplace_back(o);
		pos[i + 1] = tmp;
	}
	return ans;
}
 
int main()
{
	int t, i, ans;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		for(i = 1; i <= n; i++)
			scanf("%d", a + i);
		for(i = 1; i <= n; i++)
			vis[i] = 0;
		for(i = 1; i <= 2 * n; i++)
			pos[i].clear();
		for(i = 1; i <= n; i++)
			pos[a[i]].emplace_back(i);
		ans = n - solve();
		reverse(a + 1, a + n + 1);
		for(i = 1; i <= n; i++)
			vis[i] = 0;
		for(i = 1; i <= 2 * n; i++)
			pos[i].clear();
		for(i = 1; i <= n; i++)
			pos[a[i]].emplace_back(i);
		ans -= solve();
		printf("%d\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5, inf = 1e9;
int a[N], lp[N], rp[N], Lp[N], m;
vector<int> pos[N * 2], dp[N * 2], tmp;
int solve()
{
	int i, j, u, v, p;
	dp[1].resize(pos[1].size());
	for(i = 0; i < pos[1].size(); i++)
		dp[1][i] = i;
	for(i = 1; i < m; i += 2)
	{
		u = pos[i].size() - 1;
		v = pos[i + 2].size() - 1;
		tmp.clear();
		tmp.resize(u + 1);
		dp[i + 2].clear();
		dp[i + 2].resize(v + 1);
		for(j = 0; j <= u; j++)
			tmp[j] = dp[i][j] - rp[pos[i][j]];
		for(j = u; j > 0; j--)
			tmp[j - 1] = max(tmp[j - 1], tmp[j]);
		for(j = 0; j <= v; j++)
		{
			p = pos[i + 2][j];
			if(j)
				dp[i + 2][j] = dp[i + 2][j - 1];
			if(Lp[p] < u)
				dp[i + 2][j] = max(dp[i + 2][j], j + tmp[Lp[p] + 1]);
			dp[i + 2][j] = max(dp[i + 2][j], j - lp[p] + dp[i][Lp[p]]);
		}
	}
	return dp[m].back();
}

int main()
{
	int t, n, i, ans;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		m = 0;
		ans = n;
		for(i = 1; i <= n; i++)
		{
			scanf("%d", a + i);
			m = max(m, a[i]);
			ans -= 2 * (a[i] & 1);
		}
		m |= 1;
		for(i = 1; i <= m; i++)
			pos[i] = {0};
		for(i = 1; i <= n; i++)
		{
			pos[a[i]].emplace_back(i);
			lp[i] = (a[i] > 1 ? pos[a[i] - 1].size() - 1 : 0);
			rp[i] = (a[i] < m ? pos[a[i] + 1].size() - 1 : 0);
			Lp[i] = (a[i] > 2 ? pos[a[i] - 2].size() - 1 : 0);
		}
		ans += solve();
		reverse(a + 1, a + n + 1);
		for(i = 1; i <= m; i++)
			pos[i] = {0};
		for(i = 1; i <= n; i++)
		{
			pos[a[i]].emplace_back(i);
			lp[i] = (a[i] > 1 ? pos[a[i] - 1].size() - 1 : 0);
			rp[i] = (a[i] < m ? pos[a[i] + 1].size() - 1 : 0);
			Lp[i] = (a[i] > 2 ? pos[a[i] - 2].size() - 1 : 0);
		}
		ans += solve();
		printf("%d\n", ans);
	}
	return 0;
}

The answer is increasing, try solve for the maximum number of colors for a certain inconvenience $$$d$$$.

Every color is a connected component.

There exists a diameter-midpoint like structure.

The optimal answer has a certain structure, try finding it.

We switch the answer and the parameter, and solve for the maximum number of colors for a given diameter $$$d$$$.

A simple intuition is that each color should be a connected component, this is also easily provable: If some color is not connected, we can choose one of its "outermost" components (a more rigorous definition would be the leaves of the auxiliary tree of its components), and change it to the color of its adjacent component. In doing this, the number of different components is decreased, and our inconvenience has not increased. Therefore, after enough changes, each color will be a connected component.

The problem asks for a diameter-like value, therefore, we can try to find a diameter-midpoint-like structure:

• When $$$d$$$ is odd, there exists a color component such that the distance to all other vertices does not exceed $$$\frac{d-1}2$$$.
• When $$$d$$$ is even, there exists a vertex such that the distance to all other vertices does not exceed $$$\frac d2$$$.

Now, observe that we can "push" colors away from the midpoint and out to the leaves, to increase the number of color used, our optimal solution would look something like this:

Therefore, the optimal solution is:

• For odd $$$d$$$, remove the outermost $$$(d-1)/2$$$ levels of leaves.
• For even $$$d$$$, remove the outermost $$$d/2-1$$$ levels of leaves, and choose a maximum degree vertex in the remaining tree.

Time Complexity: $$$O(n\log n)$$$ or $$$O(n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 3e5 + 5;
vector<int> e[N];
int val[N], cnt[N], deg[N], h[N], d;
queue<int> q;
int del(int x)
{
	cnt[deg[x]]--;
	cnt[--deg[x]]++;
	return deg[x];
}
 
int main()
{
	int t, n, i, u, v, k, c;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		for(i = 1; i <= n; i++)
			e[i].clear();
		for(i = 1; i < n; i++)
		{
			scanf("%d%d", &u, &v);
			e[u].emplace_back(v);
			e[v].emplace_back(u);
		}
		for(i = 0; i <= n; i++)
		{
			val[i] = 1e9;
			cnt[i] = 0;
			h[i] = 1;
		}
		for(i = 1; i <= n; i++)
			cnt[deg[i] = e[i].size()]++;
		for(i = 1; i <= n; i++)
			if(deg[i] == 1)
				q.push(i);
		c = 0;
		d = n;
		while(!cnt[d])
			d--;
		val[1] = min(val[1], 1);
		val[d] = min(val[d], 2);
		while(!q.empty())
		{
			k = q.front();
			q.pop();
			for(auto o: e[k])
				if(del(o) == 1)
				{
					h[o] = h[k] + 1;
					q.push(o);
				}
			++c;
			while(!cnt[d])
				d--;
			val[c + 1] = min(val[c + 1], 2 * h[k] + 1);
			val[c + d] = min(val[c + d], 2 * h[k] + 2);
		}
		for(i = n - 1; i >= 1; i--)
			val[i] = min(val[i], val[i + 1]);
		for(i = 1; i < n; i++)
			printf("%d ", val[i]);
		printf("\n");
	}
	return 0;
}

We only need to calculate the minimum $$$r$$$ for each $$$l$$$, try breaking $$$21435$$$ into smaller parts.

When we fix the $$$21$$$-part, we need to append a $$$435$$$-part such that $$$val_3 \gt val_2$$$, and $$$index_4 \gt index_1$$$. (Here the footnotes refer to the value order, rather than index order.)

Therefore, we need to find $$$435$$$-subsequences that are Left-Right-Min minimal, that is, there does not exist another $$$435$$$-subsequence that is better in all three aspects.

The number of such $$$435$$$-subsequences is small. Try analyzing what kind of subsequence are minimal.

Perform scanline on the value of "$$$3$$$" from large to small, at most one $$$435$$$ will be added each time.

It suffices to find the minimal $$$r$$$ such that $$$[l,r]$$$ contains a $$$21435$$$-avoiding subsequence for every $$$l$$$.

We will refer to the elements by value order, instead of index order, in the following text, i.e. "$$$2$$$"-element refers to the leftmost element, with the second smallest value.

When we have fixed $$$l$$$, the "$$$2$$$"-element will be fixed, the "$$$1$$$"-element will just be the next element that is smaller than it, therefore, we only need to append a $$$435$$$-subsequence to it.

As we need to minimize $$$r$$$, and $$$val_3 \gt val_2,index_4 \gt index_1$$$ should be satisfied, we will need to consider all Left-Right-Min minimal $$$435$$$'s, that is, the ones where there does not exist another $$$435$$$ that is better in all three aspects.

To analyze this, we can try performing scanline on the $$$val_3$$$ from large to small, we can perform some substitutions to reduce the number of $$$435$$$'s we need to consider.

Through this, we can find a surprisingly strong restriction on minimal $$$435$$$'s: For each $$$i$$$ being considered as the "$$$3$$$"-element, the "$$$5$$$"-element must be $$$nxt(i)$$$, the closest element to the right of $$$i$$$, with value greater than $$$a_i$$$.

We perform substitutions as follows:

The three cases corresponds to:

• Left: $$$val_5 \lt val_{nxt(i)}$$$, by definition, $$$index_5 \gt index_{nxt(i)}$$$, substitute "$$$5$$$" by $$$nxt(i)$$$.
• Middle: $$$val_5 \gt val_{nxt(i)},val_4 \lt val_{nxt(i)}$$$, substitute "$$$5$$$" by $$$nxt(i)$$$.
• Right: $$$val_5 \gt val_{nxt(i)},val_4 \gt val_{nxt(i)}$$$, substitute $$$i$$$ by $$$nxt(i)$$$.

When "$$$3$$$" and "$$$5$$$" are fixed, "$$$4$$$" is also fixed. Therefore, there are at most $$$n$$$ minimal $$$435$$$'s, and they can be found by simple data structure techniques.

After finding the minimal $$$435$$$'s, the problem can be reduced to simple 2D-queries.

Time Complexity: $$$O(n\log n)$$$.

#include <bits/stdc++.h>
#define N 1000011
using namespace std;
int T,n,a[N],id[N];
int R[N];
struct sgt
{
	int D,mx[N*4];
	int query(int l,int r)
	{
		l+=D-1;r+=D+1;int ans=0;
		while(l^r^1)
		{
			if(!(l&1))ans=max(ans,mx[l^1]);
			if(r&1)ans=max(ans,mx[r^1]);
			l>>=1;r>>=1;
		}
		return ans;
	}
	void modi(int k,int p)
	{
		k+=D;mx[k]=p;
		while(k>>=1)mx[k]=max(mx[k<<1],mx[k<<1|1]);
	}
	void clear()
	{
		D=1;while(D<=n+10)D<<=1;
		for(int i=0;i<D+D;++i)mx[i]=0;
	}
}T1,T2;
int pl[N],res[N],curr[N];
int Rmn[N];
void proc()
{
	for(int i=1;i<=n;++i)R[i]=Rmn[i]=i+1,id[a[i]]=i,pl[i]=0;
	for(int i=n;i;--i)while(R[i]<=n&&a[R[i]]<a[i])R[i]=R[R[i]];
	for(int i=n;i;--i)while(Rmn[i]<=n&&a[Rmn[i]]>a[i])Rmn[i]=Rmn[Rmn[i]];
	T1.clear();
	for(int i=1;i<=n;++i)
	{
		if(R[i]<=n)
		{
			int k=T1.query(a[i]+1,a[R[i]]-1);
			pl[i]=k;
		}
		T1.modi(a[i],i);
	}
	T2.clear();
	for(int i=1;i<=n;++i)curr[i]=res[i]=0;
	for(int i=n;i;--i)
	{
		int x=id[i],y=Rmn[x];
		if(y<=n)
		{
			int rr=n+1-T2.query(y+1,n);
			if(rr<=n)res[rr]=max(res[rr],x);
		}
		if(pl[x])T2.modi(pl[x],curr[pl[x]]=max(curr[pl[x]],n+1-R[x]));
	}
	for(int i=1;i<=n;++i)res[i]=max(res[i],res[i-1]);
}
int main()
{
	scanf("%d",&T);while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;++i)scanf("%d",a+i);
		proc();
		long long ans=0;
		for(int i=1;i<=n;++i)ans+=res[i];
		printf("%lld\n",ans);
	}
}

Consider the case with $$$n=m=k$$$.

Generalize the solution for all $$$n,m,k$$$.

It can be shown that for any $$$k\times k$$$ subgrid, the colors we use must be pairwise distinct. Thus, we have an lower bound of $$$\min(n,k)\cdot\min(m,k)$$$. We can show that this lower bound is indeed achievable by coloring the upper-left $$$\min(n,k)\cdot\min(m,k)$$$ subgrid with distinct colors, and copy-pasting it to fill the rest of the grid.

Time complexity: $$$O(1)$$$.

#include <bits/stdc++.h>
using namespace std;
int t, n, m, k;
int main() {
    scanf("%d", &t);

    while (t--) {
        scanf("%d%d%d", &n, &m, &k);
        printf("%d\n", min(n, k)*min(m, k));
    }

    return 0;
}

Find some conditions that Bob need to win.

A general idea is that it is very difficult for Bob to win. We make some observations regarding the case where Bob wins. It is intuitive to see that for any subarray $$$[A_l,A_{l+1},\cdots,A_r]$$$, the elements' positions in $$$B$$$ must also form an interval. If $$$A[l:r]$$$ does not form an interval in $$$B$$$, Alice can simply remove elements until only $$$A[l:r]$$$ is left, no matter how Bob plays, there must now be an element in $$$A$$$ but not in $$$B$$$ because of our previous condition. Alice can then remove everything other than this element to win.

From here, it is easy to prove by induction that for Bob to win, either $$$A=B$$$ or $$$A=\textrm{rev}(B)$$$.

Time complexity: $$$O(n)$$$.

#include <bits/stdc++.h>
#define ll long long
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ru(i, l, r) for (int i = (l); i <= (r); i++)
#define rd(i, r, l) for (int i = (r); i >= (l); i--)
#define mid ((l + r) >> 1)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define sz(s) (int)s.size()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
int read() {
    int x = 0, w = 0;
    char ch = getchar();

    while (!isdigit(ch))
        w |= ch == '-', ch = getchar();

    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();

    return w ? -x : x;
}
int main() {
    int T = read();

    while (T--) {
        int n = read();
        vector<int> a, b;
        ru(i, 1, n) a.push_back(read());
        ru(i, 1, n) b.push_back(read());

        if (a == b) {
            printf("Bob\n");
            continue;
        }

        reverse(a.begin(), a.end());

        if (a == b) {
            printf("Bob\n");
            continue;
        }

        printf("Alice\n");
    }

    return 0;
}

The problem can't be that hard, find some simple strategy.

We consider a simple strategy: walk towards the goal in a straight line.

If some circle reaches the goal first, it is obvious that we have no chance of succeeding, no matter what path we take.

Otherwise, it can be proven that we will not pass any circles on our way to the goal.

Suppose we start at $$$A$$$, our goal is $$$B$$$, and we got intercepted by some circle $$$C$$$ at the point $$$D$$$. It follows that $$$CD=AD$$$. According to the triangle inequality, $$$CD \gt CB-DB$$$ should hold. Thus, we have $$$CB-DB\le AD$$$, which means $$$CB\le AB$$$, proof by contradiction.

Time complexity: $$$O(n)$$$.

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int t, n, x[100011], y[100011], xs, ys, xt, yt;
ll dis(int x1, int y1, int x2, int y2) {
    return 1ll * (x2 - x1) * (x2 - x1) + 1ll * (y2 - y1) * (y2 - y1);
}
int main() {
    scanf("%d", &t);

    while (t--) {
        scanf("%d", &n);

        for (int i = 1; i <= n; ++i)
            scanf("%d%d", x + i, y + i);

        scanf("%d%d%d%d", &xs, &ys, &xt, &yt);
        bool ok = 1;

        for (int i = 1; i <= n; ++i) {
            if (dis(xt, yt, x[i], y[i]) <= dis(xt, yt, xs, ys)) {
                ok = 0;
                break;
            }
        }

        printf(ok ? "YES\n" : "NO\n");
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}

Try to find some easy checks that can be maintained.

The problem revolves around finding a check for dfs orders that's easy to maintain. We have discovered several such checks, a few checks and their proofs are described below, any one of these checks suffices to tell whether a dfs order is valid.

Time complexity: $$$O((n+q)\log n)/O(n+q)$$$.

#include <bits/stdc++.h>
#define ll long long
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ru(i, l, r) for (int i = (l); i <= (r); i++)
#define rd(i, r, l) for (int i = (r); i >= (l); i--)
#define mid ((l + r) >> 1)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define sz(s) (int)s.size()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define maxn 500005
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
int read() {
    int x = 0, w = 0; char ch = getchar();
    while(!isdigit(ch)) w |= ch == '-', ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return w ? -x : x;
}
int n, Q, fa[maxn], p[maxn], q[maxn], siz[maxn];
set<int> son[maxn];
int chk(int x) {
    return son[x].empty() ? 1 : (q[x] < *son[x].begin() && *--son[x].end() + siz[p[*--son[x].end()]] <= q[x] + siz[x]);
}
void solve() {
    n = read(), Q = read();
    ru(i, 1, n) siz[i] = 1, son[i].clear();
    ru(i, 2, n) fa[i] = read();
    rd(i, n, 2) siz[fa[i]] += siz[i];
    ru(i, 1, n) son[fa[p[i] = read()]].insert(i), q[p[i]] = i;
    int cnt = 0;
    ru(i, 1, n) cnt += chk(i);
    while(Q--) {
        int i = read(), j = read(), x = p[i], y = p[j];
        set<int> s; s.insert(x), s.insert(y), s.insert(fa[x]), s.insert(fa[y]);
        for (auto x: s) if(x) cnt -= chk(x);
        son[fa[x]].erase(i), son[fa[y]].erase(j);
        swap(p[i], p[j]), swap(q[x], q[y]);
        son[fa[x]].insert(j), son[fa[y]].insert(i);
        for (auto x: s) if(x) cnt += chk(x);
        puts(cnt == n ? "YES" : "NO");
    }
}
int main() {
    int T = read();
    while(T--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
using ll = long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MAXN = 3e5 + 5;
const int MOD = 1e9+7; //998244353;
const int INF = 0x3f3f3f3f;
const ll INF64 = ll(4e18) + 5;
 
 
vector<int> g[MAXN];
 
int tin[MAXN];
int tout[MAXN];
int id[MAXN];
int par[MAXN];
int T = 0;
void dfs(int u, int p){
	id[u] = tin[u] = tout[u] = T++;
	for(auto v : g[u]) if(v != p){
		dfs(v,u);
		par[v] = u;
		tout[u] = tout[v];
	}
}
 
void solve(){
	int n,q;
	cin >> n >> q;
	vector<int> p(n+1);
	for(int i = 0; i <= n; i++) g[i].clear();
	T = 0;
	for(int i = 2; i <= n; i++){
		int pi;
		cin >> pi;
		g[pi].push_back(i);
	}
	for(int i = 1; i <= n; i++){
		cin >> p[i];
	}
	dfs(1,1);
	int cnt = 0;
	auto ok = [&](int i){
		if(p[i] == 1){
			if(i == 1) return 1;
			return 0;
		}
		int ant = p[i-1];
		if(par[p[i]] == ant) return 1;
		if(tin[ant] != tout[ant]) return 0;
		int pa = par[p[i]];
		if(tin[ant] < tin[pa] || tin[ant] > tout[pa]) return 0;
		return 1;
	};
	for(int i = 1; i <= n; i++){
		cnt += ok(i);
	}
	for(int qw = 0; qw < q; qw++){
		int x,y;
		cin >> x >> y;
		set<int> in;
		in.insert(x);
		in.insert(y);
		if(x-1 >= 1) in.insert(x-1);
		if(x+1 <= n) in.insert(x+1);
		if(y-1 >= 1) in.insert(y-1);
		if(y+1 <= n) in.insert(y+1);
		for(auto v : in){
			cnt -= ok(v);
		}
		swap(p[x],p[y]);
		for(auto v : in){
			cnt += ok(v);
		}
		cout << (cnt == n ? "YES": "NO") << '\n';
	}
	
}
 
signed main(){
 
    ios::sync_with_stdio(false); cin.tie(NULL);
 
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
 
    return 0;
}

Consider an incremental solution.

Use stacks.

The problems asks for the answer for every prefix, which hints at an incremental solution.

To add a new pair to the current prefix, we need to somehow process the new block merging with old ones. Thus, we should use some structure to store the information on the last block over time.

Namely, we use a stack to keep track of all blocks that became the last. For each block, we keep two values: its color $$$c$$$ and its lifetime $$$l$$$ (the times it takes for the block to disappear).

When inserting a new block, we pop all blocks that would be shadowed by the current one (i.e. with lifetime shorter than the current block), and merging blocks with the same $$$a$$$. When merging two blocks with length $$$x$$$ and $$$z$$$, and the maximum lifetime of blocks between them is $$$y$$$, $$$y\le\min(x,z)$$$ should hold, and the new block will have lifetime $$$x+z-y$$$.

For more details, please refer to the solution code.

There also exists $$$O(n\log n)$$$ solutions using ordered sets or heaps.

Time complexity: $$$O(n)$$$.

#include <bits/stdc++.h>
#define N 1000011
#define ll long long
#define pii pair<ll,int>
#define s1 first
#define s2 second
using namespace std;
int t, n, b[N];
ll a[N];
pii s[N];
int sn;
int main() {
    scanf("%d", &t);

    while (t--) {
        scanf("%d", &n);

        for (int i = 1; i <= n; ++i)
            scanf("%lld%d", a + i, b + i);

        sn = 0;
        ll x = 0;

        for (int i = 1; i <= n; ++i) {
            ll mx = 0;

            while (sn) {
                if (s[sn].s2 == b[i])
                    a[i] += s[sn--].s1 - mx;
                else if (s[sn].s1 <= a[i])
                    mx = max(mx, s[sn--].s1);
                else
                    break;
            }

            ++sn;
            s[sn] = pii(a[i], b[i]);
            x = max(x, s[sn].s1);
            printf("%lld ", x);
        }

        putchar(10);
    }

    return 0;
}

#include <bits/stdc++.h>
#define ll long long
#define N 3000011
#define pii pair<ll,int>
#define s1 first
#define s2 second
using namespace std;
int t, n, prv[N], nxt[N], b[N];
ll a[N];
priority_queue<pair<ll, int>> pq, del;
ll sum = 0, ans[N];
int main() {
    scanf("%d", &t);

    while (t--) {
        scanf("%d", &n);

        for (int i = 1; i <= n; ++i)
            scanf("%lld%d", a + i, b + i);

        while (!pq.empty())
            pq.pop();

        while (!del.empty())
            del.pop();

        nxt[0] = 1;
        prv[n + 1] = n;

        for (int i = 1; i <= n; ++i)
            pq.push({-a[i], i}), prv[i] = i - 1, nxt[i] = i + 1;
        ll tim = 0;
        int lst = 1;

        for (int _ = 1; _ <= n; ++_) {
            while (!del.empty() && pq.top() == del.top())
                pq.pop(), del.pop();

            pii p = pq.top();
            pq.pop();
            int id = p.s2;
            tim = -p.s1;

            if (nxt[id] <= n && b[id] == b[nxt[id]]) {
                a[nxt[id]] += tim;
                pq.push({-a[nxt[id]], nxt[id]});
            }

            if (prv[id] && nxt[id] <= n && b[prv[id]] == b[nxt[id]]) {
                del.push({-a[nxt[id]], nxt[id]});
                a[nxt[id]] -= tim;
            }

            prv[nxt[id]] = prv[id];
            nxt[prv[id]] = nxt[id];

            while (lst < nxt[0])
                ans[lst++] = tim;
        }

        for (int i = 1; i <= n; ++i)
            printf("%lld ", ans[i]);

        putchar(10);
    }

    return 0;
}

Primes are powerful.

Prime gaps are small.

We view the problem as a walk on grid, starting at $$$(1,1)$$$. WLOG, we suppose $$$l \gt f$$$, thus only cells $$$(a,b)$$$ where $$$a \lt b$$$ would be considered.

Notice that when $$$n$$$ is large enough, the largest prime $$$p\le n$$$ satisfies $$$2p \gt n$$$. As such, all cells $$$(p,i)$$$ where $$$i \lt p$$$ will be unblocked and reachable.

However, we've only bounded one side of the final result. We take this a step further, let $$$q$$$ be the second-largest prime $$$q\le n$$$. By the same logic, we assume that $$$2q \gt n$$$. As such, all cells $$$(i,q)$$$, where $$$p\le i\le n$$$ will be unblocked and reachable.

Thus, we have constructed an area where the optimal solution must be, with its dimensions bounded by $$$n-p$$$ and $$$n-q$$$. We just need to run any brute force solution (dfs with memorization or dp) on this area to find the result.

If we assume the asymptotic of prime gap is $$$O(P(n))$$$, this yields a $$$O(n\cdot P(n)^2\cdot\log P(n))$$$ solution, where the $$$\log\log n$$$ is from taking the gcd of two numbers which differ by $$$O(P(n))$$$. This can also be optimized to $$$O(n\cdot P(n)^2)$$$ by preprocessing gcd.

We added the constraints that $$$n$$$'s are pairwise distinct to avoid forcing participants to write memorizations. In fact, under the constraints of the problem, the maximum area is $$$39201$$$, and the sum of the $$$10^3$$$ largest areas is $$$2.36\times10^7$$$.

Time complexity: $$$O(P(n)^2\log P(n))/O(P(n)^2)$$$

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2e7 + 5;
bool ntp[N];
int di[405][405];
bool bad[405][405];
int pos[N], g = 0, m = 3;
int prime[2000005], cnt = 0;
void sieve(int n) {
    int i, j;

    for (i = 2; i <= n; i++) {
        if (!ntp[i])
            prime[++cnt] = i;

        for (j = 1; j <= cnt && i * prime[j] <= n; j++) {
            ntp[i * prime[j]] = 1;

            if (!(i % prime[j]))
                break;
        }
    }
}
int gcd(int x, int y) {
    if (!x)
        return y;

    if (x <= g && y <= g)
        return di[x][y];

    return gcd(y % x, x);
}

int main() {
    sieve(2e7);
    int i, j = 1, T, n, a, b, c, u, v;
    ll ans;

    for (i = 3; i <= 2e7; i++) {
        while (j < cnt - 1 && prime[j + 2] <= i)
            j++;

        g = max(g, i - prime[j] + 1);

        if (prime[j] * 2 <= i)
            m = i;

        pos[i] = j;
    }

    for (i = 0; i <= g; i++)
        for (j = 0; j <= g; j++)
            if (!i)
                di[i][j] = j;
            else
                di[i][j] = di[j % i][i];

    scanf("%d", &T);

    while (T--) {
        scanf("%*d%d%d%d", &n, &a, &b);

        if (n <= m)
            u = v = 1;
        else {
            u = prime[pos[n] + 1];
            v = prime[pos[n]];
        }

        ans = 0;

        for (i = u; i <= n; i++)
            for (j = v; j <= i; j++) {
                bad[i - u + 1][j - v + 1] = (gcd(i, j) > 1 || (bad[i - u][j - v + 1] && bad[i - u + 1][j - v]));

                if (!bad[i - u + 1][j - v + 1])
                    ans = max(ans, max((ll)a * i + (ll)b * j, (ll)a * j + (ll)b * i));
            }

        printf("%lld\n", ans);
    }

    return 0;
}

Try generalizing the solution of F1.

Write anything and pray that it will pass because of number theory magic.

We generalize the solution in F1. Let $$$p$$$ be the largest prime $$$\le m$$$ and $$$q$$$ be the largest prime $$$\le\min(n,p-1)$$$. The problem is that there might be $$$\gcd(q,i)\neq1$$$ for some $$$p+1\le i\le m$$$, thus invalidating our previous analysis.

To solve this, we simply choose $$$q$$$ to be the largest integer such that $$$q\le n$$$ and $$$\gcd(q,i)=1$$$ for all $$$p+1\le i\le m$$$. An asymptotic analysis of this solution is as follows:

As the length of $$$[p+1,m]$$$ is $$$O(P(m))$$$, and each of these integers have at most $$$O(\log_nm)$$$ prime divisors of $$$O(m)$$$ magnitude, which means that if we only restrict $$$q$$$ to primes, we will have to skip at most $$$O(P(n)\log_nm)$$$ primes to find the largest $$$q$$$. As the density of primes is $$$O(\frac1{P(n)})$$$, the asymptotic of $$$n-q$$$ will be $$$O(P(m)\log_nm\cdot P(n))=O(P(m)^2)$$$, our actual $$$q$$$ (which is not restricted to primes) will not be worse than this. Thus, our total area will be $$$O(P(m)^3)$$$, times the gcd complexity gives us an $$$O(P(m)^3\log m)$$$ solution. However, the actual area is much lower than this.

Under the constraints of the problem, when forcing $$$p,q$$$ to take primes, the maximum area is $$$39960$$$, and the sum of the $$$10^3$$$ largest areas is $$$3.44\times10^7$$$. The actual solution will not be worse than this.

Because we only need to check whether $$$\gcd(x,y)=1$$$, the complexity can actually be optimized to $$$O(P(m)^3)$$$ with some sieves. Namely, iterating over prime divisors $$$d$$$ of $$$[p,m]$$$ and $$$[q,n]$$$ and marking all cells which has $$$d$$$ as its common divisor.

This solution is by far from optimal. We invite you to continue optimizing your solutions and try to minimize the number of cells visited in each query :)

Time complexity: $$$O(P(m)^3\log m)$$$

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2e7 + 5;
bool ntp[N];
bool bad[405][405];
int pos[N];
int prime[2000005], mn[N], cnt;
void sieve(int n) {
    int i, j;

    for (i = 2; i <= n; i++) {
        if (!ntp[i])
            prime[++cnt] = i, mn[i] = i;

        for (j = 1; j <= cnt && i * prime[j] <= n; j++) {
            mn[i * prime[j]] = prime[j];
            ntp[i * prime[j]] = 1;

            if (!(i % prime[j]))
                break;
        }
    }
}
int gcd(int x, int y) {
    return x ? gcd(y % x, x) : y;
}
bool no(int l, int r, int k) {
    while (k > 1) {
        int x = mn[k];

        while (k % x == 0)
            k /= x;

        if (((l + x - 1) / x) * x <= r)
            return 0;
    }

    return 1;
}

int main() {
    sieve(20000000);
    int i, j = 0, T, n, m, a, b, u, v, g = 0, S = 0, px, py, qwq = 0;
    ll ans;
    prime[0] = 1;

    for (i = 2; i <= 20000000; i++) {
        while (j < cnt && prime[j + 1] <= i)
            j++;

        pos[i] = j;
    }

    scanf("%d", &T);

    while (T--) {
        scanf("%d%d%d%d", &n, &m, &a, &b);

        if (n < m) {
            swap(n, m);
            swap(a, b);
        }

        u = prime[pos[n]];
        v = m;

        while (v && !no(u, n, v))
            v--;

        ans = 0;
        px = py = 0;

        for (i = u; i <= n; i++)
            for (j = v; j <= m && j <= i; j++) {
                bad[i - u + 1][j - v + 1] = ((bad[i - u][j - v + 1] && bad[i - u + 1][j - v]) || gcd(i, j) > 1);

                if (!bad[i - u + 1][j - v + 1]) {
                    ans = max(ans, (ll)a * i + (ll)b * j);

                    if ((ll)a * i + (ll)b * j == ans) {
                        px = i;
                        py = j;
                    }

                    if (i <= m)
                        ans = max(ans, (ll)a * j + (ll)b * i);
                }
            }

        qwq = max(qwq, (n - px) + (m - py));
        printf("%lld\n", ans);
    }
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
#define N 20000011
using namespace std;
int t, n, m, a, b;
bool is[N];
int pr[N / 10];
int gcd(int a, int b) {
    while (b)
        a %= b, swap(a, b);

    return a;
}
ll ans = 0;
bool vis[1011][1011];
pair<int, int> vv[200011];
int vn, c;
bool flg = 0;
inline ll V(int i, int j) {
    return i <= n ? 1ll * max(i, j) * max(a, b) + 1ll * min(i, j) * min(a, b) : 1ll * i * b + 1ll * j * a;
}
void dfs(int i, int j) {
    ++c;
    bool mk = gcd(i, j) == 1;

    if (!mk)
        return;

    ans = max(ans, V(i, j));
    vis[m - i][n - j] = 1;
    vv[++vn] = {i, j};

    if (j < n && !vis[m - i][n - j - 1])
        dfs(i, j + 1);

    if (i == m || flg) {
        flg = 1;
        return;
    }

    if (i < m && !vis[m - i - 1][n - j])
        dfs(i + 1, j);
}
int main() {
    is[0] = is[1] = 1;

    for (int i = 2; i < N; ++i) {
        if (!is[i])
            pr[++pr[0]] = i;

        for (int j = 1; j <= pr[0] && i * pr[j] < N; ++j) {
            is[i * pr[j]] = 1;

            if (i % pr[j] == 0)
                break;
        }
    }

    scanf("%d", &t);

    while (t--) {
        scanf("%d%d%d%d", &n, &m, &a, &b);
        int p;

        if (m <= 10)
            p = 1;
        else {
            p = m;

            while (is[p])
                --p;
        }

        vn = 0;
        ans = 0;
        flg = 0;
        c = 0;

        for (int i = min(n, p - (p > 1));; --i) {
            assert(i > 0);
            ans = max(ans, V(p, i));

            if (p < m)
                dfs(p + 1, i);
            else
                break;

            if (flg)
                break;
        }

        for (int i = 1; i <= vn; ++i)
            vis[m - vv[i].first][n - vv[i].second] = 0;

        printf("%lld\n", ans);
    }

    return 0;
}

Meet in the middle with a twist.

Union of sets is hard. Disjoint union of sets is easy.

The problem hints strongly at meet in the middle, at each side, there will be $$$O(2^n)$$$ paths. The twist is on merging: we are given two sequence of sets $$$S_1,S_2,\cdots$$$ and $$$T_1,T_2,\cdots$$$, we have to find the maximum $$$\textrm{MEX}(S_i\cup T_j)$$$.

If we enumerate over the maximum MEX $$$P$$$, we only need to check whether there exists two sets such that $$$\{ 0,1,\cdots,P-1\} \subseteq S_i\cup T_j$$$.

Instead of meeting at $$$n$$$, we perform meet in the middle at the partition of $$$Bn$$$ and $$$(2-B)n$$$. For each $$$S_i$$$, we put all its subsets $$$S^\prime_i$$$ into a hashmap. When checking MEX $$$P$$$, we iterate over all $$$T_j$$$, and check whether $$$\{ 0,1,\cdots,P-1\} -T_j$$$ is in the hashmap. This gives us a $$$O((2^{2Bn}+2^{(2-B)n})\cdot n)$$$ solution, which is optimal at $$$B=\frac23$$$, where the complexity is $$$O(2^{\frac43}\cdot n)$$$.

We can substitute enumerating $$$P$$$ with binary search, yielding $$$O(2^{\frac43n}\cdot\log n)$$$, or checking whether $$$P$$$ can be increased each time, yielding $$$O(2^{\frac43n})$$$.

Instead of hashmaps, you can also insert all $$$S$$$ and $$$T$$$'s into a trie, and run a brute force dfs to search for MEX $$$P$$$. It can be proven that the complexity is also $$$O(2^{\frac43n}\cdot n)$$$.

The intended solution is $$$O(2^{\frac43 n})$$$, however solutions that have slightly higher complexity can pass with good optimizations.

Time complexity: $$$O(2^{\frac43n})$$$.

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int D[111][111], R[111][111], n;
const int P = 30000019;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
} HH;
int sta[P], top;
struct uset {
    struct edge {
        pair<int, ll> v;
        int next;
        edge() {} edge(pair<int, ll> _v, int _next) {
            v = _v;
            next = _next;
        }
    } e[20000011];
    int head[P], sz;
    uset() {
        memset(head, -1, sizeof(head));
        sz = 0;
    }
    void insert(pair<int, ll> x) {
        int u = HH(x.second * n + x.first) % P;
        sta[++top] = u;

        for (int i = head[u]; ~i; i = e[i].next)
            if (e[i].v == x)
                return;

        e[++sz] = edge(x, head[u]);
        head[u] = sz;
    }
    bool find(pair<int, ll> x) {
        int u = HH(x.second * n + x.first) % P;

        for (int i = head[u]; ~i; i = e[i].next)
            if (e[i].v == x)
                return 1;

        return 0;
    }
} st;
int B;
void dfs1(int x, int y, ll S, int tp) {
    if (x + y == B) {
        st.insert({x, S});
        return;
    }

    if (y < n) {
        dfs1(x, y + 1, S, 0);
        dfs1(x, y + 1, S | 1ll << R[x][y], -1);
    }

    if (x < n) {
        if (tp != 0)
            dfs1(x + 1, y, S, 1);

        dfs1(x + 1, y, S | 1ll << D[x][y], -1);
    }
}
int ans = 0;
void dfs2(int x, int y, ll S) {
    if (x + y == B) {
        int res = 0;

        while (ans <= 2 * n - 2) {
            if (st.find({x, (~S) & (1ll << (ans + 1)) - 1}))
                ans++;
            else
                break;
        }

        return;
    }

    if (x > 1)
        dfs2(x - 1, y, S | 1ll << D[x - 1][y]);

    if (y > 1)
        dfs2(x, y - 1, S | 1ll << R[x][y - 1]);
}
void solve() {
    while (top)
        st.head[sta[top--]] = -1;

    st.sz = 0;
    ans = 0;
    scanf("%d", &n);

    for (int i = 1; i < n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", D[i] + j);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < n; ++j)
            scanf("%d", R[i] + j);

    B = 2 * n / 3 + 2;
    dfs1(1, 1, 0, -1);
    dfs2(n, n, 0);
    printf("%d\n", ans);
}
int main() {
    int T;
    scanf("%d", &T);

    while (T--)
        solve();

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
void dbg_out() {
    cerr << endl;
}
template <typename H, typename... T>
void dbg_out(H h, T... t) {
    cerr << ' ' << h;
    dbg_out(t...);
}
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
using ll = long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 3e7 + 5;
const int MOD = 1e9 + 7; //998244353;
const int INF = 0x3f3f3f3f;
const ll INF64 = ll(4e18) + 5;

int D[40][40];
int R[40][40];

int L;

int32_t trie[MAXN][2];
int n;
int li = 1;
void add(int x) {
    int at = 0;
    int K = 2 * n - 2;

    for (int i = 0; i <= K; i++) {
        int id = (x >> i) & 1;

        if (trie[at][id] == 0) {
            trie[at][id] = li++;
        }

        at = trie[at][id];
    }
}

void limpa() {
    for (int i = 0; i < li; i++) {
        trie[i][0] = trie[i][1] = 0;
    }

    li = 1;
}

int query(int at, int x, int dep) {
    int id = (x >> dep) & 1;

    if (id == 0) {
        if (trie[at][1]) {
            return query(trie[at][1], x, dep + 1);
        }

        return dep;
    }

    int ans = dep;

    if (trie[at][0])
        ans = max(ans, query(trie[at][0], x, dep + 1));

    if (trie[at][1])
        ans = max(ans, query(trie[at][1], x, dep + 1));

    while ((x >> ans) & 1)
        ans++;

    return ans;
}

void rec_in(int i, int j, int tar1, int tar2, int v) {
    if (i > tar1 || j > tar2)
        return;

    if (i == tar1 && j == tar2) {
        add(v);
    }

    int right = v | (1ll << R[i][j]);
    int down = v | (1ll << D[i][j]);
    rec_in(i + 1, j, tar1, tar2, down);
    rec_in(i, j + 1, tar1, tar2, right);
}

int ANS = 0;
void rec_out(int i, int j, int tar1, int tar2, int v) {
    if (i < tar1 || j < tar2)
        return;

    if (i == tar1 && j == tar2) {
        ANS = max(ANS, query(0, v, 0));
        return;
    }

    int left = v | (1ll << R[i][j - 1]);
    int up = v | (1ll << D[i - 1][j]);
    rec_out(i - 1, j, tar1, tar2, up);
    rec_out(i, j - 1, tar1, tar2, left);
}

void solve() {
    ANS = 0;

    for (int i = 1; i <= li; i++)
        trie[i][0] = trie[i][1] = 0;

    li = 1;
    cin >> n;
    L = 4 * n / 3;

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n; j++) {
            cin >> D[i][j];
        }
    }

    if (L > n) {
        L--;
    }

    if (L > n) {
        L--;
    }

    if (L > n) {
        L--;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            cin >> R[i][j];
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i + j == L) {
                limpa();
                rec_in(0, 0, i, j, 0);
                rec_out(n - 1, n - 1, i, j, 0);
            }

    cout << ANS << '\n';

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

Try to solve Problem 101 with any approach.

Can you express the states in the solution for Problem 101 with some simple structures? Maybe dp of dp?

Try finding some unnecessary states and pruning them, to knock a $$$n$$$ off the complexity.

We analyse Problem 101 first. A dp solution will be, let $$$f_{l,r,v}$$$ be the minimum number of elements left after some operations, if we only consider elements in $$$a[l:r]$$$, without creating any elements $$$ \gt v$$$. If $$$\max(a[l:r]) \lt v$$$, then the answer is $$$1$$$ if $$$r-l+1$$$ is odd, and $$$2$$$ otherwise. We simply repeatedly perform operations with middle element as the center. It is easy to see that this is optimal.

If $$$\max(a[l:r])=v$$$, then $$$a[l:r]$$$ will be partitioned into blocks by elements equal to $$$v$$$. Denote the length of the blocks as $$$y_1,y_2,\cdots,y_l$$$. Let $$$b_i$$$ be the number of operations that has the $$$i$$$-th element with value $$$v$$$ as its center.

We can perform a dp as follows: let $$$g_{i,j}$$$ be the minimum number of elements left if we have already considered the first $$$i$$$ blocks, and $$$b_i=j$$$.

When adding a new block, we need to know several things:

• $$$[l^\prime,r^\prime]$$$, the minimum/maximum number of elements of the new block after some operations, without creating an element greater than $$$v-1$$$.

• $$$j_2$$$, the value of $$$b_{i+1}$$$.

The transition of the dp will be: $$$g_{i+1,j_2}=g_{i,j_1}+cost(j_1+j_2,l^\prime,r^\prime)$$$, where $$$cost(j,l,r)$$$ is defined as follows:

The $$$cost$$$ function follows from the case where $$$\max(a) \lt v$$$.

Now, we have a solution to Problem 101. We now consider generalizing it to Counting 101.

We make some observations regarding the structure of $$$g$$$. If you printed a table of $$$g$$$, you would discover that for each $$$g_i$$$, if you subtract the minimum element from all $$$g_{i,j}$$$ in this row, you will get something like: $$$[\cdots,2,1,2,1,2,1,0,1,0,1,0,1,0,1,2,1,2,\cdots]$$$.

We can prove this by induction and some casework, which is omitted for brevity. If a $$$g_i$$$ satisfies this property, then we can express it with a triple $$$(l,r,mn)$$$, where $$$mn$$$ is the minimum element of $$$g_i$$$, and $$$l,r$$$ are the minimum/maximum $$$j$$$ such that $$$g_{i,j}=mn$$$.

Now that we can express the structure of each $$$g_i$$$ with a triple $$$(l,r,mn)$$$, we can run a dp of dp. Our state will be $$$dp_{i,v,l,r,mn}$$$, where $$$i$$$ is the current length, $$$v$$$ is the upper bound, and $$$(l,r,mn)$$$ describes the current $$$g$$$. For each transition, we need to enumerate $$$l^\prime,r^\prime$$$, and the new $$$(l,r,mn)$$$ can be found in $$$O(1)$$$ with some casework. This gives us an $$$O(n^6m)$$$ solution.

Now to optimize the solution. We optimize the solution by reducing the number of viable states. Suppose we have a state $$$+(l,r,mn)$$$, we claim, that the answer will remain the same if we replace it with $$$+(l,\infty,mn)+(l\bmod2,r,mn)-(l\bmod2,\infty,mn)$$$.

We prove this by examining their behaviour when we add any number of blocks after them. If the answer remains unchanged for any blocks we can add, then the claim stands. Suppose we are at $$$g_i$$$, and we will add a sequence of blocks $$$S$$$ after $$$g_i$$$. The final answer can be found by running a backwards dp similar to $$$g$$$, on $$$\text{rev}(S)$$$, and merging with $$$g_i$$$ in the middle.

If we denote the backwards dp as $$$g^\prime$$$, then the answer will be $$$\min(g_j+g^\prime_j)$$$ over all $$$j$$$. It can be shown after some brief casework (using $$$g$$$'s structure), that there exists an optimal $$$j$$$ where $$$g_{i,j}$$$ is the minimum of $$$g_i$$$, thus the answer is just a range (with a certain parity) min of $$$g^\prime$$$, plus $$$mn$$$. Because $$$g^\prime$$$ also follow $$$g$$$'s structure, any range will be first decreasing, then increasing. It can be shown with these properties, $$$\min(g^\prime[l:r])=\min(g^\prime[l:\infty])+\min(g^\prime[l\bmod2:r])-\min(g^\prime[l\bmod2:\infty])$$$. Thus, our answer will not change when substituting the states.

After substituting, the total number of different $$$l,r$$$ pairs will be $$$O(n)$$$, which yields an $$$O(n^5m)$$$ solution.

The solution can also be optimized to $$$O(n^4m)$$$ using Lagrange Interpolation, but it actually runs slower than $$$O(n^5m)$$$ because of large constants (or bad implementation by setters).

#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
#define pb emplace_back
using namespace std;
const int N = 133, mod = 1e9 + 7;
struct mint {
    int x;
    inline mint(int o = 0) {
        x = o;
    }
    inline mint &operator = (int o) {
        return x = o, *this;
    }
    inline mint &operator += (mint o) {
        return (x += o.x) >= mod && (x -= mod), *this;
    }
    inline mint &operator -= (mint o) {
        return (x -= o.x) < 0 && (x += mod), *this;
    }
    inline mint &operator *= (mint o) {
        return x = (ll) x * o.x % mod, *this;
    }
    inline mint &operator ^= (int b) {
        mint w = *this;
        mint ret(1);

        for (; b; b >>= 1, w *= w)
            if (b & 1)
                ret *= w;

        return x = ret.x, *this;
    }
    inline mint &operator /= (mint o) {
        return *this *= (o ^= (mod - 2));
    }
    friend inline mint operator + (mint a, mint b) {
        return a += b;
    }
    friend inline mint operator - (mint a, mint b) {
        return a -= b;
    }
    friend inline mint operator * (mint a, mint b) {
        return a *= b;
    }
    friend inline mint operator / (mint a, mint b) {
        return a /= b;
    }
    friend inline mint operator ^ (mint a, int b) {
        return a ^= b;
    }
};
inline mint qpow(mint x, int y = mod - 2) {
    return x ^ y;
}
mint fac[N], ifac[N], inv[N];
void init(int x) {
    fac[0] = ifac[0] = inv[1] = 1;
    L(i, 2, x) inv[i] = (mod - mod / i) * inv[mod % i];
    L(i, 1, x) fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * inv[i];
}
mint C(int x, int y) {
    return x < y || y < 0 ? 0 : fac[x] * ifac[y] * ifac[x - y];
}
inline mint sgn(int x) {
    return (x & 1) ? mod - 1 : 1;
}

int n, m;
mint f[N][N];
mint g[N][N];
mint h1[N][N][N];
mint h2[N][N][N];
mint pw[N][N];
int ans[N][N][N];
int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n = 130, m = 30;
    // n = m = 10;
    L(i, 0, max(n, m)) {
        pw[i][0] = 1;
        L(j, 1, max(n, m)) pw[i][j] = pw[i][j - 1] * i;
    }
    f[0][0] = 1;
    int c1 = 0, c2 = 0;
    L(test, 1, m) {
        me(g, 0);
        int up = n;
        L(i, 0, up + 1) L(j, 0, i) L(l, 0, i) h1[i][j][l] = h2[i][j][l] = 0;
        h2[0][0][0] = 1;
        L(i, 0, up + 1) {
            L(j, 0, i) L(l, 0, i) h1[i][j][l & 1] -= h1[i][j][l];
            L(j, 0, i) {
                for (int l = (i - j) & 1; l <= i; l += 2)
                    if (h1[i][j][l].x) {
                        L(k, 0, up - i) {
                            if (l > k) {
                                int tr = k - !(l & 1);

                                if (tr < 0)
                                    h2[i + k + 1][j + 3][0] += h1[i][j][l] * pw[test - 1][k];
                                else
                                    h2[i + k + 1][j + 2][tr] += h1[i][j][l] * pw[test - 1][k];
                            } else {
                                h2[i + k + 1][j + 1][k - l] += h1[i][j][l] * pw[test - 1][k];
                            }
                        }
                    }

                for (int r = (i - j) & 1; r <= i; r += 2)
                    if (h2[i][j][r].x) {
                        int l = r & 1;
                        L(k, 0, up - i) {
                            if (l > k) {
                                int tr = k - !(r & 1);

                                if (tr < 0)
                                    h2[i + k + 1][j + 3][0] += h2[i][j][r] * pw[test - 1][k];
                                else
                                    h2[i + k + 1][j + 2][tr] += h2[i][j][r] * pw[test - 1][k];
                            } else {
                                h2[i + k + 1][j + 1][k - l] += h2[i][j][r] * pw[test - 1][k];

                                L(d, r + 1, k) if (f[k][d].x)
                                    h1[i + k + 1][j + 1][d - r] += h2[i][j][r] * f[k][d];
                            }
                        }
                    }
            }
        }
        // cout << "H = " << h[1][1][0][0].x << endl;
        L(i, 1, up + 1)
        L(j, 1, i) {

            L(l, 0, i) if (h1[i][j][l].x) {
                if (!l)
                    g[i - 1][j - 1] += h1[i][j][l];
                else
                    g[i - 1][j - 1 + (l % 2 == 0 ? 2 : 1)] += h1[i][j][l];
            }

            L(r, 0, i) if (h2[i][j][r].x) {
                if (!(r & 1))
                    g[i - 1][j - 1] += h2[i][j][r];
                else
                    g[i - 1][j - 1 + (r % 2 == 0 ? 2 : 1)] += h2[i][j][r];
            }
        }
        L(i, 1, up) {
            mint vl = 0;

            if (i == 1)
                vl = test;
            else if (i % 2 == 1) {
                vl += pw[test - 1][i];
                L(p, 1, i - 2) {
                    int l = p, r = i - p - 1;

                    if (l > r)
                        swap(l, r);

                    L(j, 1, l) {
                        vl += f[r][j] * pw[test - 1][l];
                    }
                }
            }

            g[i][1] = vl;
            mint sum = 0;
            L(j, 1, i) sum += g[i][j];
            int pos = (i & 1) ? 3 : 2;
            g[i][pos] += pw[test][i] - sum;
        }
        swap(f, g);

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                ans[test][i][j] = f[i][j].x;
            }
        }
    }
    // cout << "clock = " << clock() << endl;
    int T;
    cin >> T;

    while (T--) {
        int N, M;
        cin >> N >> M;
        L(i, 0, (N - 1) / 2)
        cout << ans[M][N][N - i * 2] << " ";
        cout << '\n';
    }

    return 0;
}