TRIPLE_INVS Editorial

editorial
, , ,
1

DIFFICULTY:

2169

Consider a binary string S of length N+1, where S_i = 1 if P_i<P_{i+1} and S_i = 0 otherwise. Clearly, we have A_ i = 3 \iff S_i = S_{i+1} = 0, A_i = 0 \iff S_i = S_{i+1} = 1. If S_i \neq S_{i+1}, then A_i can be both 1 and 2.

So, we get some conditions of form S_i = S_{i+1} = 0, S_i = S_{i+1} = 1, S_i \neq S_{i+1}. I claim that if there exists a binary string satisfying all these conditions then there exists a corresponding permutation. Indeed, let’s build a permutation of length N+1 for the A_1, A_2, \ldots, A_{N-1}. Then:

  • If A_N = 0, just set P_{N+2} = N+2.
  • If A_N = 3, set P_{N+2} = 1, and increase all previous elements by 1.
  • If A_N = 1, and P_N = x, then set P_{N+2} \to x+1, P_N \to x, and increase all other elements which are at least x+1 by 1.
  • If A_N = 2, and P_N = x, then set P_{N+2} \to x, P_N \to x+1, and increase all other elements which are at least x+1 by 1.

Now, how to check if such a string S exists? Start with S_1 = 0 or 1, build string based on conditions S_i = or \neq S_{i+1}, check if it satisfies all the conditions.

5 Likes
2

another approach

let x,y,z be 3 triplets such that x<y<z then we get inversions for following arrangements:
0 inversion → xyz
1 inversion → xzy / yxz
2 inversion → zxy / yzx
3 inversion → zyx

for the current inversion we need to analyze the last 2 char of previous inversion, so we just put these values and check if we can form the required permutation.

Solution: 64040008 | CodeChef

9 Likes
3

Can someone please help me i am getting segmentation fault for my code i have done the same thing as told in the editorial. Here is the link to my submission
https://www.codechef.com/viewsolution/64063623

4

O(n) Solution

We can observer that for any 3 numbers, only certain combinations are possible. Let 'a1, a2, a3` be the numbers.

Inversions = [a1 > a2] + [a2 > a3] + [a1 > a3] => where [.] denotes 0 or 1 depending upon the condition is true or false.

If we write all permutations of ‘1, 2, 3’ we can see only certain inequalities are mutually consistent.

Screenshot 2022-05-02 at 10.01.07 AM
Screenshot 2022-05-02 at 10.01.07 AM1040×448 27.8 KB

Let p1, p2, p3 be first 3 numbers, depending upon A[0] they follow some order.
Depending upon the current order. We know the state of [p2 > p3]. So, for any next number A[i], A[1] in this case, we can generate p4. We know inversions in [p2, p3, p4] = A[1], we know if [p2 > p3]. But notice that these 2 were last 2 number in the previous step, but they are now first 2 numbers in the current step.
Create a look up table as follows
A[number_of_inversions][a1 > a2] = [a2 > a3] We dont need to used last column here.
Only the states mentioned above are possible.
Now we need to check if we can generate all next number of not.

Its hard to explain this way, look at the code for more clarity.
CodeChef: Practical coding for everyone

void solve() {
    int n;
    cin >> n;
    int x[n];
    for(int i = 0; i < n; i++) cin >> x[i];

    int a[4][2]; // number of inversion, first pair a1 > a2
    memset(a, -1, sizeof(a));
    a[0][0] = 0;
    a[1][0] = 1;
    a[1][1] = 0;
    a[2][0] = 1;
    a[2][1] = 0;
    a[3][1] = 1;

    auto check = [&] (int next) {
        for(int i = 1; i < n; i++) {
            next = a[x[i]][next];
            if(next == -1) return false;
        }
        return true;
    };

    bool ans = false;
    if(x[0] == 0) ans = check(0);
    else if(x[0] == 1 || x[0] == 2) ans = check(0) || check(1);
    else if(x[0] == 3) ans = check(1);

    if(ans) cout << "YES\n";
    else cout << "NO\n";

}
9 Likes
5

Nice Approach brother

6

Can anyone help me debug it?
I want a failing test case for my approach:

 
bool fun(int a[],int b[],int indx,int n,int m)
{
    if(indx==n)
    {
        int z=a[indx-1];
        int z1=b[indx-1]+b[indx];
        return z==z1;
    }
    bool ans=false;
    if(b[indx]==-1)
    {
        int z=a[indx];
        if(z==0)
        {
            b[indx]=0;
            b[indx+1]=0;
            ans=ans|fun(a,b,indx+1,n,m);
        } 
        else if(z==1)
        {
            b[indx]=1;
            b[indx+1]=0;
            ans=ans|fun(a,b,indx+1,n,m);
            b[indx]=0;
            b[indx+1]=1;
            ans=ans|fun(a,b,indx+1,n,m);
        }
        else if(z==2)
        {
            b[indx]=2;
            b[indx+1]=0;
            ans=ans|fun(a,b,indx+1,n,m);
            b[indx]=1;
            b[indx+1]=1;
            ans=ans|fun(a,b,indx+1,n,m);
        }
        else 
        {
            b[indx]=2;
            b[indx+1]=1;
            ans=ans|fun(a,b,indx+1,n,m);
        }
    }
    else 
    {
        int z=a[indx];
        if(z==0)
        {
            if(b[indx]>0)
            {
                return false;
            }
            b[indx+1]=0;
            ans=ans|fun(a,b,indx+1,n,m);
        }
        else if(z==1)
        {
            if(b[indx]==1)
            {
                b[indx+1]=0;
                ans=ans|fun(a,b,indx+1,n,m);
            }
            else 
            {
                b[indx+1]=1;
                ans=ans|fun(a,b,indx+1,n,m);
            }
        }
        else if(z==2)
        {
            if(b[indx]=0)
            {
                b[indx]=1;
                b[indx+1]=1;
                ans=ans|fun(a,b,indx+1,n,m);
            }
            else 
            {
                b[indx]=2;
                b[indx+1]=0;
                ans=ans|fun(a,b,indx+1,n,m);
            }
        }
        else if(z==3)
        {
            if(b[indx]==0)
            {
                return false;
            }
            b[indx]=2;
            b[indx+1]=1;
            ans=ans|fun(a,b,indx+1,n,m);
        }
    }
    return ans;
}
void solve(int t)
{
   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }
   int m=n+1;
   int p=0,b[m];
   for(int i=0;i<m;i++)
   {
       b[i]=-1;
   }
   if(fun(a,b,0,n,m))
   {
       cout<<"Yes\n";
       return;
   }
   cout<<"No\n";
7

Try this Input:

1
4
2 0 2 0
1 Like
8

nice approach !

9

can anyone tell me where to practice these types of problems? like in which tags these problem comes in. I struggle to solve these types of problem

10

Can anyone help me find the issue in this answer?

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
for(int ti=0;ti<t;ti++){
int n =scanner.nextInt();
int a;
int res=0;
int f=0;
for(int i=0;i<n;i++){
a =scanner.nextInt();
if(a==0){
if(res==-1){
f=1;
break;
}
res=1;
}
else if (a==1){
res=res*-1;
}else if (a==2){
res=res*-1;
}else{
if(res==1){
f=1;
break;
}
res=-1;
}
}
if(f==1){
System.out.println(“NO”);
}
else{
System.out.println(“YES”);
}
}
scanner.close();
}
}

11

Great approach

12

Out of curiosity, what kind of algorithm does this belong to?
State Machine？

transfer condition: inversion count
    input state: first pair a1 > a2
    output state: second pair a2 > a3
    
    (state) a1 ? a2 
      -> (condition) 
    (state) a2 ? a3
      -> (condition)
    (sate) a3 ? a4
      -> (condition)
    ...
13

Can someone help me with my code.
I will explain my approach first. For inversion_count = 3 and inversion_count = 0, we have only 1 possible way for each of them. Let x ,y ,z be 3 numbers that belong to our permutation vector and x<y<z.
For inv =3 → zyx
For inv = 0 → xyz
For inv = 1-> yxz / xzy
For inv =2 → zxy/yzx

So basically there are 4 total possibilites 2 for inv - 1 and 2 for inv = 2. I calculated permutation vector with each possible combination possible and i started from behind if inv = 3 or 2 or 1 or 0 i arranged the 3 numbers respectively.

and then i just checked in pairs of 3 whether the inversion count for each 3 numbers is coming equal to A or not.
All of my test cases are passing but i was getting TA and all the other TC’s i made myself are also passing. In short i am not able to find any tc where my code can give error.

My Solution

14

Thanks a lot!! Got it.

15

Amazing solution. Thanks for sharing.
I came up with the triplets logic regarding what the values can be for 0,1,2, and 3. But couldn’t find a way to incorporate that into a solution.

I’m concerned about one thing in your solution. Had I implemented it on my own, I’d run into the problem of reusing the last 2 characters from the previous value in arr. Your solution just ignores them and passes new values at each step. Can that not be a problem? Also, did you get stuck at this step while implementing it yourself?

16

Hey @adityamonu_17
Thanks for asking your doubt.

There is some typo in your code.

This must be

if(b[idx]==0)

and m must be n+2.

17

Yeah! I figured it out and got it AC.

18

ya initially I was thinking of building the permutation itself with this logic, but then the question demanded only for yes and no , so I limited myself just with comparisons.

but i guess we can build the permutation too, if we once just find the configuration

test case 1

4
0 1 3 2

-> 012 + 021 + 210 + 201
so if we add them up we get
 012
  021 
   210 
+   201
----------
 016401

now we start placing numbers of the permutation starting from greater value:
6-> replaced by 6
4-> replaced by 5
1-> replaced by 4 or 3 (doesn't matter)
0-> replaced by 2 or 1 (doesn't matter)
so permutation will be

[ 1/2 , 4/3 , 6 , 5 , 3/4 , 2/1]

so there are 4 valid permutations for this test case.
```:
2 Likes
19

kindly elaborate on proof for generating permutation P , given a valid binary string S?