There is at most one cycle of length 3. After removing them and all edges which have an end point in that cycle, the resulting graph is bipartite. (Assume answer is "Yes")

• For now don't consider the equality in the condition |ai — aj| >= L/2. That is for now, there is edge if and only of |ai-aj| > L/2
• Partition the nodes with values in [0, L/2] and [L/2+1, L]. Since the maximum difference achievable in each partition is at-most L/2. There can not be any edge.
• This is means the graph is bipartite, with the above partition. With a special property that I will describe below. Also, if we have any bipartite graph with that property, we can always assign values in such a way that the above holds.
• Now let's consider the equality -
• Partition the graph as before. But we can have a edge between the first node and last node in the first partition — if sorted according to values. If there is then. Also in that case value of first node will be 0 and the last will be L/2.
• Also, we can have at most one outgoing edge from the last node in first partition. This means last node of first partition must be a part of some simple odd-length cycle of the original graph and has degree 2.
• So to solve this problem, we need to detect that special node. And then verify the special property that I mentioned above. And assign values greedily.
• special property is nothing but if there is edge from a node to u and to v then there is edge from that node to every node u <= x <= v. If we consider the nodes according to sorted values.

Disclaimer : I have coded this up but could not get accepted. Submission

Simple dp, with extreme amount of case handling. Consider cases where the size of the array is even/ odd, the current index in dp you are at is even/odd and wether you performed swap in the previous step or not.

States will be dp[last][idx], last indicating wether swap was performed for last index, and idx needs to move only until mid of the array.

You can calculate n3 mod 30 then check (n3 mod 30) mod 3 == 0

first calculate (d0+d1)%10 and then divide into group of 4s . the pattern will repeat like ; 2,4,8,6 and lastly add those. for ex. d3 = 2*(d0+d1)%10 , d4 = 4*(d0+d1)%10 , d5 = 8*(d0+d1)%10, d6 = 6*(d0+d1)%10 , like this the pattern will repeat for K/4 groups , you have to add the remaining . here is the code:

#include <bits/stdc++.h>
using namespace std;
 
 
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
#define PII pair<ll,ll> 
 
 
 
typedef long long ll;
ll x;
 
ll MOD = 1e9+7;
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
 
ll modexp(ll a, ll b, ll mod){
	ll res = 1;
	while(b){
		if(b&1)	res = (res*a)%mod;
		b = b>>1;
		a = (a*a)%mod;
	}
	return res;
}
 
int main(){
	boost;
	ll T,N,i,j,k,L,l,m,n,R;
	ll K;
	cin >> T;
	ll S;
	ll d0,d1;
	while(T--){
		cin >> K >> d0 >> d1;
		ll sum = (d0+d1)%3;
		ll s2 = 0;
		if(K == 2){
			if(sum%3 == 0)	cout << "YES" << endl;
			else	 cout << "NO" << endl;
			continue;
		}
		K -= 2;
		K -= 1;
		s2 += (d0+d1)%10;
		//for(i = 0 ; i < K/4 ; i++){
		s2 += K/4 * ((2*(d0+d1))%10+(4*(d0+d1))%10+(8*(d0+d1))%10+(6*(d0+d1))%10);
		//}
		K %= 4;
		if(K){
			s2 += (2*(d0+d1))%10;
			K--;
		}
		if(K){
			s2 += (4*(d0+d1))%10;
			K--;
		}
		if(K){
			s2 += (8*(d0+d1))%10;
			K--;
		}
		if(K){
			s2 += (6*(d0+d1))%10;
			K--;
		}
 
		//s2 %= 10;
		s2 %= 3;
		if((sum+s2)%3 == 0)	cout << "YES" << endl;
		else	cout << "NO" << endl;
 
	}
 
} 

It's a straightforward DP problem :D DP1[i]=min swaps if not swapping [i, n-i+1] in interval [i, n-i+1] DP2[i]=min swaps if swapping [i, n-i+1] in interval [i, n-i+1] You can be a little clever and just count the numbers if a1>a2<a3... and then multiply every number by -1 and do it one more time :)