Triple Sort - TRPLSRT (CodeChef May Long Challenge)
Hello everyone !
Welcome back to my blog .
Here is a link to the PROBLEM .
So , the question is pretty simple to understand ,
We just need to sort the numbers in atmost k operations . In every operation , we will pick three indices and rightshift the values .
So , the trick to get AC in all three subtasks is that for the most complex case , k=n/2 .So , we need to sort atleast 2 numbers in an operation .
Let us look at a simple algorithm , we just , go from the 1st index to the nth , and then we just check if that number is in place .
If it is , we move on , else we check where is the number which should be placed here , if these two are swaps , we find another pair of swaps and then use 2 operations ,to sort those 4 numbers in place . Otherwise , if we could not find any other pair of swaps , we let that pair be and sort other numbers .
Else if there is a number , we find the number that should be in place and we also find the number where this number in place should go and perform a right shift on it to put 2 numbers in place.
Next we run this loop another time with a change , if we find a swap and cannot find another pair of swaps , we cant sort the number ever , we cannot swap only 2 numbers with a rightshift on three indices .
Please take a look at the following C++ code for better understanding .
Code :-
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
long int n,k;
int debug=0;
cin>>n>>k;
vector<pair<long int,long int>> v,v1;
long int i=0;
long int number;
while(i!=n)
{
cin>>number;
//number=n-i;
v.push_back(make_pair(number,i));
i++;
}
v1=v;
sort(v.begin(),v.end());
i=0;
long int x,y,z;
long int a,b,c;
long int ans=0,flag=1;
vector<pair<pair<long int,long int>,long int>> operations;
pair<long int,long int> temp1,temp,temp2;
i=0;
while(i!=n)
{
/* if(i==n-3)
{
//cout<<"yes";
if(v1[i].first==n-2 && v1[i+1].first==n-1 && v1[i+2].first==n)
{
break;
}
else if(v1[i].first==n && v1[i+1].first==n-2 && v1[i+2].first==n-1)
{
ans++;
operations.push_back(make_pair(make_pair(i+3,i+2),i+1));
break;
}
else if(v1[i].first==n-1 && v1[i+1].first==n && v1[i+2].first==n-2)
{
ans++;
operations.push_back(make_pair(make_pair(i+1,i+2),i+3));
break;
}
else
{
flag=0;
break;
}
}
else */
if(v1[i].first==i+1)
{
}
else
{
x=i;
z=v[i].second;
y=v1[i].first-1;
if(y==z)
{
int j=i+1;
while(j!=n)
{
if(v1[v1[j].first-1].first==j+1 && j!=v1[i].first-1 && v1[j].first!=j+1)
{
y=j;
// cout<<x<<" "<<y<<" "<<z<<" ";
break;
}
j++;
}
if(j==n)
{
i++;
continue;
}
else
{
ans++;
temp=v1[x];
temp1=v1[y];
temp2=v1[z];
v1[x]=temp2;
v1[y]=temp;
v1[z]=temp1;
a=v1[x].second;
b=v1[y].second;
c=v1[z].second;
v1[x].second=b;
v1[y].second=c;
v1[z].second=a;
v[v1[x].first-1].second=v1[x].second;
v[v1[y].first-1].second=v1[y].second;
v[v1[z].first-1].second=v1[z].second;
operations.push_back(make_pair(make_pair(x+1,y+1),z+1));
y=y;
x=v[y].second;
z=z;
ans++;
temp=v1[x];
temp1=v1[y];
temp2=v1[z];
v1[x]=temp2;
v1[y]=temp;
v1[z]=temp1;
a=v1[x].second;
b=v1[y].second;
c=v1[z].second;
v1[x].second=b;
v1[y].second=c;
v1[z].second=a;
v[v1[x].first-1].second=v1[x].second;
v[v1[y].first-1].second=v1[y].second;
v[v1[z].first-1].second=v1[z].second;
operations.push_back(make_pair(make_pair(x+1,y+1),z+1));
}
}
else
{
ans++;
temp=v1[x];
temp1=v1[y];
temp2=v1[z];
v1[x]=temp2;
v1[y]=temp;
v1[z]=temp1;
a=v1[x].second;
b=v1[y].second;
c=v1[z].second;
v1[x].second=b;
v1[y].second=c;
v1[z].second=a;
v[v1[x].first-1].second=v1[x].second;
v[v1[y].first-1].second=v1[y].second;
v[v1[z].first-1].second=v1[z].second;
operations.push_back(make_pair(make_pair(x+1,y+1),z+1));
}
}
if(debug==1)
{long int counter=0;
while(counter!=n)
{
cout<<v1[counter].first<<" ";
counter++;
}
cout<<endl;
}
i++;
}
i=0;
// cout<<"start"<<" ";
while(i!=n)
{
/* if(i==n-3)
{
//cout<<"yes";
if(v1[i].first==n-2 && v1[i+1].first==n-1 && v1[i+2].first==n)
{
break;
}
else if(v1[i].first==n && v1[i+1].first==n-2 && v1[i+2].first==n-1)
{
ans++;
operations.push_back(make_pair(make_pair(i+3,i+2),i+1));
break;
}
else if(v1[i].first==n-1 && v1[i+1].first==n && v1[i+2].first==n-2)
{
ans++;
operations.push_back(make_pair(make_pair(i+1,i+2),i+3));
break;
}
else
{
flag=0;
break;
}
}
else */if(v1[i].first==i+1)
{
}
else
{
x=i;
z=v[i].second;
y=v1[i].first-1;
if(y==z)
{
int j=i+1;
while(j!=n)
{
if(v1[v1[j].first-1].first==j+1 && j!=v1[i].first-1 && v1[j].first!=j+1)
{
y=j;
break;
}
j++;
}
if(j==n)
{
flag=0;
break;
}
else
{
ans++;
temp=v1[x];
temp1=v1[y];
temp2=v1[z];
v1[x]=temp2;
v1[y]=temp;
v1[z]=temp1;
a=v1[x].second;
b=v1[y].second;
c=v1[z].second;
v1[x].second=b;
v1[y].second=c;
v1[z].second=a;
v[v1[x].first-1].second=v1[x].second;
v[v1[y].first-1].second=v1[y].second;
v[v1[z].first-1].second=v1[z].second;
operations.push_back(make_pair(make_pair(x+1,y+1),z+1));
y=y;
x=v[y].second;
z=z;
ans++;
temp=v1[x];
temp1=v1[y];
temp2=v1[z];
v1[x]=temp2;
v1[y]=temp;
v1[z]=temp1;
a=v1[x].second;
b=v1[y].second;
c=v1[z].second;
v1[x].second=b;
v1[y].second=c;
v1[z].second=a;
v[v1[x].first-1].second=v1[x].second;
v[v1[y].first-1].second=v1[y].second;
v[v1[z].first-1].second=v1[z].second;
operations.push_back(make_pair(make_pair(x+1,y+1),z+1));
}
}
else
{
ans++;
temp=v1[x];
temp1=v1[y];
temp2=v1[z];
v1[x]=temp2;
v1[y]=temp;
v1[z]=temp1;
a=v1[x].second;
b=v1[y].second;
c=v1[z].second;
v1[x].second=b;
v1[y].second=c;
v1[z].second=a;
v[v1[x].first-1].second=v1[x].second;
v[v1[y].first-1].second=v1[y].second;
v[v1[z].first-1].second=v1[z].second;
operations.push_back(make_pair(make_pair(x+1,y+1),z+1));
}
}
if(debug==1)
{long int counter=0;
while(counter!=n)
{
cout<<v1[counter].first<<" ";
counter++;
}
cout<<endl;
}
i++;
}
if(flag==0 || ans>k)
{
cout<<-1<<endl;
}
else
{
cout<<ans<<endl;
vector<pair<pair<long int,long int>,long int>>::iterator it;
it=operations.begin();
while(it!=operations.end())
{
cout<<(it->first).first<<" "<<(it->first).second<<" "<<it->second<<endl;
it++;
}
}
}
// your code goes here
return 0;
}
Please leave your doubts and queries in the comments section .
Comments
Post a Comment