It is always possible to rearrange the candies, unless candies of one specific color appears too often.

Let $$$x$$$ be the color with the highest number of candies. In case of ties, $$$x$$$ could be any of the candidates. Denote the number of candies with color $$$x$$$ as $$$a$$$.

Conclusion: The answer to the problem is YES if and only if there are no more than $$$n^2 - n$$$ candies of color $$$x$$$; — in other words, $$$a\le n^2 - n$$$ holds.

Proof of necessity: If there are more than $$$n^2 - n$$$ candies of color $$$x$$$, then there are less than $$$n$$$ candies not of color $$$x$$$. Since there are $$$n$$$ rows, at least one row will have no candies not of color $$$x$$$; therefore, such a row will be filled with candies of color $$$x$$$, violating the restrictions.

Proof of sufficiency: If there are no more than $$$n^2 - n$$$ candies of color $$$x$$$, we can always construct a solution with the method below.

First, if $$$a \lt n$$$ holds, then we can arrange the candies arbitrarily because no color has enough candies to fill a row or a column.

Otherwise, $$$n\le a\le n^2 - n$$$ holds.

We can put candies of color $$$x$$$ in $$$a_{1,1},a_{2,2},\ldots,a_{n,n}$$$. This will take $$$n$$$ candies of color $$$x$$$. Next, we choose $$$n$$$ candies not of color $$$x$$$ arbitrarily. We will put them at $$$a_{1,2},a_{2,3},\ldots,a_{n-1,n},a_{n,1}$$$. Lastly, we arrange other candies that have not yet been arranged arbitrarily. Since in the first step we put a candy of color $$$x$$$ in each row and column, and in the second step we put a candy not of color $$$x$$$ in each row and column, each row and column contains at least candies of two colors, satisfying the constraints.

#include<bits/stdc++.h>
#define F(i,x,y) for (int i=(x);i<=(y);i++)
#define R(i,x,y) for (int i=(x);i>=(y);i--)
#define p2i pair<int,int>
#define ll long long
#define fi first
#define se second
#define nb(x) (1<<((x)-1))
#define x1 __melody1
#define x2 __melody2
#define y1 __melody3
#define y2 __melody4
#define iosoptim ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
 
const bool MT = 1;
int n,cnt[10005];
void ygg(){
    cin>>n;
    int tmp;
    bool flag=1;
    F(i,1,n*n) {
        cin>>tmp;
        ++cnt[tmp];
        if (cnt[tmp]>n*(n-1)) flag=0;
    }
    if (flag) cout<<"YES\n";
    else cout<<"NO\n";
}
void mark() {
    F(i,1,n*n) cnt[i]=0;
}
int main (){
#ifdef ONLINE_JUDGE
    iosoptim
#endif
    int testcases=1;
    if(MT) cin>>testcases;
    while(testcases--){
        ygg();
        mark();
    }
    return 0;
}

good mid bad didn't solve

For the sake of simplicity, let's assume all cards have different costs. If multiple cards have the same cost, we break ties by their initial position in the deck (the earlier card is considered to have a lower cost for the purpose of the strategy).

The optimal strategy: If the win-condition is among the first $$$k$$$ cards, then we play it. Otherwise, we play the card in the first $$$k$$$ places with the lowest cost. Proof of optimality is shown below.

Lemma: If at any time, the win-condition is placed at position $$$x \gt k$$$, the cost used before the win-condition is played again is at least the sum of the costs of $$$x-k$$$ cards with the lowest costs out of all the $$$x-1$$$ cards placed before the win-condition. Our strategy reaches this minimum value.

Proof:

Since playing any card in front of the win-condition moves the win-condition 1 place toward the front, we need to play $$$x-k$$$ normal cards before the win-condition is playable.

Before the win-condition moves to position $$$k$$$ and becomes playable, every card placed before the win-condition can be played at most once, and every card placed at the back of the win-condition cannot be played. Therefore, the cost used is at least the sum of the first $$$x-k$$$ lowest costs of the cards initially placed before the win-condition. We mark the $$$x-k$$$ cards placed before the win-condition with the lowest costs.

Among all the $$$x-1$$$ cards placed before the win-condition, exactly $$$k-1$$$ cards are not marked, so whenever before the win-condition is played the first time, at least one marked card will be in the first $$$k$$$ places. Therefore, our strategy will always play a marked card in the first $$$x-k$$$ plays since their costs are always lower than not marked ones. Since each marked card can be only played for at most once, after $$$x-k$$$ plays we will play each marked card once, which achieves the lower bound described above.

Therefore, the lemma is proven.

Now, let $$$A$$$ be the sum of the costs of $$$p-k$$$ cards with the lowest costs placed before the win-condition. Let $$$B$$$ be the sum of the costs of $$$n-k$$$ cards with the lowest costs, without considering the win-condition.

By the above lemma, the cost spent before playing the win-condition the first time is at least $$$A$$$. After it is played each time, it always gets placed at position $$$n$$$, so the cost spent before playing the win-condition another time is at least $$$B$$$. Our strategy achieves the minimum.

Therefore, the cost used to play the win-condition any non-negative number of times is minimized, which proves the optimality of the strategy.

The answer is $$$\lfloor \dfrac{m-A-a_p}{B+a_p}\rfloor + 1$$$ if $$$m-A-a_p\ge 0$$$. Otherwise, the answer is $$$0$$$.

The value of $$$A$$$ and $$$B$$$ can be calculated with a priority queue in $$$O(n\log n)$$$. Therefore, the overall time complexity is $$$O(n\log n)$$$.

Alternatively, you may simulate the strategy above directly; the time complexity will be $$$O(nm)$$$, which is also sufficient to pass.

#include<bits/stdc++.h>
#define F(i,x,y) for (int i=(x);i<=(y);i++)
#define R(i,x,y) for (int i=(x);i>=(y);i--)
#define p2i pair<int,int>
#define ll long long
#define fi first
#define se second
#define nb(x) (1<<((x)-1))
#define x1 __melody1
#define x2 __melody2
#define y1 __melody3
#define y2 __melody4
#define iosoptim ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

const bool MT = 1;
int n,k,p,a[100005];
ll m;
void ygg(){
	cin>>n>>k>>p>>m;
	F(i,1,n) cin>>a[i];
	multiset<int> opt;
	F(i,1,k-1) opt.insert (a[i]);
	F(i,k,p-1) {
		opt.insert (a[i]);
		m-=*opt.begin ();
		opt.erase (opt.begin ());
	}
	m-=a[p];
	if (m<0) {
	    cout<<0<<"\n";
	    return;
	}
	ll sum=a[p];
	opt.clear ();
	F(i,1,n) {
		if (i!=p) opt.insert (a[i]);
	}
	F(i,1,n-k) {
		sum+=*opt.begin ();
		opt.erase (opt.begin ());
	}
	cout<<1+m/sum<<"\n";
}
void mark() {

}
int main (){
#ifdef ONLINE_JUDGE
	iosoptim
#endif
	int testcases=1;
	if(MT) cin>>testcases;
	while(testcases--){
		ygg();
		mark();
	}
	return 0;
}

good mid bad didn't solve

Notice that the value of $$$S$$$ does not affect your decision. This meant for integer $$$i\in[1,n-1]$$$ the decision of tasks $$$[1,i]$$$ does not affect the decision of tasks $$$[i+1,n]$$$.

Let $$$f_i$$$ be the answer for considering tasks $$$[i,n]$$$ only and assuming that $$$S=1$$$. It holds that $$$f_i=\max(f_{i+1},f_{i+1}\cdot(1-\frac{p_i}{100})+c_i)$$$, and $$$f_1$$$ is the answer needed.

#include<bits/stdc++.h>
#define ld long double
using namespace std;
const int N=1e5+5;
ld c[N],p[N];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int cv,pv;
		cin>>cv>>pv;
		c[i]=cv,p[i]=pv/100.0;
	}
	ld ans=0;
	for(int i=n;i>=1;i--){
		ans=max(ans,ans*(1-p[i])+c[i]);
	}
	cout<<fixed<<setprecision(10)<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin>>T;
	for(int i=1;i<=T;i++) solve();
}

good mid bad didn't solve

If a solution exists, it must be unique.

Assume a solution exists, construct the graph accordingly, and verify afterward that it satisfies all given conditions.

Consider the necessary and sufficient condition for the existence of a directed edge $$$ u \to v $$$.

Two conditions must hold:
1. Node $$$ v $$$ must be reachable from $$$ u $$$.
2. There must be no intermediate node $$$ w $$$ such that $$$ u $$$ can reach $$$ w $$$ and $$$ w $$$ can reach $$$ v $$$.

Implementing this directly yields an $$$ O(n^3) $$$ solution, which is sufficient for D1. One can further optimize it to $$$ O\left(\frac{n^3}{\omega}\right) $$$ using bitsets, though this is not required for this subtask.

Let $$$ R_u $$$ denote the set of nodes reachable from $$$ u $$$, excluding $$$ u $$$ itself.

Let $$$ s_u $$$ denote the number of nodes reachable from $$$ u $$$. Among all nodes in $$$ R_u $$$, let $$$ v $$$ be the one with the largest $$$ s_v $$$. What can we infer?

It can be proven that the edge $$$ u \to v $$$ must exist in the solution.

We iteratively apply the idea from Hint 4:

• Find the node $$$ v \in R_u $$$ with the largest $$$ s_v $$$, and add the edge $$$ u \to v $$$.
• Then remove all nodes in $$$ R_v $$$ from $$$ R_u $$$, since they are already reachable from $$$ u $$$ indirectly via $$$ v $$$, and therefore cannot have a direct edge from $$$ u $$$.
• Repeat this process until $$$ R_u $$$ becomes empty. At that point, all outgoing edges from $$$ u $$$ have been determined.

Since the final graph is a tree with exactly $$$ n - 1 $$$ edges, the total number of such removal operations across all nodes is $$$ O(n) $$$. Each operation involves scanning or updating a set of size at most $$$ n $$$, leading to an overall time complexity of $$$ O(n^2) $$$.

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e4+5;
int n, id[N], cnt[N];
bool vs[N], e[N][N];
struct Dsu {
	int fa[N];
	void init(int n) {
		for (int i = 1; i <= n; i++) fa[i] = i;
	}
	int find(int x) {
		if (x == fa[x]) return x;
		return fa[x] = find(fa[x]);
	}
	void merge(int x, int y) {
		fa[find(x)] = find(y);
	}
} dsu;
bool reach[N];
vector<int> tree[N];
void search(int u) {
	reach[u] = 1;
	for (int v : tree[u]) {
		search(v);
	}
}
void solve(int tid) {
	cin >> n;
	for (int i = 1; i <= n; i++) cnt[i] = 0, tree[i].clear();
	for (int u = 1; u <= n; u++) {
		id[u] = u;
		string s;
		cin >> s;
		for (int v = 1; v <= n; v++) {
			e[u][v] = s[v-1]-'0';
			cnt[u] += e[u][v];
		}
	}
	sort(id + 1, id + n + 1, [&](int u, int v) {
		return cnt[u] > cnt[v];
	});
	vector<pair<int, int >> edges;
	for (int u = 1; u <= n; u++) {
		for(int i = 1; i <= n; i++) {
			vs[i] = false;
		}
		vs[u] = true;
		for (int i = 1; i <= n; i++) {
			int v = id[i];
			if (!vs[v] && e[u][v]) {
				edges.push_back({u, v});
				if(edges.size() >= n) {
					cout << "No" << "\n";
					return ;
				}
				for (int w = 1; w <= n; w++) {
					if (e[v][w]) {
						vs[w] = true;
					}
				}
			}
		}
	}
	if (edges.size() != n - 1) {
		cout << "No" << "\n";
		return ;
	}
	sort(edges.begin(), edges.end());
	dsu.init(n);
	for (auto [u, v] : edges) {
		dsu.merge(u, v);
		tree[u].push_back(v);
	}
	int flag = 1;
	for (int i = 1; i <= n; i++) flag &= (dsu.find(i) == dsu.find(1));
	if (!flag) {
		cout << "No" << "\n";
		return ;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) reach[j] = 0;
		search(i);
		for (int j = 1; j <= n; j++) {
			if (reach[j] != e[i][j]) {
				cout <<  "No" << "\n";
				return ;
			}
		}
	}
	cout<< "Yes\n";
	for (auto [u, v] : edges) {
		cout << u << ' ' << v << '\n';
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	for (int i = 1; i <= T; i++) solve(i);
	return 0;
}

good mid bad didn't solve

Find a straightforward criterion to determine whether an array is "cute".

First, consider a necessary condition: If $$$X_i \ge i$$$ for any $$$i$$$, the array $$$X$$$ cannot be cute.

It is well-known that the structure of $$$X$$$ relates to a monotonic stack. We can verify whether an array $$$X$$$ of length $$$n$$$ is cute using the following simulation procedure:

1. Maintain a stack $$$S$$$, initialized with a single sentinel element $$$0$$$.
2. Iterate $$$i$$$ from $$$1$$$ to $$$n$$$:
   • Check if the value $$$X_i$$$ exists in $$$S$$$.
   • If $$$X_i$$$ is not in $$$S$$$, then $$$X$$$ is not a cute array.
   • If $$$X_i$$$ is in $$$S$$$, pop elements from $$$S$$$ until $$$X_i$$$ becomes the top element. Then, push $$$i$$$ onto the stack.
3. If the loop completes without violating the conditions above, $$$X$$$ is a cute array.

Solve the problem for the following special case: For all $$$i$$$, $$$X_i$$$ is either $$$-1$$$ or $$$i-1$$$.

We can use dynamic programming to solve this special case. Let $$$f_{i,k}$$$ denote the number of ways to fill the $$$-1$$$s in the prefix $$$X_1 \dots X_i$$$ such that the array remains potentially cute and the current stack size is $$$k$$$.

The transition is straightforward: * If $$$X_i = -1$$$, we can pop an arbitrary number of elements. Thus, $$$f_{i,k} = \sum_{j=k-1}^{i} f_{i-1,j}$$$. * If $$$X_i = i-1$$$, we cannot pop any elements (the previous index must be the nearest greater element). Thus, $$$f_{i,k} = f_{i-1,k-1}$$$.

Analyze the failure condition of the stack procedure further.

If $$$X_i$$$ is not found in $$$S$$$ during the simulation, it implies that $$$X_i$$$ was previously popped from the stack while processing some earlier index $$$j$$$. This indicates the existence of a pair $$$(j, i)$$$ such that $$$X_j \lt X_i \lt j \lt i$$$.

Consequently, an array $$$X$$$ is cute if and only if no such pair $$$(j, i)$$$ exists that satisfies this condition.

First, check if all fixed values (where $$$X_i, X_j \neq -1$$$) satisfy the condition that no pair $$$(j, i)$$$ with $$$j \lt i$$$ exists such that $$$X_j \lt X_i \lt j \lt i$$$. Additionally, ensure $$$X_i \lt i$$$ for all $$$i$$$. If these conditions are not met, the answer is $$$0$$$.

Consider each fixed $$$X_i \neq -1$$$ as defining an interval $$$[X_i, i]$$$. By sorting these intervals by length from smallest to largest, we can process them hierarchically. Once all $$$X_k$$$ within a specific interval are determined, the interval effectively behaves like the base case $$$[i-1, i]$$$ mentioned in Hint 2.

This reduction transforms the general problem into the special case solved in Hint 2. We can compute the final answer using the DP approach with prefix sum optimization, resulting in an overall time complexity of $$$O(n^2)$$$.

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,mod=998244353;
inline void add(int &x,int v){ x=(x+v)%mod; }
int T,n,ans,a[N],id[N],mx[N],f[N],sf[N];
void calc(int l,int r){
	int tp=0,cnt=0;
	f[0]=1,sf[0]=1;
	while(1){
		if(mx[l]==0) l++,tp=0;
		else l=mx[l],tp=1;
		if(l>r) break;
		cnt++;
		if(tp==0){
			for(int i=1;i<=cnt;i++) f[i]=sf[i-1];
			f[0]=0;
		}
		else{
			for(int i=cnt;i>=1;i--) f[i]=f[i-1];
			f[0]=0;
		}
		sf[cnt+1]=0;
		for(int i=cnt;i>=0;i--) sf[i]=(sf[i+1]+f[i])%mod;
	}
	ans=1ll*ans*sf[0]%mod;
}
void solve(){
	cin>>n;
	for(int i=0;i<=n;i++) mx[i]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		if(a[i]>=i) return void(cout<<0<<"\n");
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i]!=-1 && a[j]!=-1){
				if(a[i]<a[j] && a[j]<i) return void(cout<<0<<"\n");
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]!=-1) id[++cnt]=i;
	}
	sort(id+1,id+cnt+1,[](int x,int y){ return x-a[x]<y-a[y]; });
	ans=1;
	for(int i=1;i<=cnt;i++){
		calc(a[id[i]],id[i]-1);
		mx[a[id[i]]]=id[i];
	}
	calc(0,n);
	cout<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	for(int i=1;i<=T;i++) solve();
}

good mid bad didn't solve