MONMED - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given a permutation of odd length N, find any sequence of \frac{N+1}{2} subarrays such that:

  • The subarrays have lengths 1, 3, 5, \ldots, N
  • Each subarray contains the previous one
  • The medians of the subarrays are strictly increasing

EXPLANATION:

Observe that the final subarray is forced to be the entirety of [1, N], whose median is \frac{N+1}{2}.

Since we want \frac{N+1}{2} subarrays with increasing medians, with the largest median being \frac{N+1}{2}, the sequence of medians we’re forced to have is

1, 2, 3, \ldots, \frac{N+1}{2}

So, the i-th subarray must have length 2i-1 and a median of i.

For a subarray of length 2i-1 to have a median of i, it must contain i, then i-1 elements smaller than i and i-1 elements larger than i.
However, “i-1 elements smaller than i” can only be all the elements 1, 2, \ldots, i-1.
Further, if a subarray of length 2i-1 contains all of 1, 2, \ldots, i, then since we’re working with a permutation all the remaining elements are strictly larger than i.

Thus, a subarray of a permutation of length 2i-1 has median i if and only if it contains all the values 1, 2, \ldots, i.

Define L_i to be the smallest index containing an element \le i, and R_i to be the largest index containing an element \le i.
A subarray contains all the values from 1 to i if and only if it starts \le L_i and ends \ge R_i.

In particular, observe that if we fix the length to 2i-1, the set of left endpoints of subarrays of this length that contain every value from 1 to i forms a contiguous range.
Let lo_i and hi_i denote the endpoints of this range for i.
(If the range is empty for any i \le \frac{N+1}{2} clearly no solution exists, so we assume all such ranges are non-empty.)

Also, a subarray of length s starting at position x is contained inside a subarray of length s+2 starting at position y if and only if y \in [x-2, x].

So, our goal is to find a sequence of left endpoints L_1, L_2, \ldots, L_k such that:

  • lo_i \le L_i \le hi_i, and
  • L_{i+1} \in [L_i-2, L_i].

This is doable in linear time.

Observe that after processing values 1, 2, \ldots, i, the set of valid left endpoints of a sequence of length i will in fact form an interval by itself.
This interval can be kept updated with lo_{i+1} and hi_{i+1} as we go fairly easily, using the L_{i+1} \in [L_i-2, L_i] condition.

If this “active” interval ever becomes empty, no solution exists; otherwise a solution always exists and reconstruction is not hard given that we have the valid interval of left endpoints always.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> p(n + 1), pos(n + 1);
    
    for (int i = 1; i <= n; i++){
        cin >> p[i];
        pos[p[i]] = i;
    }
    
    vector <pair<int, int>> vec;
    int L = n, R = 1;
    int k = (n + 1) / 2;
    
    for (int i = 1; i <= k; i++){
        L = min(L, pos[i]);
        R = max(R, pos[i]);
        
        if (R - L + 1 > 2 * i - 1){
            cout << -1 << "\n";
            return;
        }
        vec.push_back({L, R});
    }
    
    vec.push_back({1, n});
    
    vector <pair<int, int>> seq;
    auto [l, r] = vec[0];
    seq.push_back(vec[0]);
    for (int i = 1; i < vec.size(); i++){
        while (l > vec[i].first){
            l--;
            seq.push_back({l, r});
        }
        while (r < vec[i].second){
            r++;
            seq.push_back({l, r});
        }
    }
    
    assert(seq.size() == n);
    for (int i = 0; i < k; i++){
        cout << seq[2 * i].first << " " << seq[2 * i].second << "\n";
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
MONMED2 - Editorial