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$$$?

339616059

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