What happens when there are two equal elements?

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (auto &x : a)
		cin >> x;
		
	sort(a.rbegin(), a.rend());
	
	for (int i = 0; i < n-1; i++)
		if (a[i] == a[i+1]) {
			cout << "-1\n";
			return;
		}
	
	for (auto x : a)
		cout << x << " ";
	cout << "\n";
}
 
int main() {
	int T;
	cin >> T;
	while (T--)
		solve();
}

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
 
int t, n, m;
 
int main() {
    
    int t; cin >> t;
    while(t--) {
        int n, m; cin >> n >> m;
        
        int c, cnt, mx = 1;
        
        for(int i = 0; i < n; i++) {
            int a; cin >> a;
            
            if (!i) {
                c = a;
                cnt = 1;
            }
            else if (a != c) {
                c = a;
                mx = max(mx, cnt);
                cnt = 1;
            }
            else {
                cnt++;
            }
        }
        
        mx = max(mx, cnt);
        
        if(mx < m) cout << "YES" << "\n";
        else cout << "NO" << "\n";
    }
    
    return 0;
}

We want an easy to check condition on $$$m$$$, $$$n$$$, $$$p$$$, $$$q$$$ that is equivalent to being able to fill the grid.

You can fill the $$$m\times n$$$ grid if an oly if $$$p+2q = m(n+1)+n(m+1)$$$ and $$$p\ge \vert m-n\vert$$$. (See tutorial for proof)

$$$p+2q = m(n+1) + n(m+1)$$$ is quadratic on $$$m$$$ and $$$n$$$. If you assume $$$m\ge n$$$, can you say anything on the size of $$$n$$$?

370969986

371019251

370975568

Think of some kind of subtree DP.

370987541

Having a good visual image of the problem in mind may help. That is, for each vertex, thinking there is an array of infinite slot, and some of them are occupied by token, and the operation correspond to moving certain token to the first hole.

Draw some small cases! What would these infinite arrays change when doing operation on root?

Doing operation on vertex with $$$p_v \lt f(v)$$$ is useless. Consider the rest situations.

when doing operation on $$$v$$$, how would $$$f(x)$$$ change if $$$x$$$ is in subtree of $$$v$$$?

There are two cases, $$$f(x) = f(v)$$$ and $$$f(x) \gt f(v)$$$.

Solve https://judge.yosupo.jp/problem/vertex_add_subtree_sum

371007707

Can you rewrite the condition on the board to something simpler?

Label the board $$$v_{i,j}$$$ where $$$v_{0,0}$$$ is the top left cell. We work mod $$$2$$$. A board $$$v_{i,j}$$$ is valid if and only if $$$v_{i,j}+v_{i+1,j}+v_{i,j+1}=0$$$ and all entries above the secondary diagonal are zero.

Warm up: try to get a construction of density $$$1/4$$$.

The next few hints get quite spoilery. If you don't want to see them yet but are stuck, consider coding some kind of heuristic (say, simulated annealing or A*) and running it on small values of $$$n$$$ to see what the result looks like.

Prove that the density is at most $$$1/3$$$.

Consider the grid $$$w_{i,j}$$$ with $$$w_{i,j}=1$$$ when $$$i+j\ge n-1$$$ and $$$i\not\equiv j\pmod 3$$$, and $$$w_{i,j}=0$$$ otherwise.

This grid is almost valid: $$$v_{i,j}+v_{i+1,j}+v_{i,j+1}=1$$$ only for very few concrete positions $$$(i,j)$$$. Try to fix the issues at those positions in a way that does not disturb much of the grid.

For each position $$$(i_0, j_0)$$$ on the diagonal where $$$w_{i_0,j_0} = 0$$$, we want to add a pattern to the grid that fixes the issues there.

For each such $$$(i_0,j_0)$$$, flip $$$w_{i_0,j_0}$$$ and add a Pascal triangle mod $$$2$$$ to the grid.

To implement this in $$$O(n^2)$$$, instead of adding each pascal independently, try to compute the sum of all of the pascals directly.

371015865