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)$$$.

#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;
}

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);
	}
}