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 and only 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

371035963

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

How big can the answer be?

Which coordinates can you reach in $$$2$$$ or $$$3$$$ moves?

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
#define int long long
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		int x,y;
		cin>>x>>y;
		if(x==y || x==y+1 || y==1)cout<<-1<<endl;
		else if(x<y)cout<<2<<endl;
		else cout<<3<<endl;
	}
}

Don't over complicate, there is a simple construction

There is a construction where each number $$$x$$$ is placed at distance either $$$x$$$ or $$$2 \cdot x$$$.

Here is a construction where only the number $$$n$$$ is placed at distance $$$n$$$. All other numbers are placed at distance $$$2 \cdot x$$$.

There is a construction where the first element of the array is always $$$n$$$.

#include <bits/stdc++.h>
using namespace std;
 
int t, n;
 
signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = n; i >= 1; i--) {
      cout << i << " ";
    }
    cout << n;
    for (int i = 1; i < n; i++) {
      cout << " " << i;
    }
    cout << "\n";
  }
}

If we have two consecutive $$$1$$$'s, the rabbits on the left and right of this block are independent. We can divide our problem into multiple subproblems.

If one of these subproblems mentioned in hint $$$1$$$ contains two consecutive 0's, can we solve this subproblem?

If we don't have consecutive $$$0$$$'s in these subproblems mentioned in hint $$$1$$$, the pattern looks like $$$10101 \dots 10101$$$, in which of these patterns can we place the rabbits?

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n; cin >> n;
	string s; cin >> s;
	bool ok = true;
	bool curr = (s[0] == '1');
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '0')
			cnt++;
		if (i == 0)
			continue;
		if (s[i] == s[i-1] && s[i] == '0')
			curr = false;
		if (s[i] == s[i-1] && s[i] == '1') {
			if (curr && cnt % 2 == 1)
				ok = false;
			curr = true;
			cnt = 0;
		}
	}
	
	if (curr && cnt % 2 == 1 && s[n-1] == '1')
		ok = false;
		
	cout << (ok ? "YES" : "NO") << "\n";
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T; cin >> T;
	while (T--)
		solve();
}

Solve small cases.

What happens when every value is even?

How can we add exactly one odd number to the solution of hint 2?

339616059

The answer is bounded by $$$31$$$.

We will precalculate the minimum operations for each answer.

How will the bitwise or look like if we want to increase the popcount from the original by increasing the number of $$$1$$$'s.

We can show that it is better to fill the least significant $$$0$$$'s first.

What is the best way to fill a certain bit.

The solution is a greedy algorithm.

339616091

Solve the problem in $$$\mathcal{O}(n b + t b^2 + q \log (b))$$$.

Try to understand what are the SCCs.

They are a line. Given the sizes of the SCC, find a closed formula for the answer.

Think how to maintain the formula using data structures.

339616164

There was a lot of cheating on this problem, which is why there were many in-contest solves. Cheaters will be banned. We’re sorry if the high solve count during the contest misled anyone, but please understand that this isn’t something the authors, coordinators, or codeforces can control.

What happens when $$$n$$$ is big?

$$$b_n$$$ is $$$a^{a^N}$$$ for some big $$$N$$$.

Given $$$a$$$ and $$$m$$$ find a condition for $$$a$$$ to be $$$m$$$-tetrative.

The condition is $$$\forall p|ord_m(a), p|a$$$.

Fix the number of values of $$$a$$$ such that $$$ord_m(a) = k$$$ and get a formula.

If $$$m$$$ is an odd prime power, the number above for $$$k|\varphi(m)$$$ is $$$\varphi(k)$$$.

Manipulate the formula until it only depends on the prime divisors of $$$\varphi(m)$$$ that are not in $$$m$$$.

Factor it to calculate it in $$$O(\log m)$$$.

339616197

Think of min-cut instead of max-flow.

Can you think of a sufficient condition so that all the min-cuts between any pair of vertices are divisible by the same number?

In fact, the expected sufficient condition implies that all cuts of the graph (not just min-cuts) are divisible by the same number.

The minimum number of colors is always $$$1$$$ or $$$2$$$. You can check if the answer is $$$1$$$ by brute force.

It is possible to make all cuts even in each induced subgraph using just $$$2$$$ colors.

339616226

The expected is $$$n = mlogm - O(m)$$$ steps using harmonic sum.

Think of a solution in 2D (not needed but good intuition).

Put points as an almost regular polygon and keep doing circles around it jumping with step $$$1$$$, then $$$2$$$, then $$$3$$$...

Think how to project this solution to 1D

339616257

There is a $$$n = 2m-3$$$ solution that will be useful: given two groups of points in arithmetic progression far enough apart you can add two pivots in the middle to keep jumping from the left to the right group: ..... .. .....

The goal is to recursively construct a solution using smaller ones.

339616281