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?

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ld = long double;
using ll = long long;
const int maxN = 2e5+5;
const int INF = 1e18;
const int MOD = 1e9+7;
#define F first
#define S second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd(int b){
	return (unsigned long long)rng()%b;
}
int power(int a, int b){
	if(b==0)return 1;
	if(b%2)return a*power(a,b-1)%MOD;
	return power(a*a%MOD,b/2);
}
int inv(int a){
	return power(a,MOD-2);
}
vector<int>fact(maxN);
vector<int>invfact(maxN);
 
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
 
		map<int,int>freq;
		int s= 0;
		int sum = 0;
		for(int i = 0;i<n;i++){
			int x;
			cin>>x;
			if(x%2)freq[x]++, s+=x-1;
			else s+=x;
			sum +=x;
		}
		int A = s/2;;
		vector<int>b;
		for(auto [u,v] : freq)b.push_back(v);
		sort(b.rbegin(),b.rend());
		for(int i = 0;i<b.size();i+=2)A+=b[i];
		cout<<A<<" "<<sum-A<<endl;
 
	}
	
}

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.

339612536

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.

339608901

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)$$$.

339609655

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.

339609874

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

339610927

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.

339611036