333 Permutation#11838

333 Permutation (Çözgüdiň düşündirişi)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Let's consider construction via mods , we've only 3 choices ${0, 1, 2}$ \{0,1,2\} , Let's notice some stable valid pattern , before that we've to identify the valid triplets

{(0, 0, 1) (0, 0, 2) (0, 1, 1) (0, 2, 2) (1, 1, 2) (1, 2, 2)}

\{ (0,0,1)\\ (0,0,2) \\ (0,1,1) \\ (0,2,2) \\ (1,1,2) \\ (1,2,2) \\ \}

and to avoid too much casework let's consider some long repeated segment that's valid , we can consider a segment of $[2, 2, 0, 0, 1, 1]$ [2,2,0,0,1,1] , notice that at worst case only 5 elements will remain to distribute correctly ! Here's the fixed segment :

[⌊ \frac{n}{6} ⌋ times 0, 0, 1, 1, 2, 2]

[\underbrace{0,0,1,1,2,2}_{\left \lfloor \displaystyle \frac{n}{6} \right \rfloor \displaystyle \text{ times}} ]

Now let's consider the remaining cases :

$n mod 6 = 0$ n \bmod 6=0 : The segment itself is ready and correct and everything is fine.
$n mod 6 = 1$ n \bmod 6=1 : This implies that $n mod 3 = 1$ n \bmod 3=1 so we've an extra element with mod 1 , this can be added to the front of construction.
$n mod 6 = 2$ n \bmod 6=2 : construct based on the previous case , this implies that $n mod 3 = 2$ n \bmod 3=2 so we've an extra element with mod 2 , this can be added to the back.
$n mod 6 = 3$ n \bmod 6=3 : Here the case is different that's because we've an extra element of each type $(0, 1, 2)$ (0,1,2) , Here we'll push to front $1$ and $2$ and 0 to back so construction will be like $[2, 1, 1, 0, 0, 1, 1, ..., 0]$ [2,1,1,0,0,1,1,...,0].
$n mod 6 = 4$ n \bmod 6=4 : construct based on the previous case , we'll have an extra $1$ , so we can add it to the front and everything is fine.
$n mod 6 = 5$ n \bmod 6=5 : construct based on the previous case , we'll have an extra 2 , we can add it to the front.

This can be done fast with $deque$ , Complexity $O (n)$ overall.

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
int solve(int n){
    if(n==4){
        cout<<"3 4 1 2\n"; 
        return 0;
    }
    if(n==5){
        cout<<"3 4 1 2 5\n";
        return 0;
    }
    deque<int>p;
    stack<int>m0,m1,m2;
    for(int i=1;i<=n;i++){
        if(i%3==0)m0.push(i);
        if(i%3==1)m1.push(i);
        if(i%3==2)m2.push(i);
    }
    for(int i=0;i<n/6;i++){
        for(int i=0;i<2;i++){
            p.pb(m2.top());
            m2.pop();
        }
        for(int i=0;i<2;i++){
            p.pb(m0.top());
            m0.pop();
        }
        for(int i=0;i<2;i++){
            p.pb(m1.top());
            m1.pop();
        }
    }
    // remains
    if(n%6==1 || n%6==2){
        p.pf(m1.top());
        m1.pop();
    }
    if(n%6==2){
        p.pb(m2.top());
        m2.pop();
    }
    if(n%6>=3){
        p.pf(m1.top());
        p.pf(m2.top());
        p.pb(m0.top());
        m1.pop();
        m2.pop();
        m0.pop();
    }
    if(n%6>=4){
        p.pb(m1.top());
    }
    
    if(n%6==5){
        p.pf(m2.top());
    }
    for(auto i:p){
        cout<<i<<" ";
    }
    cout<<"\n";
    return 0;
}  

int main() {
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        solve(n);
    }
    return 0;
}

C++