FIX - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: ro27
Tester: mexomerf
Editorialist: raysh07

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

An array A of length n is given, and we need to construct the lexicographically maximal array B of length n, such that every element of B is present in A, and each element in prefix of A, i.e. A_1, A_2, ...., A_i is present at least once in the corresponding prefix of B, i.e. B_1, B_2, ...., B_i.

EXPLANATION:

The general idea behind a lot of lexicographically maximal (or minimal) problems is to try to construct the sequence starting from the first element and greedily trying to choose the maximal (or minimal) element which still allows a valid sequence to be formed.

Let M denote the maximum element in A.

For now, assume that we have constructed the sequence upto (i - 1) elements B_1, B_2,..., B_{i - 1}, and need to decide B_i. if A_i has already occured in the sequence B_1, B_2, ...., B_{i - 1}, then set B_i = M (recall that every element of B has to be present in A) otherwise set B_i = A_i.

It is easy to see this algorithm always constructs a valid sequence, and we always choose the largest element which still allows a valid sequence, thus making it lexicographically maximal possible. To check if A_i occurs in the prefix of B, we can use a set.

A slightly more intuitive way to think of it is: if i is the first time A_i has occured in the array A, then set B_i = A_i, else B_i = M. It’s not hard to see that this is also equivalent to the previous solution.

TIME COMPLEXITY:

\mathcal{O}(nlogn) per testcase.

CODE:

Editorialist's Code (C++) 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int t; cin >> t;
    
    while (t--){
        int n; cin >> n;
        
        vector <int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        
        int mx = 0;
        for (int i = 0; i < n; i++) mx = max(mx, a[i]);
        
        set <int> st;
        for (int i = 0; i < n; i++){
            if (st.find(a[i]) == st.end()){
                cout << a[i] << " ";
            } else {
                cout << mx << " ";
            }
            st.insert(a[i]);
        }
        
        cout << "\n";
    }
    return 0;
}
1 Like