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

Solve small cases.

What happens when every value is even?

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

Let's separate odd and even numbers. One can intuitively see that it is bad to choose $$$x$$$ even since right after the other player can choose $$$x-1$$$ and get at least as many points as you did. This however is not true for odd numbers since after picking $$$x=1$$$ the opposite player cannot pick $$$x=0$$$.

Let the frequencies of the odd numbers (sorted) be $$$f_0 \geq f_1 \geq \ldots \geq f_k$$$. We claim that the difference in points between players will be $$$S = \sum_{i=0}^k (-1)^i f_i$$$. The following strategy gets at least $$$S$$$ points difference: if $$$k \gt 0$$$ choose $$$f_0$$$, otherwise choose any $$$x$$$. Now there are 3 cases.

• If player 2 chooses $$$f_i$$$ with odd $$$i$$$ you have by induction exactly $$$S$$$ points difference at the end.
• If player 2 chooses $$$f_i$$$ with even $$$i$$$ you can choose $$$f_{i-1}$$$ and by induction end up with $$$S - f_i+f_{i-1} \geq S$$$ difference at the end.
• If player 2 chooses an even $$$x$$$, copy and take $$$x-1$$$. Repeat until player 2 chooses an odd $$$x$$$. During this process you will have collected some (possibly 0) $$$f_i$$$'s and after that you will also get the alternating sum of the remaining $$$f_i$$$. Assume you remove one $$$f_i$$$ from $$$f$$$ to collect $$$f_i$$$ points. If $$$i$$$ is even, all $$$f_j$$$ signs for $$$j \gt i$$$ will be changed so you end up with $$$S + 2\sum_{j=i+1}^k(-1)^{j-(i-1)}f_j \geq S$$$. If $$$i$$$ is odd, all $$$f_j$$$ signs will be changed for $$$j\geq i$$$ so you end up with $$$S + 2\sum_{j=i}^k(-1)^{j-i}f_j \geq S$$$ which is at least $$$S$$$ in any case.

This bound is also an upper bound since player 2 gets at least $$$-f_0 + \sum_{i=1}^k (-1)^{i-1} f_i = -S$$$ points using this same strategy.

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