EQLIS - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Utkarsh Gupta
Tester: Aryan Choudhary
Editorialist: Lavish Gupta

DIFFICULTY:

Easy

PREREQUISITES:

Longest Increasing Subsequence
You do not need to know the algorithm of computing LIS, just a familiarity with the definition of LIS is sufficient.

PROBLEM:

For a permutation P of length N, we define L(P) to be the length of the longest increasing subsequence in P. That is, L(P) is the largest integer K such that there exist indices i_1 \lt i_2 \lt \ldots \lt i_K such that P_{i_1} \lt P_{i_2} \lt \ldots \lt P_{i_K}.

Define P^R to be the permutation (P_N, P_{N-1}, \ldots, P_1).

You are given a positive integer N. You need to output a permutation P of length N such that L(P) = L(P^R), or say that none exist.

Note: P is said to be a permutation of length N if P is a sequence of length N consisting of N distinct integers between 1 and N. For example, (3, 1, 2) is a permutation of length 3, but (1, 4, 2), (2, 2, 3) and (2, 1) are not.

HINTS:

  • In constructive problems, it usually helps to try figuring out the answers for lower values of N using pen and paper. It usually leads to a good number of observations, and helps in constructing the answer for the larger N.
  • In the constructive problems involving LIS, thinking in the following two directions can be sometimes useful: Constructing sequence which is first increasing and then decreasing (or vice-versa). Or breaking down the sequence in blocks, and choosing and arranging elements in block such that you can only take a single (or some fixed number of) element/s from each block.

Coming back to the problem, the following hints might be useful:

Hint 1

The answer is “NO” only for N= 2. For all other values of N, a valid permutation exists.

Hint 2

Try to find out the answer for N = 4, 5 on pen and paper.

Hint 3

For N = 4, the valid permutations are: \{2, 4, 1, 3\} and \{2 , 1 , 4 , 3\}
For N = 5, one of the valid permutations are: \{1, 2, 5, 4, 3\}

Hint 4

The answer for odd values of N is: First have an increasing sequence from 1 till \left \lfloor{\frac{N}{2}}\right \rfloor, and then have a decreasing sequence from N till \left \lceil{\frac{N}{2}}\right \rceil.

Hint 5

Try constructing answer for even values of N using the construction for odd values of N. There can be several possible solutions. One such solution is:

First have an increasing sequence from 2 till \frac{N}{2}, then have 1 and then have a decreasing sequence from N till \frac{N}{2} + 1.

So, for N = 6, the answer will be 2 , 3 , 1 , 6 , 5 , 4.

EXPLANATION:

After trying to find the permutation for N = 5 while thinking in the general directions as mentioned in the Hints section, we can figure out that the answer for odd values of N (present in Hint 4).

There is actually no algorithm of finding out the construction, you just need to play a little bit with some random permutations, and keep using the observations made in the process.

When N is even
At first, it looks like the answer will be “NO” for even values of N. However, on trying all the possible permutations for N = 4, you will see that the following two permutations are valid: \{2, 4, 1, 3\} and \{2 , 1 , 4 , 3\}

You can try to expand the solution for N = 4 to higher values, and observe the pattern.

An Incorrect way?
After seeing the permutation \{2 , 1 , 4 , 3\}, and going by the general direction of breaking sequence in blocks, it initially looks motivating to break the sequence in blocks of 2 and try to proceed further. On further pursuing, you might see some patterns, but they seemed little complicated. Do let us all know in the comment box if you have got some pattern :slight_smile:

One possible way
Because we have a solution for odd values, it looks motivating to get use the answer for N-1 and extend it to N.
One way to do this is to observe that we create Increasing Subsequences at the beginning of the permutation. If we insert 1 in the middle, it will not affect the LIS.
The same argument holds when we look at the reverse of the permutation. This motivates us to create answer for [2 \cdots N] using Hint 4, and then insert 1 in the middle. This leads to the following construction:
First have an increasing sequence from 2 till \frac{N}{2}, then have 1 and then have a decreasing sequence from N till \frac{N}{2} + 1.

TIME COMPLEXITY:

For each Test-Case, it will take O(N) time.

SOLUTION:

Tester's Solution
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         const lli u=readIntSp(1,n)-1;
//         const lli v=readIntLn(1,n)-1;
//         e[u].pb(v);
//         e[v].pb(u);
//         d.merge(u,v);
//     }
//     assert(d.size(0)==n);
//     return e;
// }

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,1e3);
lli sumN = 2e5;
while(T--)
{

    n=readIntLn(1,sumN);
    sumN-=n;
    dbg(n);
    if(n==2){
        cout<<"NO"<<endl;
        continue;
    }
    cout<<"YES"<<endl;
    lli bk=1;
    while(bk*bk<n)
        bk++;
    vector<vi> b(bk);
    lli cnt=0;
    for(lli i=0;i<bk;++i){
        cnt++;
        b[i].pb(i*bk);
    }

    for(lli i=0;i<bk&&cnt<n;++i)
        for(lli j=1;j<bk&&cnt<n;++j){
            cnt++;
            b[i].pb(i*bk+j);
        }
    vi a;
    for(auto &v:b){
        sort(all(v));
        reverse(all(v));
        a.insert(a.end(),all(v));
    }
    vi c=a;
    sort(all(c));
    (c).erase(unique(all(c)),(c).end());
    for(auto x:a){
        x=lower_bound(all(c),x)-c.begin();
        cout<<x+1<<" ";
    }
    cout<<endl;
}   aryanc403();
    readEOF();
    return 0;
}

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std ;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif

    int t ;
    cin >> t ;
    while(t--)
    {
        int n;
        cin >> n ;

        if(n == 2)
        {
            cout << "NO\n" ;
            continue ;
        }

        cout << "YES\n" ;
        if(n%2 == 1)
        {
            int val = n/2 ;
            for(int i = 1 ; i <= val ; i++)
                cout << i << ' ' ;
            for(int i = n ; i > val ; i--)
                cout << i << ' ';
            cout << '\n' ;
        }
        else
        {
            int val = (n/2);

            for(int i = 2 ; i <= val ; i++)
                cout << i << ' ';
            cout << 1 << ' ';
            for(int i = n ; i > val ; i--)
                cout << i << ' ';
            cout << '\n' ;
        }
    }
 
    return 0;
}
3 Likes
#include<bits/stdc++.h>
using namespace std;
void solve()
{
  int n;
  cin>>n;
  if(n==2) cout<<"NO";
  else if(n==4) cout<<"YES\n2 1 4 3";
  else if(n%2==1)
  {
    cout<<"YES\n";
    for(int i=1; i<=n/2; i++) cout<<i<<" "<<n+1-i<<" ";
    cout<<n/2+1;
  }
  else
  {
    cout<<"YES\n";
    cout<<"1 5 3 ";
    if(n>=8) for(int i=7; i<n; i+=2) cout<<i<<" ";
    for(int i=n; i>0; i-=2) cout<<i<<" ";
  }
  cout<<"\n";
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin>>t;
  while(t--) solve();
}

@lavish315 can you please tell why this is wrong?

#define yes cout << "YES" \
                 << "\n"
#define no cout << "NO" \
                << "\n"
#define ll long long int
void solve() {

    ll n;
    cin >> n;
    ll rn=n;
    if(n<=2){
      no;
      return;
   }
    yes;
    ll start=1;

    while(start<n){
          cout<<start<<" "<<n<<" ";
          start++;
          n--;
     }
     if(rn%2!=0)cout<<start<<endl;
     else cout<<endl;
}

Another valid permutation for N = 4 can be {1, 3, 2, 4}

Also can anyone tell why am I getting incorrect solution for the following code?

Submission link - Solution: 56696686 | CodeChef

#include <bits/stdc++.h>

using namespace std;

void compute(int n) {
	for (int i = 1; i <= n; i += 2)
		cout << i << " ";
	for (int i = n - 1; i > 0; i -= 2) 
		cout << i << " ";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int tt;
	cin >> tt;
	while (tt--) {
		int n;
		cin >> n;
		if (n == 2) {
			cout << "NO\n";
			continue;
		}
		cout << "YES\n";
		if (n % 2)
			compute(n);
		else {
			compute(n - 1);
			cout << n;
		}
		cout << "\n";
	}
	return 0;
}

Am I missing something or is my approach wrong?

Please, can anyone tell me what’s wrong in this code !!!

#include<bits/stdc++.h>
using namespace std;

int main()
{
   int t;
   cin>>t;
   while(t--)
   {
      int n;
      cin>>n;
      if(n==2)
         cout<<"NO\n";
      else
      {
         int a[n];
         int it=1;
         for(int i=0; i<n; i=i+2)
         {
            a[i] = it;
            it++;
         }
         for(int i=1; i<n; i=i+2)
         {
            a[i] = it;
            it++;
         }
         cout<<"YES\n";
         for(int i=0; i<n; i++)
         {
            cout<<a[i]<<" ";
         }
         cout<<"\n";
      }
   }
}

For N=4 => {1,3,2,4} is wrong permutation. because
Front side LIS{1,3,2,4} = 3 {1,2,4} and Back side LIS{1,3,2,4} = 2 {3,2}

Therefore the LIS from both sides are not equal, so I think your approach is wrong.

4 Likes

I got confused in subsequence and subarray.That’s why I got it wrong.

4 Likes

Thank you for clarifying my doubt!

I mis-interpreted the problem statement and inferred it as subarray instead of subsequence.

1 Like

So the subsequence doesn’t have to be consecutive?

Nope, Consecutive ones are subarray.

1 Like

If N is even integer ( >= 4)

we can break the permutation of length n into length n-2
(Reverse of permutation P is denoted as P1)
In permutation P = {N , … , N-1} , here whatever the numbers we write for all i (1 <= i <= n-2) (assuming 0-based indexing) , LIS of P will definitely include last element and LIS of P1(reverse of permutation P) will include first element . So to make LIS of P and P1 equal , LIS from index 1 to n-2 should also be equal for permutation P and P1

As every time length is decreased by 2 : N → N-2 → N-4 … → 4

using pen and paper , we can find valid permutation of length 4 easily (3 1 4 2) .

So for any N (> 4 and even) , valid permutation will be : N , N-1 , N-2 , …{3 1 4 2 } … 5 , 6 , …

for N = 10 ans will be 10 9 8 {3 1 4 2} 5 6 7
for N = 12 ans will be 12 11 10 9 {3 1 4 2} 5 6 7 8

Solution

1 Like

Can someone please tell me why this code is wrong? It passed 7 out of 8 test cases and I’m not able to figure out why it didn’t pass all 8.

#include<bits/stdc++.h>
using namespace std;
#define ll long long

void solve(){
    ll n; cin>>n;
    ll arr[n+1];
    if(n==2){cout<<"NO"<<endl; return;}
    if(n==3){
        cout<<"YES"<<endl;
        cout<<2<<" "<<1<<" "<<3<<endl; 
        return;
    }
    if(n==4){
        cout<<"YES"<<endl;
        cout<<2<<" "<<1<<" "<<4<<" "<<3<<endl;  
        return;
    }
    if(n%2==0){
        for(ll i=1; i<=n/2; i++) arr[i]=i-1;
        arr[1]=n/2;
        ll x = n;
        for(ll i=n/2+1; i<=n; i++){
            arr[i]=x;
            x--;
        }
        cout<<"YES"<<endl;
        for(ll i=1; i<=n; i++) cout<<arr[i]<<" ";
        cout<<endl;
        return;
    }
    cout<<"YES"<<endl;
    arr[1]=(n+1)/2;
    ll z=1;
    for(ll i=3; i<=(n+1)/2; i++){
        arr[i]=z;
        z++;
    }
    arr[1]=n/2;
    arr[2]=n/2+1;
    ll y = n;
    for(ll i=1+((n+1)/2); i<=n; i++){
        arr[i]=y;
        y--;
    }
    for(ll i=1; i<=n; i++) cout<<arr[i]<<" ";
    cout<<endl;
}

int main(){
    ll t; cin>>t;
    while(t--) {solve(); cout<<'\n';}
    return 0;
}

2,3,1,6,5,4.
can somebody tell me what is the Length of LIS in this, and what elements will you take.???

1 Like

From front side
LIS is 3 {2,3,6}

From Back Side
LIS is 3 {4,5,6}

It is 3. Take 2,3,4. And when reversed, take 4,5,6.

2,3,1,6,5,4 has longest increasing subsequence is 2 [2,3] but its reverse has [4,5,6,1,3,2] has longest increasing subsequence is 3 [4,5,6] how this is valid??

Also Why this approach is wrong!!
if n%2 == 0
cout<<n<<" ";
n–;
do things for n as n is now odd…

The length of longest increasing subsequence for [2, 3, 1, 6, 5, 4] is 3.
There are more than one increasing subsequences of length 3 for this case, one of them is [2, 3, 4]

1 Like

What’s wrong in my code! It’s showing perfect sequence!
Like for N=5, 1 4 5 3 2 can’t it be a perfect sequence?

int t; cin>>t;
while(t–){
int n; cin >> n;
if(n==2) cout << “NO\n”;
else{
cout << “YES\n”; cout << 1<< " ";
for(int i = n/2+2; i <=n; i++) cout << i<< " ";
for(int i = n/2+1; i >=2; i–) cout << i<< " ";
cout<<endl;
}

void solve1()
{
ll n;
cin>>n;
if(n==2)
{
cout<<“N0”<<endl;return;
}
else
{ vector ans(n);
ll s=(n/2)+1,in=0;
while(s<=n)ans[in++]=(s++);
s=(n/2);
while(s>=1)ans[in++]=(s–);
if(n%2==0)swap(ans[in-1],ans[in-2]);
reverse(all(ans));
cout<<“YES”<<endl;
for(auto i:ans)cout<<i<<’ ';cout<<endl;
}
}
?? why is it wrong

{1,4,2,3} is a valid permutation?? Also if its valid then why is my solution getting WA?

#include <bits/stdc++.h>
#define ll long long 
#define vi vector<int>
#define vll vector<long long>
using namespace std;

int main() {
	ll t;
	cin>>t;
	while(t--)
	{
	    ll n;
	    cin>>n;
	    if(n%2)
	    {
	        cout<<"Yes"<<endl;
	        for(ll i=1;i<=n;i+=2)cout<<i<<" ";
	        for(ll i=n-1;i>=2;i-=2)cout<<i<<" ";
	    }
	    else
	    {
	        if(n==2)
	        {
	            cout<<"No"<<endl;
	            continue;
	        }
	        else
	        {
	            cout<<"Yes"<<endl;
	            ll i=1,j=n;
	            while(i<n/2){cout<<i<<" ";i++;}
	            cout<<j<<" ";
	            j--;
	            for(ll k=j-1;k>=i;k--)cout<<k<<" ";
	            cout<<j;
	            
	            
	        }
	    }
	    cout<<endl;
	}
	return 0;
}