 # CONSTRRAY - Editorial

Author: nirkhut
Preparer: satyam_343
Testers: iceknight1093, yash_daga
Editorialist: iceknight1093

TBD

None

# PROBLEM:

Construct an array of length N such that for each 1 \leq i \lt N,

• If i is odd, P(i) \gt S(i)
• If i is even, P(i) \lt S(i)

P(i) denotes the sum of the first i elements of A, S(i) denotes the sum of the last i elements of A.

# EXPLANATION:

Looking at what the inequalities given to us mean in terms of the values of A, we see that:

• A_1 \gt A_N
• A_1 + A_2 \lt A_N + A_{N-1}
• A_1 + A_2 + A_3 \gt A_N + A_{N-1} + A_{N-2}
\vdots

Intuitively, for the inequalities to reverse we see A_2 should be “much smaller” than A_{N-1}; A_3 should be “much larger” than A_{N-2}; and so on.
In general,

• If i is odd, A_i should be much larger than A_{N+1-i}
• If i is even, A_i should be much smaller than A_{N+1-i}

In particular, A_i can never equal \$A_{N+1-i} for any 1 \leq i \leq N.

Notice that this immediately tells us that when N is odd, no such array can exist: we would require the middle element to not equal itself, which is obviously impossible.

Now let’s deal with the case when N is even.

One easy way to deal with the “much larger/much smaller” conditions is to make one of the elements positive and the other negative. Setting one of them to x and the other to -x for an appropriately chosen x will give us what we want.

Let’s try to build A in this fashion.

• First, set A_1 = 1 and A_N = -1. This ensures A_1 \gt A_N.
• Now, if we set A_2 = -2 and A_{N-2} = 2, we get P(2) = -1 and S(2) = 1, satisfying the inequality.
• Once again, it’s easy to see that setting A_3 = 2 and A_{N-2} = -2 gives us P(3) = 1 and S(3) = -1, as necessary.
\vdots

In general, alternating between 2 and -2 (except for the first and last elements) will give us what we want:

• If i is even
• P(i) = 1 + (-2) + 2 + (-2) + \ldots + (-2) = -1
• S(i) = -1 + 2 + (-2) + 2 + \ldots + 2 = 1
• If i is odd
• P(i) = 1 + (-2) + 2 + (-2) + \ldots + 2 = 1
• S(i) = -1 + 2 + (-2) + 2 + \ldots + (-2) = -1

This satisfies all the inequalities we have, and so is a valid array.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

Preparer's code (C++)
//#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;
const ll MAX=500500;
void solve(){
ll n; cin>>n;
if(n&1){
cout<<"-1\n";
}
else{
if(n==4){
cout<<"0 5 343 -100\n";
return;
}
cout<<"1";
ll use=-2;
for(ll i=2;i<n;i++){
cout<<" "<<use;
use*=-1;
}
cout<<" -1\n";
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
if n%2 == 0: print( *([-1] + [2, -2]*(n//2 - 1) + ) )
else: print(-1)


CONSTRRAY
can anyone tell me why this is giving WA?

void solve(){
int n;
cin>>n;
if(n%2!=0)
cout<<-1<<endl;
else{
int a = 1;
int b = n*-1;
for(int i =0 ;i<n/2;i++){
cout<<a++<<" ";
cout<<b++<<" ";
}
cout<<endl;
}
}


It fails when N starts becoming slightly large, for example N = 10.

You print [1, -10, 2, -9, 3, -8, 4, -7, 5, -6].
The sum of the first 5 elements is -13, the sum of the last 5 elements is -12.