CONSTRRAY - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

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

DIFFICULTY:

TBD

PREREQUISITES:

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; 
const ll INF_ADD=1e18; 
#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;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
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) + [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.