How big can the answer be?

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

This problem is about handling cases.

The main solution is to quickly realize that $$$x \lt y$$$ can be done in 2 moves and $$$x \gt y+1$$$ with $$$y \gt 1$$$ in 3. You can guess that other cases are impossible.

Using two moves, we can move to any ($$$x$$$,$$$y$$$) with $$$x \lt y$$$ by first moving $$$x$$$ and then $$$y$$$. Using 3 moves $$$0 \lt a \lt b \lt c$$$ we get to ($$$a+c$$$,$$$b$$$) as follows: first to ($$$a$$$,$$$0$$$), then to ($$$a$$$, $$$b$$$), and then to ( $$$a+c$$$, $$$b$$$). Without loss of generality we can subtract $$$1$$$ from $$$a$$$ and add $$$1$$$ to $$$c$$$ anytime so we can assume $$$a=1$$$ and hence we can reach ($$$x$$$, $$$y$$$) in $$$3$$$ moves if and only if $$$x \gt y+1$$$ and $$$y \gt 1$$$.

Now assume we can reach some ($$$x$$$, $$$y$$$) with $$$k \gt 3$$$ jumps. The last two jumps can be merged with the previous 2 jumps giving a solution with $$$k-2$$$ jumps. Hence any other case is impossible.

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

There are multiple ways to solve this problem. We believe the easiest one is based on the following construction:

It's easy to see that both occurrences of $$$n$$$ are at a distance of $$$n$$$, and all the other values appear at a distance of twice their value. In other words, we place the two $$$n$$$'s at the first position and at the $$$(n+1)$$$-th position, then we use the second $$$n$$$ as a pivot to place numbers from $$$1$$$ to $$$n-1$$$ in order.

There exist other constructions as well. For example, for $$$n$$$ odd, we can use:

For $$$n$$$ even, the pattern is similar but we adjust the positions of $$$n-1$$$ and $$$n-2$$$ accordingly.

A greedy algorithm also works: we go from $$$n$$$ to $$$1$$$, and try to place each number in the leftmost possible position. Note that this greedy algorithm follows the same pattern as the first construction.

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

The first observation is to notice that every substring ``11'' splits the problem into two subproblems since rabbits on opposite sides cannot interact with each other. For instance, in the string $$$0110$$$, the rabbits placed in positions $$$1$$$ and $$$4$$$ cannot interact with each other.

The second observation is that if we split the string in a way such that each subproblem does not contain two consecutive $$$1$$$'s, the string $$$101010 \dots 0101$$$ (no consecutive 0's) is solvable iff the number of 0's is even since we can match the rabbits in the following way $$$1R1L1R \dots R1L1$$$ (where $$$R$$$ means that we place a rabbit looking to the right and $$$L$$$ means that we place a rabbit looking to the left).

The last observation is that if we have two consecutive $$$0$$$'s, we can split the problem using them in a way that every subproblem looks like this alternating pattern ($$$101010 \dots 0101$$$) with an odd number of $$$0$$$'s. Thus, the only thing we need to look for is a substring with this alternating pattern that has an odd number of zeros.

We should also take care of boundary conditions. If the string starts or ends with a zero, we can ignore that position by placing the rabbit looking towards the border; these cases were present in the sample tests.

Alternatively, we can solve the problem using a dp that considers $$$dp_{i, L}$$$ = Is it possible to solve the prefix $$${0, 1, \dots, i}$$$ placing the rabbit in position $$$i$$$ looking to the left, and $$$dp_{i, R}$$$ defined in the same way.

#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();
}