STABWAR - Editorial

PROBLEM LINK:

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

Author: negativecode
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Medium

PREREQUISITES:

None

PROBLEM:

You’re given an array P. You can do the following:

  • Choose indices i, j and set P_i := P_j.
    After this, all elements at even indices will increase by 1 every second.

Find a sequence of at most 3N + 5 operations that will result in all the elements of A becoming equal, or claim that no such sequence exists.

EXPLANATION:

Since N \geq 3, it is in fact always possible to make all the elements of P equal.

The idea here is that even-indexed elements keep increasing, so if we’re able to make all the odd-indexed elements equal, all the even-indexed ones equal, and the even elements are \leq the odd ones (with the difference being not too large), we can “wait” a while to let the even elements increase and equal the odd ones.

Here’s one solution that uses about \frac{3N}{2} moves, and doesn’t care about the initial values of P at all.

First, perform the operation (2, 1). After the increase, we’ll have P_2 = P_1 + 1.
Now, “wait” for \frac{N}{2} + c seconds (where c is some small constant like 2 or so) by repeatedly performing the operation (1, 1), which will cause A_2 to increase to P_1 + 1 + \frac{N}{2} + c.

Next, perform the operation (3, 2) to store this ‘large’ value of P_2 somewhere where it won’t change. This value is what all elements will equal in the end.
After this, set all odd-index elements except P_1 to be this target value, by performing (5, 3), (7, 3), (9, 3), \ldots

Next, perform (2, 1) again. This resets P_2 to P_1 + 1.
Now, repeatedly propagate this value among the even indices, by doing (4, 2), (6, 2), (8, 2), \ldots
This uses \frac{N}{2} - 1 moves to make all the even-index elements equal. Note that as we make them equal, they’re still all increasing, so by the end of this process all the even-index elements will be around P_1 + 1 + \frac{N}{2} or so.

After this, perform operation (1, 3) to set P_1 to be equal to the target value.
At this point, we’ve reached the situation we want: all odd-index elements are equal, all even-index elements are equal, and the even-index elements are smaller (but not by much: the difference is around c which we chose to be small).
So, simply wait for a few more moves by performing (1, 1) till everything becomes equal, and we’re done!

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define INF 1e17
#define FOR(a, b, c) for (int a = b; a < c; a++)
#define int long long
#define pb push_back
#define endl '\n'
typedef vector <int> vint;
//----------------------DEBUGGER----------------------------------------------------------
#define dbg(x) cout << #x <<" "; _print(x); cout << endl;
 
void _print(int t) {cout << t;}
void _print(string t) {cout << t;}
void _print(char t) {cout << t;}
void _print(long double t) {cout << t;}
void _print(double t) {cout << t;}
void _print(unsigned int t) {cout << t;}
 
 
template <class T> void _print(vector<vector<T>> v) {for(int j =0;j<v.size();j++){cout <<endl<<"[ "; for (T i : v[j]){_print(i); cout << " ";} cout << "]";};}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.first); cout << ","; _print(p.second); cout << "}";}
template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(vector<vector<vector<T>>> v){for(int k =0;k<v.size();k++){_print(v[k]);}}
//----------------------------------------------------------------------------------------



void solve(){
    int n; cin >> n; 
    vint v(n);

    FOR(i,0,n){
        cin >> v[i];
    }

    
    vector <pair<int,int>> seq;

    seq.pb({2, 1});                    
    FOR(i,0,n/2-1){
        seq.pb({1,1});                // wait for n/2-1 time
    }

    seq.pb({3, 2});
    if(n%2) seq.pb({1,1});

    int prev = 1;
    for(int i = 4; i <= n ; i += 2){
        seq.pb({i, prev});
        prev = i;
    }

    seq.pb({1, 2});
    seq.pb({2, 3});
    
    for(int i = 3 ; i <= n ; i += 2){
        seq.pb({i, 1});
    }
        
    cout << seq.size() << endl;
    for(auto [i, j] : seq){
        cout << i << " " << j << endl;
    }


}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(10);
    int t;
    cin >> t;
    FOR(i,1,t+1){
        solve();
    }
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case){
    ll n; cin >> n;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];

    vector<pll> ans;

    // a[1] to all evens
    for(int i = 2; i <= n; i += 2){
        if(i == 2){
            ans.pb({2,1});
        }
        else{
            ans.pb({i,i-2});
        }
    }

    // 1 idle op
    ans.pb({1,1});

    // a[2] to all odds except a[1]
    for(int i = 3; i <= n; i += 2){
        if(i == 3){
            ans.pb({3,2});
        }
        else{
            ans.pb({i,i-2});
        }
    }

    // a[1] to all evens
    for(int i = 2; i <= n; i += 2){
        if(i == 2){
            ans.pb({2,1});
        }
        else{
            ans.pb({i,i-2});
        }
    }

    // a[1] = a[3]
    ans.pb({1,3});

    assert(sz(ans) <= 3*n/2+5);

    cout << sz(ans) << endl;
    for(auto [i,j] : ans){
        cout << i << " " << j << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n);
        for (int &x : a) cin >> x;

        vector<array<int, 2>> ops;
        auto op = [&] (int i, int j) {
            ops.push_back({i, j});
        };

        op(1, 2);
        for (int i = 0; i < n/2 + 1; ++i) op(1, 1);

        op(2, 3);
        int target = a[0] + 1 + n/2 + 1;
        for (int i = 5; i <= n; i += 2) op(i-2, i);

        op(1, 2); // a[1] + 1
        a[1] = a[0] + 1;
        for (int i = 4; i <= n; i += 2) op(i-2, i), ++a[1];
        op(3, 1); ++a[1];
        while (a[1] != target) {
            op(1, 1);
            ++a[1];
        }

        cout << size(ops) << '\n';
        for (auto [x, y] : ops) cout << y << ' ' << x << '\n';
    }
}

If someone have other solutions to this please share.