• Great contest
• Good contest
• Average contest
• Bad contest

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

If the sequence $$$a$$$ consists entirely of $$$1$$$ s, what will Alice do?

Consider discussing the values of $$$a_1$$$ and $$$a_n$$$.

First, if the entire sequence consists of $$$1$$$ s, Alice wins immediately by operating on the whole sequence.

Note that the last operation must involve at least one of $$$a_1$$$ or $$$a_n$$$. We discuss based on the values of $$$a_1$$$ and $$$a_n$$$:

If $$$a_1 = 1$$$, then Alice can directly operate on the interval $$$[2,n]$$$ to win, because $$$a_{2 \sim n}$$$ must contain at least one $$$0$$$.

If $$$a_n = 1$$$, then Alice can directly operate on the interval $$$[1,n-1]$$$ to win, because $$$a_{1 \sim n-1}$$$ must contain at least one $$$0$$$.

If $$$a_1 = 0$$$ and $$$a_n = 0$$$, then operating on the entire sequence would certainly cause Alice to lose. This implies that Alice cannot operate on both $$$a_1$$$ and $$$a_n$$$ simultaneously. Therefore, after Alice's operation, there will still be at least one $$$0$$$ in the sequence $$$a$$$. Bob can then operate on the entire sequence to win. Hence, in this case, Bob wins.

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

#include<bits/stdc++.h>
using namespace std;
int _t_,n,a[100010];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    if(a[1]+a[n]==0)
        cout<<"NO\n";
    else
        cout<<"YES\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>_t_;
    while(_t_--)
        solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Considering that in the end only $$$k - 1$$$ numbers will remain, which numbers in an interval of length $$$k$$$ are invalid?

Consider the Pigeonhole Principle.

Since only $$$k - 1$$$ numbers will remain in the end, it is relatively easy to notice that for any interval of length $$$k$$$, numbers within this interval that are greater than or equal to $$$k-1$$$ or have duplicate values are invalid. One of these two types of numbers can be removed. Since there are only $$$k - 1$$$ numbers from $$$0$$$ to $$$k-2$$$, in any interval of length $$$k$$$, there must be at least one number that can be deleted. Therefore, the answer is $$$\min(\text{mex}(a), k-1)$$$.

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

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
ll _t_;
ll n,m;
ll maxn;
ll a[1000010];
ll b[1000010];
void _clear(){}
void solve()
{
    _clear();
    cin>>n>>m;
    forl(i,1,n)
        cin>>a[i],a[i]=min(a[i],n+1);
    forl(i,0,n+5)
    	b[i]=0;
    ll mex=0;
	forl(i,1,n)
		b[a[i]]++;
	while(b[mex])
		mex++;
	cout<<min(mex,m-1)<<endl; 
}
int main()
{
    IOS;
    _t_=1;
    cin>>_t_;
    while(_t_--)
        solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider a greedy algorithm.

What shape must the finally occupied bases take?

If the capital is the first city (i.e., $$$k=1$$$), how to solve it?

The finally occupied bases must form an interval containing $$$k$$$.

If the finally occupied bases do not form an interval containing $$$k$$$, then there must exist some $$$x, y$$$ such that $$$1 \le x \lt y \lt k$$$ or $$$k \lt y \lt x \le n$$$, with $$$x$$$ occupied and $$$y$$$ unoccupied. Consider a soldier at $$$y$$$ starting from $$$k$$$ and moving to $$$x$$$; it must pass through base $$$x$$$ along the way. Consider making this soldier stop exactly at $$$x$$$. Then soldier $$$y$$$ ends up at $$$x$$$. After a finite number of such adjustments, we will reach a state where no further adjustment is possible, which implies the finally occupied bases must be an interval containing $$$k$$$.

Suppose this interval contains $$$a$$$ positions to the left of $$$k$$$ and $$$b$$$ positions to the right of $$$k$$$ (excluding $$$k$$$ itself) ($$$0 \le a \le k-1$$$, $$$0 \le b \le n-k$$$). It is possible to occupy this interval if and only if $$$a + b + \max(a, b) - 1 \le m$$$.

Sufficiency:

We can imagine a simple strategy. Initially, we do nothing until the capital contains $$$a$$$ soldiers. Then we move $$$a$$$ soldiers from $$$k$$$ to $$$k-1$$$, then move $$$a-1$$$ soldiers from $$$k-1$$$ to $$$k-2$$$, and so on. Thus $$$k-1, k-2, \ldots, k-a$$$ are all filled with soldiers. Then we wait (if necessary) until the capital contains $$$b$$$ soldiers and move them in the same way to $$$k+1, \ldots, k+b$$$. It can be observed that this strategy requires exactly $$$a + b + \max(a, b) - 1$$$ days.

Necessity:

We prove that for any strategy, the required number of days $$$m$$$ is at least $$$a + b + \max(a, b) - 1$$$.

First, we need at least $$$a+b$$$ days to obtain the extra $$$a+b$$$ soldiers. Second, we cannot move new soldiers to new bases every moment. In fact, we can prove that there are at least $$$\max(a, b) - 1$$$ idle days. The proof is as follows.

Assume without loss of generality that $$$a \ge b$$$.

Define the potential function $$$h(S)$$$ of a state $$$S$$$ as the number of soldiers minus the number of occupied bases.

Suppose the first move to the left is moving $$$t$$$ soldiers to the leftmost consecutive $$$t$$$ positions $$$k-a, \ldots, k-a+t-1$$$.

(If the move is not to the leftmost positions but to some intermediate positions, we can show through adjustment that such a move is suboptimal. Therefore, an optimal solution will not contain such moves.)

Let $$$S_0$$$ be the state before the move, $$$S_1$$$ be the state when moving $$$t$$$ soldiers to $$$k-a+t$$$, $$$S_2$$$ be the state after completing the move of all $$$t$$$ soldiers, and $$$S_3$$$ be the final state.

We have $$$h(S_2) = h(S_1)$$$, $$$h(S_3) \ge h(S_2)$$$.

$$$h(S_1) - h(S_0) \ge a - t$$$ (during the intermediate $$$a-t$$$ steps, the potential increases each time).

$$$h(S_0) \ge t - 1$$$ (at least $$$t$$$ movable soldiers are needed).

Summing up, we get $$$h(S_3) \ge a - 1$$$. Therefore, the number of days needed is at least $$$2a + b - 1$$$.

In summary, at least $$$a + b + \max(a, b) - 1$$$ days are required.

We consider a greedy approach. First, if $$$k-1 \lt n-k$$$, we replace $$$k$$$ with $$$n+1-k$$$.

We define two variables $$$a$$$ and $$$b$$$, representing how many cells have been extended to the left and right, respectively. Initially, $$$a = 0$$$, $$$b = 0$$$. Then we repeatedly try to increase $$$a$$$ and $$$b$$$ by $$$1$$$ in turns. We first try to increase $$$b$$$ by $$$1$$$ (if $$$b \lt n-k$$$ and $$$a + (b+1) + \max(a, b+1) - 1 \le m$$$), then set $$$b$$$ to $$$b+1$$$. Next, we try to increase $$$a$$$ by $$$1$$$ (if $$$a \lt k-1$$$ and $$$(a+1) + b + \max(a+1, b) - 1 \le m$$$). If we cannot increase $$$a$$$, we break the loop. Finally, $$$a + b + 1$$$ (don't forget the home base) is the answer. The time complexity is $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
int n,k,m;
signed main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m>>k;
        if(k-1<n-k)k=n+1-k;
        int a=0,b=0;
        while(1){
            if(b<n-k&&a+(b+1)+max(a,b+1)-1<=m)++b;
            if(a<k-1&&(a+1)+b+max(a+1,b)-1<=m)++a;
            else break;
        }
        cout<<a+b+1<<endl;
    }
}

Solve the problem in $$$O(1)$$$ or $$$O(\log n)$$$ time per test case.

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider which points cannot be colored in the same operation.

Find a lower bound for the number of operations.

Suppose the number of points at depth $$$i$$$ is $$$t_i$$$. First, points at the same depth cannot be colored simultaneously, so the lower bound for the answer is $$$\max t_i$$$.

However, note that if points in layer $$$x$$$ share a common parent, they and their parent also cannot be colored simultaneously. Thus, the answer must also be compared with $$$\max(t_x + 1)$$$.

We claim this is the answer. Proof follows from the constructive proof in D2.

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

When can the minimum number of operations reach $$$\max t_i$$$? How much more than $$$\max t_i$$$ can it be at most?

We claim the maximum number of operations is $$$\max t_i + 1$$$. Consider the following constructive proof.

Let $$$S_i$$$ denote the set of points for the $$$i$$$ th operation.

Without loss of generality, let $$$T=\max t_i$$$. Find the largest $$$x$$$ such that $$$t_x=T$$$. Clearly, points with $$$d_i=x$$$ cannot be operated on simultaneously; we can place them into $$$S_1, S_2, \cdots, S_T$$$ respectively.

Then we only need to consider placing points of depth $$$\neq x$$$ into $$$S$$$. First, consider points of depth $$$ \gt x$$$. Suppose we have already placed all points of depth $$$k-1$$$. Now, when placing points of depth $$$k$$$, it is clear that each $$$S_i$$$ can contain at most one point of depth $$$k-1$$$.

Now, $$$t_{k-1}$$$ sets contain points of depth $$$k-1$$$, which impose constraints on the depth $$$k$$$ points to be placed; The remaining $$$T-t_{k-1}$$$ sets contain no points of depth $$$k-1$$$ and can freely add any point of depth $$$k$$$ (see the diagram below, where the upper red dots represent sets containing points of depth $$$k-1$$$, and the blue dots represent sets without such points).

For restricted sets (where children cannot be placed), we can retain only one child and place the others into unrestricted sets. Since the number of points in the lower layer is strictly less than $$$T$$$, at least one unrestricted set will remain. At this point, we can place each retained child into the set to its right.

Next, we construct the point of depth $$$ \lt x$$$. Suppose we have already constructed the point of depth $$$k+1$$$. Now we need to place the point of depth $$$k$$$ into a set. Clearly, there are $$$t_{k+1}$$$ sets with restrictions. Assume the current number of sets is $$$a = T$$$ or $$$T + 1$$$. The number of unrestricted sets is $$$c = a - t_{k+1}$$$. We proceed with some case analysis:

1. $$$a=T$$$ and $$$c=0$$$: All points at depth $$$k+1$$$ share a common parent.

This parent cannot be placed into any set. We set $$$a$$$ to $$$T+1$$$, place the parent into this new set, and assign the remaining points arbitrarily.

1. Points at depth $$$k$$$ have at least two non-leaf neighbors.

We can rotate these fathers into their children's sets, placing the remaining unrestricted nodes arbitrarily.

1. A node at depth $$$k$$$ has exactly one non-leaf child, and at least one set lacks any node at depth $$$k+1$$$.

Place this father into the set lacking a node at depth $$$k+1$$$, then place the remaining nodes arbitrarily.

The above process constructs a solution with either $$$T$$$ or $$$T+1$$$ sets. It yields $$$T+1$$$ sets precisely when there are $$$T$$$ points at the same depth with the same parent, making this process clearly optimal. These sets can be maintained in $$$O(n)$$$ or $$$O(n\log n)$$$ time.

Some bottom-up, directly greedy approaches are also valid, but their complexity is generally $$$O(n\log n)$$$.

This solution is from nldr.

Consider the construction scheme.

We assign each node $$$u$$$ a color $$$c_u \in {1, \dots, k}$$$ such that:

If $$$dep_u = dep_v$$$ and $$$u \neq v$$$, then $$$c_u \neq c_v$$$.

If $$$u$$$ is the parent node of $$$v$$$, then $$$c_u \neq c_v$$$.

Assign colors layer by layer based on depth. For each layer of $$$m$$$ nodes, convert it into a matching problem.

Select $$$m$$$ distinct colors from $$${1, \dots, k}$$$ to assign to these $$$m$$$ nodes, ensuring each node does not receive the color of its parent node.

Consider removing all nodes from the $d+1$th layer.

Sort them by their parent node's color. This groups child nodes constrained by the same color together.

Let the sorted nodes be $$$u_0, u_1, \dots, u_{m-1}$$$.

Let their parent node colors be $$$f_0, f_1, \dots, f_{m-1}$$$.

Define: $$$c_{u_i} = ((i + \Delta) \pmod k) + 1$$$.

Here we treat colors as a cycle $$$0 \dots k-1$$$ and attempt to assign the sorted nodes $$$m$$$ consecutive colors.

We need to find a $$$\Delta$$$ such that for all $$$i$$$, $$$(i + \Delta) \pmod k \neq f_i$$$.

That is, $$$\Delta \not\equiv (f_i - i) \pmod k$$$.

We compute all invalid $$$\Delta$$$ values (i.e., $$$(f_i - i) \pmod k$$$), yielding $$$m$$$ constraints in total.

Since there are $$$k$$$ possible values for $$$\Delta$$$ and typically $$$m \lt k$$$ or constraints overlap, by the Pigeonhole Principle, a valid $$$\Delta$$$ must exist under the lower bound definition of $$$k$$$.

In practice, because we've sorted by $$$f_i$$$, the constraints form a regular pattern—we only need $$$\Delta$$$ to avoid specific values.

We can enumerate $$$\Delta$$$ values from smallest to largest and find the first valid $$$\Delta$$$.

The complexity bottleneck lies in the sorting operation, which is $$$O(n \log n)$$$.

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> e[300005],v[300005],g[300005];
int n,d[300005],t[300005],id[300005],son[300005],snum[300005],fa[300005];
bool flag[300005];
void dfs(int pos,int fa)
{
	::fa[pos]=fa;
	d[pos]=d[fa]+1;
	t[d[pos]]++;
	g[d[pos]].push_back(pos);
	for(int x:e[pos])
	{
		if(x==fa)
			continue;
		snum[pos]++;
		dfs(x,pos);
	}
}
void test()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		e[i].clear(),g[i].clear(),v[i].clear(),d[i]=t[i]=id[i]=snum[i]=0;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	int mx=0,mt=0;
	for(int i=1;i<=n;i++)
		if(t[i]>=mx)
			mx=t[i],mt=i;
//	for(int i=1;i<=n;i++)
//		cerr<<i<<" "<<fa[i]<<" "<<d[i]<<"\n";
	int ans=mx;
	for(int i=1;i<=mx;i++)
		id[g[mt][i-1]]=i,v[i].push_back(g[mt][i-1]);
	for(int i=mt+1;i<=n;i++)
	{
		vector<int> vfa;
		for(int j:g[i-1])
		{
			son[j]=0;
			if(snum[j])
				flag[id[j]]=1;
		}
		int pos=1;
		for(int j:g[i])
		{
			if(!son[fa[j]])
				son[fa[j]]=j,vfa.push_back(fa[j]);
			else
			{
				while(flag[pos])
					pos++;
				assert(pos<=mx);
				id[j]=pos,v[pos].push_back(j),pos++;
			}
		}
		while(flag[pos])
			pos++;
		assert(pos<=mx);
		int lst=pos;
		for(int x:vfa)
		{
			id[son[x]]=lst;
			v[lst].push_back(son[x]);
			lst=id[x];
		}
		for(int j:g[i-1])
			flag[id[j]]=0;
	}
	for(int i=mt-1;i>=1;i--)
	{
		vector<int> vfa;
		for(int j:g[i])
			son[j]=0;
		for(int j:g[i+1])
		{
			flag[id[j]]=1;
			if(!son[fa[j]])
				son[fa[j]]=j,vfa.push_back(fa[j]);
		}
		assert(!vfa.empty());
		if(vfa.size()==1)
		{
			if(ans==t[i+1])
				ans++,id[vfa[0]]=ans,v[ans].push_back(vfa[0]);
			else
			{
				int pos=1;
				while(flag[pos])
					pos++;
				assert(pos<=ans);
				id[vfa[0]]=pos,v[pos].push_back(vfa[0]);
			}
		}
		else
		{
			for(int i=0;i<vfa.size();i++)
				id[vfa[i]]=id[son[vfa[(i+1)%vfa.size()]]],v[id[vfa[i]]].push_back(vfa[i]);
		}
		for(int j:g[i+1])
			flag[id[j]]=0;
		for(int x:vfa)
			flag[id[x]]=1;
		int pos=1;
		for(int x:g[i])
			if(!son[x])
			{
				while(flag[pos])
					pos++;
				assert(pos<=ans);
				id[x]=pos,v[pos].push_back(x);
				pos++;
			}
		for(int x:vfa)
			flag[id[x]]=0;
	}
	cout<<ans<<"\n";
	for(int i=1;i<=ans;i++)
	{
		cout<<v[i].size()<<" ";
		for(int x:v[i])
			cout<<x<<" ";
		cout<<"\n";
	}
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    	test();
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider the term $$$\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}$$$. What properties can you derive if $$$a_i \lt a_{i+1}$$$?

Recall that $$$\frac{1}{\operatorname{lcm}(a_i,a_{i+1})} = \frac{\gcd(a_i,a_{i+1})}{a_i a_{i+1}}$$$. Notice that when $$$a_i \lt a_{i+1}$$$, the inequality $$$\gcd(a_i,a_{i+1}) \le a_{i+1}-a_i$$$ always holds.

You might have bounded the sum of the first $$$n-1$$$ terms. Try comparing the term $$$\frac{a_n-a_1}{a_1 a_n}$$$ (from the telescoping sum) with the last term $$$\frac{a_1}{a_1 a_n}$$$.

If $$$y \gt x$$$ and $$$\gcd(x,y)=y-x$$$, what does this imply about the relationship between $$$x$$$ and $$$y$$$? How many such pairs $$$(x,y)$$$ exist for $$$1\le x \lt y \le m$$$?

Note that

The equality holds if and only if $$$\gcd(a_i,a_{i+1})=a_{i+1}-a_i$$$ for all $$$1\le i \lt n$$$, and $$$a_1=1$$$. Thus, the problem is transformed into counting the number of sequences that satisfy these conditions.

The condition $$$\gcd(x,y)=y-x$$$ implies that $$$y-x$$$ is a divisor of $$$x$$$. In other words, there exists a divisor $$$d$$$ of $$$x$$$ such that $$$y=x+d$$$. Therefore, the total number of such valid pairs $$$(x,y)$$$ is only $$$\mathcal O(m \ln m)$$$. Consequently, we can easily obtain the answer using dynamic programming with a time complexity of $$$O(nm\ln m)$$$.

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
using namespace std;
namespace FastIO
{
    const int BUF_SIZE=1<<20;
    char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    char* in_ptr=in_buf+BUF_SIZE;
    char* out_ptr=out_buf;
    char get_char()
    {
        if(in_ptr==in_buf+BUF_SIZE)
        {
            in_ptr=in_buf;
            fread(in_buf,1,BUF_SIZE,stdin);
        }
        return *in_ptr++;
    }
    void put_char(char c)
    {
        if(out_ptr==out_buf+BUF_SIZE)
        {
            fwrite(out_buf,1,BUF_SIZE,stdout);
            out_ptr=out_buf;
        }
        *out_ptr++=c;
    }
    struct Flusher
    {
        ~Flusher()
        {
            if(out_ptr!=out_buf)
            {
                fwrite(out_buf,1,out_ptr-out_buf,stdout);
            }
        }
    } flusher;
}
#define getchar FastIO::get_char
#define putchar FastIO::put_char
inline int read()
{
    int x=0;
    bool zf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            zf=0;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return zf?x:-x;
}
void print(cint x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }
    char buf[12];
    int len=0,y=x;
    if(y<0)
    {
        putchar('-');
        y=-y;
    }
    while(y)
    {
        buf[len++]=(y%10)+'0';
        y/=10;
    }
    while(len--)
    {
        putchar(buf[len]);
    }
}
inline void princh(cint x,const char ch)
{
    print(x);
    putchar(ch);
}
cint N=3000,M=3000;
cint mod=998244353;
int n,m;
int a[N+1];
int dp[N+1][M+1];
vector<int>d[M+1];
int ans;
void solve()
{
    n=read();
    m=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
    }
    if(a[1]>1)
    {
        princh(0,'\n');
        return;
    }
    dp[1][1]=1;
    for(int i=2;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            dp[i][j]=0;
            for(int x:d[j])
            {
                (dp[i][j]+=dp[i-1][j-x])>=mod?(dp[i][j]-=mod):0;
            }
        }
        if(a[i])
        {
            for(int j=1;j<=m;++j)if(j!=a[i])dp[i][j]=0;
        }
    }
    ans=0;
    for(int j=1;j<=m;++j)
    {
        (ans+=dp[n][j])>=mod?(ans-=mod):0;
    }
    princh(ans,'\n');
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    for(int i=1;i<=M;++i)
    {
        for(int j=i;j<=M;j+=i)
        {
            d[j].push_back(i);
        }
    }
    int T=read();
    while(T--)solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Calculating the sum of squares of counts is difficult.

Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings.

Try dynamic programming.

The DP transition is continuous over the DFS sequence.

Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings.

Let $$$f_{i,j}$$$ represent the number of ways to choose two strings located at nodes $$$i$$$ and $$$j$$$, respectively, within their subtrees. Clearly, $$$f_{i,j}$$$ has a non-zero value only if $$$c_i = c_j$$$, where $$$c$$$ denotes the string sequence.

Then, $$$f_{p,q}$$$ contributes to $$$f_{i,j}$$$ if and only if $$$p$$$ is in the subtree of $$$i$$$ and $$$q$$$ is in the subtree of $$$j$$$. By performing a depth-first search (DFS) on the tree and marking timestamps, the $$$(x, y)$$$ pairs of contributing $$$f_{p,q}$$$ must form a rectangle (as in a DFS sequence, each subtree is a range). Sorting by reverse DFS order and computing $$$2$$$ — dimensional suffix sums suffices.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e3 + 10;
const int mod = 998244353;

inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }
inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; }

int T, n, ans[MAXN], sum[MAXN][MAXN]; char s[MAXN];

vector<int> g[MAXN]; int in[MAXN], out[MAXN], rev[MAXN], id;

void init(int u, int f = 0) {
	in[u] = ++id, rev[id] = u;
	for (int v : g[u]) if (v != f) init(v, u);
	out[u] = id;
}

inline 
int query(int al, int ar, int bl, int br) {
	return sub(add(sum[al][bl], sum[ar + 1][br + 1]), add(sum[al][br + 1], sum[ar + 1][bl]));
}

int main() {
	for (scanf("%d", &T); T--; ) {
		scanf("%d%s", &n, s + 1), id = 0;
		for (int i = 1, u, v; i < n; i++) {
			scanf("%d%d", &u, &v);
			g[u].emplace_back(v), g[v].emplace_back(u);
		}
		init(1);
		for (int i = n; i; i--) {
			for (int j = n; j; j--) {
				if (s[rev[i]] == s[rev[j]]) {
					sum[i][j] = add(query(in[rev[i]] + 1, out[rev[i]], in[rev[j]] + 1, out[rev[j]]), 1);
				}
				cadd(sum[i][j], sub(add(sum[i + 1][j], sum[i][j + 1]), sum[i + 1][j + 1]));
			}
		}
		for (int i = 1; i <= n; i++) {
			printf("%d ", query(in[i], out[i], in[i], out[i]));
		}
		puts("");
		for (int i = 1; i <= n; i++) g[i].clear();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) sum[i][j] = 0;
		}
	}
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider under what circumstances you need to return $$$-1$$$.

Consider what information you can get by querying the string L.

The case analysis process for this problem is not complicated.

Consider querying three fixed strings to determine all snakes' speeds.

Consider querying the three strings: L, LR, and R.

It can be observed that the sizes of the sets returned from querying L and LR are the same. The specific proof states that after querying LR, the positions of the surviving snakes are exactly their initial positions. Since the relative order of the snakes remains unchanged, performing operation R after operation L will definitely not cause any two snakes to collide. Therefore, the sizes of the returned sets are the same.

By establishing a one-to-one correspondence with the initial coordinates, we can easily deduce the speeds of all snakes that survive after performing operation L.

At this point, we only lack the speeds of the snakes that died after performing operation L. A simple case analysis reveals the following scenarios (the first number on the right represents the speed of the snake that died after operation L, and _ indicates that there is no snake at that initial position):

• 01.
• 02.
• 0_2.
• 12.

We can directly solve the problem by classifying these cases, but the implementation might be somewhat cumbersome. Therefore, let's consider a more concise approach to the case analysis.

First, try to determine some snakes with speed $$$2$$$. For the position and speed of such a snake, the following cases allow direct determination:

• The previous snake is at a distance of $$$1$$$ and has been determined to have speed $$$1$$$.
• The previous snake is at a distance of $$$1$$$ and has not been determined. Let's explain why this snake's speed is certain in this case:
• If the previous snake's speed is $$$0$$$, it will definitely not be killed in a collision, so this case is impossible.
• If the previous snake's speed is at least $$$1$$$, then this snake must have a speed of at least $$$2$$$ to catch up and collide with the previous snake. Therefore, this snake's speed is at least $$$2$$$.
• The previous snake is at a distance of $$$2$$$ and has been determined to have speed $$$0$$$.

The case analysis above naturally eliminates the 0_2 and 12 scenarios.

Now, only the 01 and 02 cases remain. It can be observed that only the patterns 010 and 020 are indistinguishable. Therefore, we can initially ignore this situation: first find one valid solution, and then check if this solution contains such an indistinguishable pattern.

Otherwise, since the snake immediately after this one must have a speed of at least $$$1$$$ (under the condition of a unique solution), the position this snake would reach if it moved ignoring obstacles is exactly the position of the first snake whose position is $$$\ge$$$ this snake's position after performing the R query. If this snake does not come into contact with any other snake while moving right, its position can also be directly determined. Therefore, we can directly deduce the speeds of all snakes using this method.

Time complexity: $$$O(\sum n)$$$ or $$$O(\sum n \log n)$$$.

/*
OI 2025 RP++!!!

author: wmrqwq[alsu]

time: 2025/7/12

contest:

Tips:

RE, MLE?
greedy, dp?
natural time?
map, umap?
giveup rating, get score.
brute force, right solution?
%mod? std/run/maker/checker?
add bruteforce?
clear?
double, long double?
O(n)? O(n^2)!
make data!

last but not least.

bruteforce -> SegTree?
Think more.
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define cll const ll
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
#define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))
#define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))
#define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)
#define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)
#define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))
#define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// #define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))
#define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)
#define x first
#define y second
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
#define bug1 cout<<"bug1,AWaDa?\n";
#define bug2 cout<<"bug2,AWaDa!\n";
#define bug3 cout<<"bug3,AKTang?\n";
#define bug4 cout<<"bug4,AKTang!\n";
#define IM (ll)1e9
#define LM (ll)1e18
#define MIM (ll)-1e9
#define MLM (ll)-1e18
#define sort stable_sort
ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}
ll pw(ll x,ll y,ll mod){if(mod==1)return 0;if(y==0)return 1;if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
ll pw(ll x){return 1ll<<x;}
template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}ll Ss=chrono::steady_clock::now().time_since_epoch().count();mt19937_64 Apple(Ss);ll rand_lr(ll l,ll r){return Apple()%(r-l+1)+l;}
// cll mod=1e9+7,N=300010;ll fac[N],inv[N];void init(){fac[0]=1;forl(i,1,N-5)fac[i]=i*fac[i-1],fac[i]%=mod;inv[N-5]=pw(fac[N-5],mod-2,mod);forr(i,N-5,1)inv[i-1]=inv[i]*i%mod;}ll C(ll n,ll m){if(n<m || m<0)return 0;return (fac[n]%mod)*(inv[n-m]*inv[m]%mod)%mod;}
// void add(ll&x,ll y){x=((x+y)%mod+mod)%mod;}void del(ll&x,ll y){x=(x%mod-y%mod+mod)%mod;}
ll _t_;
struct BIT{
    ll maxn;
    ll tree[1000010];
    void clear(ll l){
        forl(i,0,l)
            tree[i]=0;
    }
    void add(ll x,ll y){
        for(;x<=maxn;x+=lowbit(x))
            tree[x]+=y;
    }
    ll query(ll x){
        ll S=0;
        for(;x;x-=lowbit(x))
            S+=tree[x];
        return S;
    }
    ll query(ll l,ll r){
        return query(r)-query(l-1);
    }
};
// ll lg[1000010];
void Init(){
    // forl(i,2,1e6+5)
    //     lg[i]=lg[i>>1]+1;
}
//sunny
ll n;
ll a[100010];
ll ans[100010];
vector<ll>vl,vr,vlr;
//tulpa
void ask(string s,vector<ll>&v)
{
    cout<<"? "<<s<<endl;
    v.pb(rd());
    forl(i,1,v[0])
        v.pb(rd());
}
/*
012

01
02

120
*/
void _clear(){}
void solve()
{
    _clear();
    vl.clear(),vr.clear(),vlr.clear();
    cin>>n;
    forl(i,1,n)
        cin>>a[i],
        ans[i]=-1;
    ask("L",vl),ask("R",vr),ask("LR",vlr);
    ll sz=vlr[0],L=1;
    forl(i,1,n)
    {
        while(L<=sz && vlr[L]<a[i])
            L++;
        if(L<=sz && vlr[L]==a[i])
            ans[i]=vlr[L]-vl[L];
    }
    forl(i,2,n)
        if(ans[i]==-1 && ((a[i]-a[i-1]==1 && abs(ans[i-1])==1) || (a[i]-a[i-1]==2 && ans[i-1]==0)))
        {
            // if(ans[i-1]==-1)
            //     ans[i-1]=1;
            ans[i]=2;
        }
    forl(i,1,n)
        if(ans[i]==-1)
            ans[i]=*lower_bound(vr.begin()+2,vr.end(),a[i])-a[i];
    forl(i,1,n-2)
        if(a[i]+1==a[i+1] && a[i+1]+1==a[i+2] && ans[i]+ans[i+2]==0 && ans[i+1])
        {
            cout<<"! "<<-1<<endl;
            return ;
        }
    cout<<"! ";
    forl(i,1,n)
        cout<<ans[i]<<' ';
    cout<<endl;
}
int main()
{
    Init();
//    freopen("tst.txt","r",stdin);
//    freopen("sans.txt","w",stdout);
    IOS;
    _t_=1;
    cin>>_t_;
    while(_t_--)
        solve();
    QwQ;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Subsequences are too hard; can we find some properties? How should we approach the case where $$$k\le n\le500$$$?

The approach for $$$k\le n\le500$$$ is too naive; how can we optimize it? What if $$$k\le n\le5000$$$?

What if we are guaranteed that the count of positive numbers $$$m \le 5000$$$?

The requirement of exactly $$$k$$$ segments, combined with the previous optimizations, suggests what technique? Consider the data constraints.

Sort $$$a$$$ in non-decreasing order. The cost of a group depends only on the multiset of its values, so the original positions are irrelevant.

Lemma 1 (canonical form). There exists an optimal partition whose groups are contiguous blocks in the sorted array. If their lengths are $$$l_1,l_2,\dots,l_k$$$ in order of increasing values, then $$$l_1\ge l_2\ge\cdots\ge l_k$$$.

Henceforth, partitions are partitions of the sorted array into contiguous blocks. Let $$$S_0=0$$$, $$$S_i=a_1+\cdots+a_i$$$, and

be the cost of the block $$$a_{j+1}\dots a_i$$$. If $$$f_{t,i}$$$ is the minimum cost of partitioning the first $$$i$$$ elements into exactly $$$t$$$ blocks, then

which gives an $$$O(n^2k)$$$ algorithm if evaluated directly.

For $$$0\le a\le b\le c\le d\le n$$$, expansion gives

If all elements are non-negative, the right-hand side is non-negative, so

This quadrangle inequality (QI) implies decision monotonicity in each DP layer, and therefore an $$$O(nk)$$$ algorithm for non-negative arrays. For arbitrary signs, (2) may fail.

Let

Thus $$$0$$$ is grouped with the non-positive elements. Let $$$\mathcal P_0$$$ be the partition whose first block contains the smallest $$$n-k+1$$$ elements and whose other blocks are singletons; its cost is

Lemma 2 (boundary shift). In a canonical partition with at least two blocks, let the first two block lengths be $$$p\ge q$$$. If $$$q\ge2$$$ and the first element $$$x$$$ of the second block satisfies $$$x\le0$$$, moving $$$x$$$ into the first block does not increase the cost.

After a shift, reapply Lemma 1 to the later blocks. The first block has grown and remains a longest block, so its set of elements is unchanged by this reordering. If $$$k=1$$$, then $$$\mathcal P_0$$$ is the unique partition; below let $$$k\ge2$$$.

Case 1: $$$k \gt m$$$. Then $$$\mathcal P_0$$$ is optimal. Indeed, in a canonical partition, if the second block is a singleton then all later blocks are singletons. Otherwise its first element must be non-positive: if it were positive, all remaining elements would be positive, at most $$$m$$$ elements in $$$k-1\ge m$$$ blocks, forcing all those blocks to be singletons. Lemma 2 therefore moves the first cut one step right without increasing the cost. Repeating ends at $$$\mathcal P_0$$$. In particular, all positive elements are singletons.

Case 2: $$$k\le m$$$. There is an optimal partition whose first block contains all non-positive elements. To see this, let the first cut be $$$b \lt z$$$ in a canonical optimal partition. The second block starts with a non-positive element. It cannot be a singleton: otherwise all later blocks would be singletons and $$$b=n-k+1\ge n-m+1=z+1$$$, a contradiction. Lemma 2 hence increases $$$b$$$ by one without increasing the cost. Repeating gives $$$b\ge z$$$. Later blocks are then positive, although the first block may also contain positive elements.

This structural form with monotone DP on the positive suffix gives $$$O(nk)$$$. For the full constraints, use Aliens' trick. Its inner DP requires QI also for transitions from cut $$$0$$$, and deleting cuts inside the non-positive prefix is not enough: for $$$a=(-100,1,1,1)$$$ and $$$(a,b,c,d)=(0,2,3,4)$$$, the right-hand side of (1) is negative. We extend the forced prefix further.

Start with $$$T=z$$$. While $$$t=T+1\le n$$$ satisfies

increase $$$T$$$ to $$$t$$$. The left side is the marginal cost of appending $$$a_t$$$ to the first $$$t-1$$$ elements as one block.

Claim. For $$$k\le m$$$, there is an optimal partition whose first cut is at least $$$T$$$, unless it is $$$\mathcal P_0$$$.

Thus, apart from $$$\mathcal P_0$$$, only cuts in

are needed. If $$$T \gt n-k+1$$$, no partition with first cut in $$$\mathcal J$$$ has $$$k$$$ blocks, so the answer is $$$\operatorname{base}$$$. If $$$T\le n-k+1$$$, then $$$\mathcal P_0$$$ itself uses only cuts from $$$\mathcal J$$$.

Lemma 3. Inequality (2) holds for all $$$a,b\in\mathcal J$$$ with $$$a\le b\le c\le d$$$.

Let $$$G(t)$$$ be the minimum cost of a partition into exactly $$$t$$$ blocks using cuts from $$$\mathcal J$$$, where $$$1\le t\le n-T+1$$$.

Lemma 4. $$$G$$$ is convex: $$$G(t-1)+G(t+1)\ge2G(t)$$$ for $$$2\le t\le n-T$$$.

Now apply Aliens' trick. For an integer reward $$$\mu$$$ per block, let $$$\operatorname{check}(\mu)$$$ be the minimum of $$$\text{cost}-\mu\cdot(\text{number of blocks})$$$ over partitions with cuts in $$$\mathcal J$$$, and let $$$\operatorname{cnt}(\mu)$$$ be the corresponding number of blocks, with ties broken toward fewer blocks. Adding the same constant $$$-\mu$$$ to every block preserves (2). By Lemma 4, $$$\operatorname{cnt}(\mu)$$$ is non-decreasing in $$$\mu$$$. For the largest $$$\mu$$$ with $$$\operatorname{cnt}(\mu)\le k$$$, the standard recovery gives $$$G(k)=\operatorname{check}(\mu)+\mu k$$$. The answer is $$$\min(\operatorname{base},G(k))$$$.

To compute $$$\operatorname{check}(\mu)$$$, let $$$dp[i]$$$ be the optimal pair (penalised value, block count) for the first $$$i$$$ elements; in the implementation, ck(mu) evaluates this DP and returns whether the resulting block count is at most $$$k$$$. Then $$$dp[0]=(0,0)$$$ and, for $$$i\ge\max(T,1)$$$,

with the block count increased by $$$1$$$ in each transition. In the code, a is overwritten by the prefix sums $$$S$$$, p is $$$\max(T,1)$$$, the precomputed ans is $$$\operatorname{base}$$$, and calc(i,j,mu) evaluates the transition above.

By Lemma 3, the optimal $$$j$$$ is monotone in $$$i$$$. The queue q stores candidate cuts in increasing order, and lim[idx] is the first right endpoint at which q[idx + 1] is at least as good as q[idx]. Removing front candidates with lim[l] <= i therefore leaves an optimal cut for $$$dp[i]$$$. To insert $$$i$$$, find(i,q[r],mu) binary-searches the first endpoint where $$$i$$$ beats the tail candidate q[r]; if this point is at most lim[r - 1], then q[r] never becomes optimal and is discarded. Each cut enters and leaves the queue once, so one check takes $$$O(n\log n)$$$ time.

The binary search over $$$\mu$$$ needs $$$O(\log V)$$$ checks, where $$$V=O(n^2\max_i|a_i|)$$$. The total complexity is $$$O(n\log n\log V)$$$ time and $$$O(n)$$$ memory per test case after sorting. All costs are stored in __int128.

#include <bits/stdc++.h>
using namespace std;
 
#define S cerr << "SYT AK IOI" << endl;
#define M cerr << "MKF AK IOI" << endl;
 
using ll = long long;
using pii = pair<int, int>;
using uint = unsigned int;
using ull = unsigned long long;
mt19937 rnd(0 ^ (*new int));
// #define int long long                                             //use it if possible
#define pb(x) push_back(x)
#define F(i, a, b) for (int i = (a), i##end = (b); i <= (i##end); ++i)
#define UF(i, a, b) for (int i = (a), i##end = (b); i >= (i##end); --i)
#define gc() getchar()
#define pc putchar
#define popcount(x) __builtin_popcount(x)
 
inline void init();
inline void IO();
__int128 n,k,p;
__int128 a[1000100],lim[1000100],q[1000100];
array<__int128,2>dp[1000100];
ll rd()
{
	ll x;
	cin>>x;
	return x;
}
inline array<__int128,2> calc(__int128 i,__int128 j,__int128 x){
    return (array<__int128,2>){dp[j][0]+(i-j)*(a[i]-a[j])-x,dp[j][1]+1};
}
inline bool c2(__int128 x,__int128 i,__int128 j,__int128 m){
    return calc(x,j,m)>=calc(x,i,m);
}
inline __int128 find(__int128 i,__int128 j,__int128 m){
    int l=i,r=n,mid,res=n+1;
    while(l<=r) c2(mid=l+r>>1,i,j,m)?res=mid,r=mid-1:l=mid+1;
    return res;
}
inline __int128 ck(__int128 mid){
    for(__int128 i=p,l=1,r=1;i<=n;i++){
        for(;l<r&&lim[l]<=i;l++);dp[i]=calc(i,q[l],mid);
        for(;l<r&&lim[r-1]>=find(i,q[r],mid);r--);
        lim[r]=find(i,q[r],mid);q[++r]=i;
    }
    return dp[n][1]<=k;
}
void print(__int128 x){if(x<0) putchar('-'),x=-x;if(x>9) print(x/10);putchar(x%10+'0');}
inline void mian()
{
//    cin>>n>>k;
	n=rd(),k=rd();
    F(i,1,n)a[i]=rd();
    sort(a+1,a+1+n);
    F(i,2,n)a[i]+=a[i-1];
    if(k==1){print(n*a[n]);putchar('\n');return;}
    __int128 ans=(n-k+1)*a[n-k+1]+a[n]-a[n-k+1];p=1;
    while(p<=n and a[p]-a[p-1]<=0)p++;
    while(p<=n and p*a[p]-a[p]+a[p-1]<(p-1)*a[p-1])p++;
    --p,p=max(p,(__int128)1);
    if(n-p<k-1){print(ans);putchar('\n');return;}
    __int128 l=-n*n*(__int128)(1e9),r=-l,mid,res=l;
    while(l<=r) ck(mid=l+r>>1)?res=mid,l=mid+1:r=mid-1;
    ck(res);
    ans=min(ans,(__int128)k*res+dp[n][0]);
    print(ans);putchar('\n');
}
signed main()
{
    IO();
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    #define multitest 1
#ifdef multitest
    T=rd();
#endif
    init();
 
    while (T--)
        mian();
    return 0;
}
 
inline void init()
{
}
 
#define NAME(x) #x
#define INNAME(x) NAME(x)
// #define FILEIO sub3_15
inline void IO()
{
#ifdef FILEIO
    freopen(INNAME(FILEIO) ".in", "r", stdin), freopen(INNAME(FILEIO) ".out", "w", stdout);
#endif
}