# FINDPERM343 - Editorial

Author: satyam_343
Tester: tabr
Editorialist: iceknight1093

TBD

None

# PROBLEM:

You’re given an array A that contains every integer from 1 to N exactly twice.
Find a permutation P of \{1, 2, \ldots, N\} such that:

• For each i = 1, 2, \ldots, N, delete both instances of P_j for j \gt i.
In the resulting array, the two occurrences of P_i should have at most \frac{|A|}{2} elements between them.

# EXPLANATION:

Observe that when checking the condition for i, we’re essentially taking the subsequence of A that contains only the elements \{P_1, P_2, \ldots, P_i\}; everything else is deleted.
Each such element occurs exactly twice in A, so this subsequence has length 2i — and our aim is to ensure that in this subsequence, both occurrences of P_i have at most \frac{2i}{2} = i elements between them.

Since there are i-1 distinct elements (other than P_i), one way to achieve this is to ensure that each P_j (for j\lt i) occurs at most once between the occurrences of P_i.

One relatively easy way to attain this is as follows:

• Let L_i denote the index of the leftmost occurrence of i in A.
This is easily computed in \mathcal{O}(N) time.
• Then, create P in increasing order of L_i values.
That is, P_i will be the element with the i-th smallest L-value.

For example, if A = [1, 2, 1, 4, 2, 3, 3, 4], we’ll have L = [1, 2, 6, 4].
This gives us the answer permutation P = [1, 2, 4, 3].

It’s not hard to see that this always works: after all, when looking at P_i, we know that for every j \lt i L_{P_j} \lt L_{P_i} will hold (by construction).
This means each P_j occurs at least once before the leftmost occurrence of P_i, meaning each P_j can also occur at most once between the two occurrences of P_i — exactly what we wanted!

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

Author's code (C++)
#pragma GCC optimize("O3,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 int
#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;
vector<ll> ans,found(n+5,0);
for(ll i=1;i<=2*n;i++){
ll x; cin>>x;
if(!found[x]){
ans.push_back(x);
}
found[x]=1;
}
for(ll i=0;i<n;i++){
cout<<ans[i]<<" \n"[i+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";
}


Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#define IGNORE_CR

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}

assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}

string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
input_checker in;
int sn = 0;
while (tt--) {
sn += n;
auto a = in.readInts(2 * n, 1, n);
{
vector<int> b(n);
for (int i : a) {
b[i - 1]++;
}
for (int i = 0; i < n; i++) {
assert(b[i] == 2);
}
}
vector<int> c(n, -1);
for (int i = 0; i < 2 * n; i++) {
if (c[a[i] - 1] == -1) {
c[a[i] - 1] = i;
}
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return c[i] < c[j];
});
for (int i = 0; i < n; i++) {
cout << order[i] + 1 << " ";
}
cout << '\n';
}
assert(sn <= 3e5);
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
lt = [2*n+1]*(n+1)
for i in range(2*n):
x = a[i]
lt[x] = min(lt[x], i)
ind = list(range(1, n+1))
ind.sort(key= lambda x: lt[x])
print(*ind)

2 Likes

What will be issue with Greedy approach ?

Whenever we find second occurrence of any number, we will delete that number.

Logic : Worst-case scenario, we didn’t delete any number from first n/2 numbers. Now n/2 + 1th number MUST be deleted, if we didn’t delete single number from first ‘n/2’ number numbers.

@iceknight1093

If we fill P from P_N to P_1 based on index of second occurrence in A, you get AC: Submission. This doesn’t always work if you fill P from P_1 to P_N since we can have test cases like A = [1, 2, 3, 3, 2,1]

1 Like

What’s wrong if i sort the numbers based on their gaps between occurances.that’s the array P.Where am i going wrong here

Instead of sorting in increasing order of gaps, sort them in decreasing order of gaps. It will get AC CodeChef: Practical coding for everyone

This is also the alternative soln I have. Its not difficult to prove why this works.

Counter testcase for sorting in increasing order

3 1 2 2 1 3
Your submission prints 2 1 3, but for 3 the gap is 5 which is more than 6/2.

3 Likes

Why will it not work ? please elaborate ? Even when we have test-case like

Step 1 : Delete 3
[ 1 , 2 , 3 , 3 , 2 , 1 ] , The distance between both 3 is less than 6/2 , so we can delete it.

Step 2: delete 2
[ 1 , 2 , 2 , 1 ] , is the remaining array. Now we can delete 2.

Step 3: delete 1
[1 1] is the remaining array.

The process you’re doing is exactly what @stephen_allen mentions - “fill P from P_N to P_1 based on index of second occurrence in A” (this is also basically the same thing as the editorial solution, just on the reversed array).

The first number you delete will be the last element of P (notice that the statement says that when the condition for i is being checked, we delete all P_j for j \gt i, not j \lt i).

My approach doesn’t care about P_N to P_1 , or reverse of it.

My approach is,

1. TRAVEL INPUT ARRAY, FROM LEFT TO RIGHT. initialize ans = [] (empty list/vector ).
2. Whenever  we find second occurrence of the element, delete it, and append it to answer.
3. Print Ans.


This solution passes [ 1 , 2 , 3 , 3 , 2 , 1 ] . It will delete values from array in 3 , 2 , 1 order.

Where am I going wrong in logic ?

So the answer array you create is [3, 2, 1] yes?

1 Like

Yes, so the answer we create by the above algorithm is [ 3 , 2 , 1 ] . I am confused, what is wrong in that answer ?

We are deleting numbers in reverse order of the final printed answer… is that right ? @iceknight1093 ?

Let’s take A = [1, 2, 3, 3, 2, 1] and your answer, P = [3, 2, 1], and see what the statement says for i = 3.

• For every j \gt i, delete P_j from the array.
Since i = 3, there’s no such j and nothing gets deleted.
• This means A = [1, 2, 3, 3, 2, 1].
Now, P_3 = 1, and the distance between the ones is 4.
4 is strictly larger than |A|/2 = 6/2 = 3, so this is wrong.

Your approach very much does care - P is the answer array.
What stephen_allen meant is that you build the answer array from right to left. You’re building it from left to right (that’s what appending does).

1 Like

got it bhai. another example of, why reading problem statement is important. I thought, “printing sequence of deleting elements in order” is sufficient. But it was in reverse order.

Sorry.

Thank you for clarifications.

I submitted my code but it shows judge error why ?