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.

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
const int N = 1e6+6;
const int B = 61;
 
ll a[N], a2[N];
 
ll calcor(ll* arr, int n) {
    ll curor = 0;
    for (int i = 0; i < n; ++i) curor |= arr[i];
    return curor;
}
 
signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ///
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        for (int i = 0; i < n; ++i) cin >> a[i];
        vector<pair<ll, int>> prec;
        int curbits = __builtin_popcountll(calcor(a, n));
        prec.push_back({0, curbits});
        for (int k = 0; k < B; ++k) if (!((calcor(a, n) >> k)&1ll)) {
            ll curops = 0;
            for (int j = 0; j < n; ++j) a2[j] = a[j];
            for (int b = k; b >= 0; --b) if (!((calcor(a2, n) >> b)&1ll)) {
                int pos = 0;
                ll bt = 1ll << b;
                for (int i = 0; i < n; ++i) {
                    if ((a2[i]&(bt-1)) > (a2[pos]&(bt-1))) pos = i;
                }
                ll ops = bt-(a2[pos]&(bt-1));
                a2[pos] += ops;
                curops += ops;
            }
            ++curbits;
            prec.push_back({curops, curbits});
        }
        while (q--) {
            ll bi;
            cin >> bi;
            cout << prev(lower_bound(prec.begin(), prec.end(), pair<ll, int>({bi+1, -1})))->second << '\n';
        }
    }
}

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

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